感谢狗亮 提供的拉链法知识

拉链法

Hash Map

日常的话我们定义对象都是key=>value的方式(大多面像对象的都是)比如定义一个人:

image.png

计算的储存:

计算机存储空间有两个属性：存储地址和所存储的值，机器可以根据给定的存储地址去读写该地址下的值。根据这种结构，假如我们将一块存储空间分成一个一个的格子，然后将这些数据依次塞到每个格子里，接下来我们就可以根据格子编号直接访问格子的内容了。这种方式就是数组（也叫线性连续表）：数组头保存整个数组储存空间的起始地址，不同下标代表不同的储存地址的偏移量，访问不同下标所对应的地址就能实现数组元素的读写。所以，很自然就会想到将上述的键值对数据的key映射成数组下标，接着读写数组就变成了读写value值。将key的字符串转换成代表下标数值比较简单，可以用特定的码表（如ASCII）进行转换.（复制来的）

分析白话:

so..小明的属性名（key）经过变换，可能就变成了这样：

[图片上传中...(image.png-fbcffd-1562815573420-0)]

由于key的值不同长度不一，所以转换后的下标的值也相差巨大，另外key的个数不确定，也就意味着下标的个数也有很大的范围，甚至无穷多，就有了下面的问题：

?>怎么将一组值相差范围巨大，个数波动范围很大的下标放入特定的数组空间
?>如何处理冲突的问题.

简单的解决方案(网上常见复制散列)

直接取下标值作为存储数组的下标，虽然简单，但是你会发现这个长度为10010的数组只存了8个值，太浪费,如果我们想要缩短数组的长度,比如缩为10,最简单的方式可以使用取模的方式来确定下标：69 % 10 = 9，7 % 10 = 7, 198 % 10 = 8……。这个取模就是哈希算法、也叫散列算法。
通过这样的方式得到的下标分别为9、7、8、3、6、2、0，可以得到保存小明数据的数组:

image.png

这样就造成了hash 冲突(碰撞)
这种方式很容易出现重复,假如我们增加一个属性phone,对应的映射值是29,那么29跟69算出来的下标就重复了.也就是哈希算法中的冲突,也叫碰撞。好的哈希算法能极大减少冲突，但由于输入几乎是无穷的，而输出却要求在有限的空间内，所以冲突是不可避免的。

解决冲突:

29和69发生了冲突，但可以将他们组成一个链表,链表的头部放在数组中,得到一个链表结构，每个元素（除单向链表的尾部）都包含了相连元素的内存地址和本身的值，上面的冲突放入一个链表中，可以得到这样的结构：

image.png

最终得到的这个数据结构，也就是我们常说哈希表了。这种将数组与链表结合生成哈希表的方法，叫拉链法。

ps:

哈希表数据的查找:

比如想知道小明的name属性，即小明.name。流程：

1> 根据字符映射关系得到映射值为69
2>使用哈希算法得到下标 index=hash(69)=9
3）遍历数组中下标为9的链表，链表的第一个元素的key刚好就是我们要找的name，所以返回value值小明
哈希表中增删一个元素并不会影响到其他的元素，不像数组一样需要改变后面所有的元素下标。在拉链式的哈希表中，属性的增删就是链表的增删，非常方便。而在纯数组形式的哈希表中，对属性的删并不是真的删除，而是做一个空标志而已，所以不影响其他元素。