哈希表
大致介绍
1、哈希表的本质是一个数组；
2、数组中每一个元素称为一个箱子；
3、它通过把关键码值映射到表中一个位置(箱子的位置)来访问记录，以加快查找的速度；
4、映射函数叫做散列函数(也叫哈希函数)，存放记录的数组叫做散列表，也就是哈希表；
哈希表的存储过程如下
根据 key 计算出它的哈希值 h。
假设箱子的个数为 n，那么这个键值对应该放在第（(h % n)——一种散列算法）个箱子中。
如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决(1.7及之前的HashMap)冲突。
在使用拉链法解决哈希冲突时，每个箱子其实是一个链表，属于同一个箱子的所有键值对都会排列在链表中。
以汉语字典比喻(大致，非恰当)
假设 汉语字典一共500页，汉字共有500个发音，共有20000个字需要存储。以读音作为key，汉字作为value的话。
那么用发音对于汉字的位置作散列的话，也算是一种hash算法吧。
那么一页存一个音，就会有的页数字多，有的字少。把每页的字数多少就比喻成哈希冲突。
把每页的字的顺序排列，看成一个单项链表的话，就成了hash链。
有区别在于，我们查汉字，需要针对发音找目录，查看哪个音在哪一页。而计算机是，直接计算这个音的hash值，直接告诉你在哪一页。
详细
网友评论