定义

  1. 散列表也叫哈希表，是根据关键码值直接进行访问的数据结构
  2. 把关键码值映射到表中的方法 - 哈希函数
  3. 存放记录的表 - 实际存储结构

实现思路

  1. 创建存储位置，建立一个数组用来存放元素
  2. 创建哈希函数，最重要的一步
  3. 通过计算后的位置存储元素
  1. class HashMap {
  2.     constructor() {
  3.         this.list = []
  4.     }
  6.     hashCode(key) {
  7.         return key.length % 10
  8.     } 
  10.     put(key, value) {
  11.         this.list[ this.hashCode(key) ] = value
  12.     } 
  14.     get (key) {
  15.         return this.list[ this.hashCode(key) ]
  16.     }
  18.     remove (key) {
  19.         this.list[ this.hashCode(key) ] = undefined
  20.     }
  22.     clear () {
  23.         this.list = []
  24.     }
  25. }
  27. const hashMap = new HashMap();
  29. hashMap.put('animal', 'dog');
  31. console.log(hashMap.get('animal')); // 'dog'

哈希函数

  1. 直接给地址法， 比如人口统计表，统计1-100岁的人数，可以直接使用年龄作为地址，无需经过hash计算

    1. function hashCode(age) { return age }

  2. 数字分析法 ```javascript / 一个班级的学生要统计出生日期 年。月。日 96.10.07 96.12.16 96.05.17 96.05.11 96.12.08 96.11.13 …… /

  1. 经过数据分析，只有前三位的重复性比较大，去前三位造成的冲突可能比较大，只用后三位比较好
  3. 3. 平均取中法
  4. ```javascript
  5. const hashCode = (key) => {
  6.     const len = `${key.length * key.length}`
  7.   return len.slice(1, len.length - 1)
  8. }
  9. hashCode('my name is xiaobai') // 结果是324 取最中间的一位为 2

  1. 取余法

    1. // 如果哈希表的最大存储长度为30
    2. const hashCode = (key) => {
    3.  return key % 30
    4. }

  2. 随机数法

    1. const hashCode = (key) => {
    2.  return Math.floor(Math.random() * key.length)
    3. }

哈希冲突
哈希冲突就是两个key经过哈希函数处理后得到了一样的值
无论设计多么精细，都逃脱不了冲突的命运，需要一些首都来避免或者解决这种冲突现象

  1. 链地址法， 发现要添加的位置已经有一个元素，可以将这个地址改为链表存储
  2. 多哈希法， 多设计几种哈希函数， 经过多次hash函数的处理，降低冲突的概览
  3. 开放地址法
    1. 线性探测：线性探测是逐步搜索空的位置。缺点：数据项聚集，越来越大，越后面找到空位插入数据项需要时间越多
    2. 二次探测：寻找和插入都是在起始下标的1,4,9，16……位置后寻找数据或将数据插入空白单元，即步长是按平方增大的，有可能超过整型范围。克服了方法1的大片聚集，但是仍然会产生二次聚集，这个问题不大
    3. 再哈希法：通过给不同关键字设置不同步长解决数据项聚集的问题，开放地址法中常使用此方法
  4. 桶地址法，为表中的每个地址关联一个桶，如果桶满了，就是用开放地址法处理

小结

  1. 什么是散列表
  2. 哈希函数的定义方式，直接给定地址，数字分析，平方取中，取余，随机数
  3. 哈希冲突产生和解决方法， 链地址法，多哈希法，开放地址法，桶地址法

练习题

替换 val 值。并且保证替换前相同的节点替换后也相同
注：使用时间复杂度尽可能小的算法（解题方式不唯一）

  1. // 替换前 第4 8 24 行的val相同，替换后，这几行的val依然相同。
  2. let data = [
  3.   {
  4.     val: 1.235464654,
  5.     child: {
  6.       val: 0.656464848,
  7.       child: {
  8.         val: 1.235464654,
  9.         child: {
  10.           val: 1.467487978,
  11.           child: {
  12.             val: 0.656464848,
  13.             child: {
  14.               // ………………
  15.             }
  16.           }
  17.         }
  18.       }
  19.     }
  20.   }
  21. ];
  1. 创建一个表，用来存储生成的随机数
  2. 循环遍历data下第一层的子节点，由于data为数组，所以使用forEach来遍历
  3. 创建一个新的函数遍历第二层之后的子节点
  4. 查询节点的val值，如果map中保存了，则说明之前生成过，此时直接替换child.val即可
  5. 如果在map中没有获取到值，则重新生成一个，并且保存到map中
  6. 如果还有后继的child节点，则递归处理 ```javascript const map = new Map() replaceSameElement(data) function replaceData(data) { data.forEach(item => { deepReplace(item) }) }

function deepReplace(child) { let childVal = map.get(child.val) if (!childVal) { childVal = (Math.random() * 10).toFixed(9) map.set(child.val, childVal) } child.val = childVal;

if (child.child) { deepRepalce(child.child) } } ```