本文源码这里

理论

特点

1.基于数组创建的一种数据结构2.存储元素时，对每一个元素通过哈希函数，进行哈希化后存储3.存储后的这个数组就叫做哈希表(HashTable，也有叫散列表的)

和数组对比

优点

比数组更快的查找速度(因为删除，修改基于查找所以效率也提高)

缺点

key值不可以重复哈希表没有顺序，不能以一定的顺序遍历

哈希函数

1.当在一百万数据的数组中，根据内容查找一个元素和根据那个元素的下标来查找时，时间差距很大 2.哈希函数做的事就是把一个元素的key值转换成一个数字，然后在数组中以这个数字为下表存入数据3.查找时，也是根据存入时哈希化(使用哈希函数对key进行转换的过程)的key值条件,先对其哈希化然后通过哈希化后的数字去数组中查找4.一个好的哈希函数应该具有2个特点:

1.快速计算(减少乘法，乘法比加法在计算机中更耗费性能)
2.哈希后的数组下标要尽可能平均

冲突

当哈希化key值后出现的数字发生重复时这种现象叫做冲突冲突的解决方案

1.链地址法(用的更多，下文代码实现也使用这种方式)

存储元素时，用数组或链表进行存储

2.开放地址法(寻找还是空的位置来存储)

线性探测：以一定的规则来寻找下一个空位置来存储，这个规则得出的数一般是一个质数，称做步长.

代码实现

封装哈希表

封装方法：

哈希函数---hash(key)

传入要哈希的key，然后将该key值每个字母转换成ASCII码做和在进行一定的处理，以下函数规则参考自《学习JavaScript数据结构与算法》

存储元素---put(obj)

传入要存储的元素(下文是存储一个对象)，存储时先通过哈希函数将某个属性(下文是name)哈希化得到要存储的位置，然后在存储时进行判断：1.该位置为空，直接插入；2.不为空，对比查看name值是否相同，不同插入在最后，若相同，覆盖；

获取元素---get(str)

传入要查找的的内容(存储时哈希化的属性name)，查找时先通过哈希函数将查找值哈希化得到目标位置，然后直接查找，有返回整个对象；无，返回null

function HashTable() {
  //  存储元素的数组
  this.items = [];
  // 哈希函数
  HashTable.prototype.hash = function (key) {
    let hashCode = 5381;
    for (let i = 0; i < key.length; i++) {
      hashCode = 33 * hashCode + key.charCodeAt();
    }
    return hashCode % 1013;
  };
  // 存和改
  HashTable.prototype.put = function (obj) {
    let index = this.hash(obj.name);
    // 初始化该位置
    let current = this.items[index];
    // 判断要存储位置是否为空
    if (current == null) {
      this.items[index] = [];
      current = this.items[index];
      // 为空 直接插入到第一个位置
      current.push(obj);
    } else {
      // 不为空 判断和里面的元素是否相同
      for (let i = 0; i < current.length; i++) {
        // 相同修改
        if (current[i].name == obj.name) {
          current[i] = obj;
          return;
        }
      }
      // 不同 插入到最后
      current.push(obj);
    }
  };
  // 取
  HashTable.prototype.get = function (str) {
    let index = this.hash(str);
    let current = this.items[index];
    if (current != null) {
      for (let i = 0; i < current.length; i++) {
        if (current[i].name == str) {
          return current[i];
        }
      }
    }
    return null;
  };
}
// 测试代码

let hs = new HashTable();
// 创建一个对象并存如
let shuaxin = {
  name: "shuaxin",
  phone: "158****26**",
};
hs.put(shuaxin);
// 测试哈希表和数组查找效率对比
// 先给数组空的位置插入模拟数据 100w
function insert() {
  for (let i = 0; i < 1000000; i++) {
    if (hs.items[i] == null) {
      hs.items[i] = [
        {
          name: "demo",
          phone: "456",
        },
      ];
    } else {
      continue;
    }
  }
}
insert();
// 数组普通的对比查找
function find(str) {
  // console.log(str);
  for (let i in hs.items) {
    if (str == hs.items[i][0].name) {
      return hs.items[i][0];
    }
  }
  return null;
}

// 上文图片的结果
console.warn("100w数据中效率对比");
// 250+ms
console.time("遍历查找");
console.log(find("shuaxin"));
console.timeEnd("遍历查找");
// 1ms左右
console.time("哈希查找");
console.log(hs.get("shuaxin"));
console.timeEnd("哈希查找");

《学习JavaScript数据结构与算法》笔记---哈希表

本文源码 这里

理论

代码实现

本文源码这里