哈希表/散列表 ​

简介 ​

哈希表是一种以 "key-value" 形式存储数据的数据结构，其特点是能够通过key快速找到对应的value，时间复杂度为O(1)。

实现方法 ​

给定哈希表一个长度n，计算出要存储数据的key的code值：

// 计算 key 对应的 char code
let hash = Array.from(key).reduce((hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)), 0)
// 取余
hash = hash % n

// 计算 key 对应的 char code
let hash = Array.from(key).reduce((hashAccumulator, keySymbol) => (hashAccumulator + keySymbol.charCodeAt(0)), 0)
// 取余
hash = hash % n

然后在计算出的hash位置，存放value值。下次查找时，计算出hash即可快速找到存放在这里的value值了。

由于键值是取余得来的，为了尽量避免key算出来的hash重复度较高，一般情况下哈希表的长度都是取比较合适的质数。

哈希冲突 ​

由于可能存在多个不同的key最后计算出来的code值相同，这就造成了哈希冲突，一般解决哈希冲突有两种方法：开链法和线性探索法。

开链法的实现原理是将多个相同code值的元素用链表的形式添加。这样每次通过计算出的code可以找出对应的链表，这个链表里存放着所有相关的元素，然后通过链表进行查找，最终通过对比当前要查找的key和链表里存放的key来找到对应的value。

线性探索法是如果存放元素时，计算出的code位置已被占用，那么会寻找下一个位置。如果下一个位置没有被占用，那么就将该元素存放与此。下次取的时候，也会依照这个线性关系去查找对应的key。

线性探索法一般适用于元素数目相较于哈希表长度比较小的情况，开链法则相反。