哈希表

大致介绍

1、哈希表的本质是一个数组；

2、数组中每一个元素称为一个箱子；

3、它通过把关键码值映射到表中一个位置(箱子的位置)来访问记录，以加快查找的速度；

4、映射函数叫做散列函数(也叫哈希函数)，存放记录的数组叫做散列表，也就是哈希表；

哈希表的存储过程如下

根据 key 计算出它的哈希值 h。

假设箱子的个数为 n，那么这个键值对应该放在第（(h % n)——一种散列算法）个箱子中。

如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决(1.7及之前的HashMap)冲突。

在使用拉链法解决哈希冲突时，每个箱子其实是一个链表，属于同一个箱子的所有键值对都会排列在链表中。

以汉语字典比喻(大致，非恰当)

    假设 汉语字典一共500页，汉字共有500个发音，共有20000个字需要存储。以读音作为key，汉字作为value的话。

    那么用发音对于汉字的位置作散列的话，也算是一种hash算法吧。

    那么一页存一个音，就会有的页数字多，有的字少。把每页的字数多少就比喻成哈希冲突。

    把每页的字的顺序排列，看成一个单项链表的话，就成了hash链。

有区别在于，我们查汉字，需要针对发音找目录，查看哪个音在哪一页。而计算机是，直接计算这个音的hash值，直接告诉你在哪一页。

详细

见https://www.cnblogs.com/chinajava/p/5808416.html