哈希表的基本原理，包括通过哈希函数将键值映射为索引以实现快速定位。重点讲解了冲突避免策略，如哈希函数设计（除留余数法、线性函数法）和负载因子调控（扩表）。详细阐述了冲突解决方法，涵盖闭散列（线性探测、二次探测及删除的墓碑标记）和开散列（链式结构）。最后分析了哈希表的时间复杂度优势（O(1)）以及空间利用率较低的固有缺陷。
把节点的键值通过哈希函数计算映射成索引，直接确定在数组中的存储位置。相较于进去搜寻与一个个比较的确定方式，维护的映射确定存储能使得哈希表实现对数据的极速定位来操作（存储、查询、修改、删除）。
不同元素的不同键值多个对应映射到哈希表相同索引处时，存储冲突就发生了。为尽量避免哈希表里面去深度存储或降低深度存储时的复杂度，我们要做的就是降低键值存储时的冲突率，通过合理的哈希函数设计或存储的键值多时去扩表调控负载因子。
哈希函数要使得要来的键值都能且尽量均匀少重叠地对应转为哈希数组的索引范围内。
键值 % 数组长度的值域为 0~数组长度 -1，即刚好面向存储的哈希数组所有位置存放。且对于大部分套数据，不规则的模上数组长度得到的也是不规则值域，最后散落在哈希数组中均匀分布的。
如果套数据连续紧凑，也可以设置成线性函数 A*Key+B 对应连续紧凑地对上数组。
填入表中的元素越多时，元素之间的存储冲突概率就会变大。大到一定程度时就通过扩表将表的存储冲突率再降下去，动态地调控使表的冲突率维持在一个范围之下。
扩表时，表的容量改变。如果哈希函数与表的容量相关的，哈希函数也改变，键值映射到的索引也会改变需要更新，即要把所有元素去重新哈希重新映射存储。
扩表代码
private void resize() {
Node[] tmpArr = new Node[array.length * 2];
// 遍历原来的数组 将所有的元素《重新哈希》到新的数组当中
for (int i = 0; i < array.length; i++) {
Node cur = array[i];
while (cur != null) {
// 每个索引桶里面的链表全部节点都要重新哈希
// 记录当前链表节点的下个节点
Node curNext = cur.next;
// 重新映射的索引
int newIndex = cur.key % tmpArr.length;
// 头插
cur.next = tmpArr[newIndex];
tmpArr[newIndex] = cur;
cur = curNext;
}
}
array = tmpArr;
}
元素的键值多个对应映射到哈希表相同索引处时，存储冲突就发生了，要把冲突元素进行二次分配。
闭散列把冲突元素分配到哈希表的其它空位上。
如果键值存储计算的索引冲突了，那么将冲突的键值按照规定的探测方式找到并放到表中其它剩余的空位里，下次查询时都是如果遇到已填上就按照约定以约定的探测方法会再往后查查看。
以冲突索引为起始点，(index+i)%table_size（i=1,2,3...）线性探测以常量 1 为增量一个个往后增键值化索引探测找空位放。
线性探测一个个往后填空位的方式在后面会使得空位被填成冲突点成线性成块直线连续。
理想情况下是直到有次找空位找到回起始冲突点时，说明表已填满而去扩表，但实际肯定会在表满之前负载因子挺高时就直接退出探测去扩表了。
填空的直线分布会导致后续的每次找空位都会连续地遍历表近 O(n)，时间复杂度会变得很高，所以不会等到表真的全填满，在负载因子超过一定数值后表就留空位用不上而去扩表了，而且线性探测时负载因子会设得很低，每次表留的空位会很多，维护的表的空间利用率很低。
以冲突索引为起始点，(index+i²)%table_size（i=1,2,3...）二次探测以探寻次数 i 的平方变量为增量往后跳跃增键值化索引去探测空位放。
用二次探测的表的容量要设置为 table_size=4k+3 的质数，这样能保证二次探测能探测到表的所有位置。
能不规则地整体均匀地探测存储冲突率小。
所以探测找空位循环的结束条件就设置成的是探测次数超过表容量时就停下。
以不规则跳跃性地探测，表容量次中肯定会有很多次的重复探测而且越到后面就会呈现出很多空位点实际而且是需要不止表容量次才能探测到的，就会出现表实际还有很多空位而认为表满而退出去扩表，这样的一直维护就会导致任意次每次创的表中都会有很多空位创建来而用不上填不上去存储而就又去扩表的，再加上负载因子条件的主动退出填表，表的空间利用率会低（二次探测因为不规则的存储与跳跃探测，能承受的负载因子会更高时再去扩表，空间利用率比线性探测的会高点）。
删除元素时，采用墓碑标记删除，节点还是存储在那存在，仅把节点的状态标记为删除。
墓碑实现代码
class HashEntry {
final int key;
String value;
boolean isDeleted; // 标记删除时不清空数据
void delete() {
isDeleted = true;
}
}
开散列把冲突元素分配到同桶的链式结构上。
分配放到的桶存储链式结构可以是链表、红黑树、或又是一个哈希表。
链式结构的链条过长时，通过扩表或转红黑树减短链长。
虽然有时候需要进行二次分配、二次搜索，但经过合理的哈希函数设计、调控负载因子的扩表，哈希表的冲突率调控得是比较低的，每索引桶里面如果有冲突，冲突元素的个数也是常量级的，二次存储的结构也就比较简单，往二次存储结构搜索的时间复杂度也是 O(1)，所以总体哈希表的定位元素去插删查的时间复杂度是 O(1)。
哈希表的闭散列冲突解决方式的空间利用率是很低的，虽然开散列的空间利用率不会像闭散列低得很明显，但空间利用率低就是哈希本质的缺陷。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online