共计 2039 个字符，预计需要花费 6 分钟才能阅读完成。
散列表：
素数哈希、ASCII 哈希，还有 djb2
素数哈希：把一个素数作为模数（modulus number）
来给你举一个例子，在这个例子里，咱们把 11 这个素数作为了模数，用上面的一组键值对中的键除以模数，所取得的余数，放到一个数组中。就造成了一个散列表。
{key:7, value: "南昌"}
{key:24, value: "太原"}
{key:42, value: "郑州"}
Prime number: 11
7 % 11 = 7 // 余数为 7
24 % 11 = 2 // 余数为 2
42 % 11 = 9 // 余数为 9 存在的问题：如果解决的数据数量足够多，那么就会呈现抵触的状况。
为了尽量减少这种抵触，业界也在尝试其余方法，比方应用 ASCII code 和素数联合来生成哈希，但这种形式和下面的素数哈希一样，即便联合了 ASCII，哈希值也不能完全避免碰撞的产生，只能缩小抵触。
asciiHashCode(key) {if (typeof key === 'number') {return key;}
const tableKey = this.toStrFn(key);
let hash = 0;
for (let i = 0; i < tableKey.length; i++) {hash += tableKey.charCodeAt(i);
}
return hash % 37;
}djb2 的算法：
先用一个长质数 5381 作为哈希数，而后依据字符串长度循环，将哈希数乘以 33，再加上字符的 ASCII 码迭代。后果和模数 1013 的余数后果就是最初的哈希值。
djb2HashCode(key) {const tableKey = this.toStrFn(key);
let hash = 5381;
for (let i = 0; i < tableKey.length; i++) {hash = (hash * 33) + tableKey.charCodeAt(i);
}
return hash % 1013;
} 字典：如何查找对象的内存地址
散列表能够只有值，没有键，能够说是数组延长进去的索引。
通常字典是有键值对的。字典作为一种数据结构，又叫做映射（map）、符号表（symbol table）或者关联数组（associative array）。
在 JavaScript 中，咱们其实能够把对象看做是一种能够用来构建字典的一种散列表，因为对象里就蕴含 key-value 的属性。
对象在栈的援用和它在堆中的理论存储间的关联就是通过地址映射来实现的。这种映射关系就是通过字典来存储的。
Map 和 Set：各解决什么问题
JavaScript 中的 Map 就是字典的构造，它外面蕴含的就是键值对。咱们说过对象就是一个能够用来实现字典的反对键值对的散列表。Map 和对象最大的区别就是 Map 里的键能够是字符串以外的其它数据结构，比方对象也能够是一个键名。
JavaScript 中的 Set 就是汇合的构造，它外面蕴含值，没有键。与数组的区别次要在于 JS 中的汇合属于无序汇合，并且外面不能有雷同的元素。
WeakMap 或 WeakSet
第一，它们都是弱类型，代表没有键的强援用。所以 JavaScript 在垃圾回收时能够清理掉整条记录。第二个起因，也是它的特点，在于既然 WeakMap 里没有键值的迭代，只能通过钥匙能力取到相干的值，所以保障了外部的封装公有属性。
散列抵触：解决哈希碰撞的形式
线性探查法、平方探测法和二度哈希法。
线性探查法
当一个散列碰撞产生时，程序会持续往上来找下一个空地位，比方在之前例子中，7 被南昌占用了，北京就会顺移到 8。
平方探测法
平方探测法用平方值来代替线性探查法中的往后顺移一位的形式，这样就能够做到基于无效的指数做更均匀的散布。
二度哈希法
第一次的哈希的根底上再次哈希。在上面公式里，x 是第一次哈希的后果，R 小于哈希表。假如每次迭代序列号是 i，每次哈希碰撞通过 i * hash2(x) 来解决。hash2(x) = R − (x % R)
HashMap：Java 是如何解决散列抵触的？
HashMap、LinkedHashMap 和 TreeMap。
HashMap：底层逻辑是通过链表和红黑树实现的。
规定是，当哈希函数生成的哈希值有抵触的时候，就把有抵触的数据放到一个链表中，以此来解决哈希碰撞。当抵触的数据过多的时候，它就会产生性能上的问题，这个时候用增删改查的红黑树来代替会更适合。
散列加链表：基于双链表存值排序
LinkedHashMap：是在 HashMap 的根底上，外部维持了一个双向链表（Doubly Linked List），它利用了双向链表的性能特点，能够起到另外一个十分重要的作用，就是能够放弃插入的数据元素的程序。
TreeMap：基于红黑树的键值排序
TreeMap 也是 Java 一种基于红黑树实现的字典，然而它和 HashMap 有着实质的不同，它齐全不是基于散列表的。而是基于红黑树来实现的。相比 HashMap 的无序和 LinkedHashMap 的存值有序，TreeMap 实现的是键值有序。它的查问效率不如 HashMap 和 LinkedHashMap，然而相比前两者，它是线程平安的。