一文彻底搞定哈希表( 三 ) _哈希表

咋样，这块明白了嘛？
小白：嗯嗯，明白的，庆哥继续！
庆哥：那好，我们继续，键值对说的简单点就是有一个key和一个value对应着，比如这张图里的学生信息：

文章插图

学生的学号和姓名就是一个键值对啊，根据这个学号就能找到这个学生的姓名，那啥是Entry嘞，我们都知道键值对，在很多语言中也许都有键值对，说白了就是个大众脸啊，咋弄，在咱jdk中可不能那么俗气，不能再叫键值对了，叫啥嘞，那就叫Entry吧
咋样，知道啥是键值对和Entry了吧！
小白：必须滴啊，讲的那么生动，这张图感觉远不止如此啊，庆哥继续啊
哈希表如何存数据庆哥：好滴，那咱们就继续，来说说哈希表是如何存放数据的，记得看上面的图啊，我们按照这个图来说，我们已经知道了哈希表本质是个数组，所以这里有个数组，长度是8，现在我们要做的是把这个学生信息存放到哈希表中，也就是这个数组中去，那我们需要考虑怎么去存放呢？
这里的学号是个key，我们之前也知道了，哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是用来确定这个Entry要存放在哈希表中的位置的，实际上这个值就是一个下标值，来确定放在数组的哪个位置上。
比如这里的学号是101011，那么经过哈希函数的计算之后得到了1，这个1就是告诉我们应该把这个Entry放到哪个位置，这个1就是数组的确切位置的下标，也就是需要放在数组中下表为1的位置，如图中所示。
我们之前已经介绍过什么是Entry了，所以这里你要知道，数组中1的位置存放的是一个Entry，它不是一个简单的单个数值，而是一个键值对，也就是存放了key和value，key就是学号101011，value就是张三，我们经过哈希函数计算得出的1只是为了确定这个Entry该放在哪个位置而已。
现在我们就成功把这个Entry放到了哈希表中了，怎么样，这块听懂了嘛？
小白：嗯嗯，听懂了，不过看到这里我产生了一个疑问，那就是这个哈希函数，是不是有一个特定的加工过程，比如可以经过某种计算把101011转换成1，那么有没有可能其他的学号经过哈希函数的计算也得出1呢？那这个时候是不是就撞衫啦
哈希冲突庆哥：的确，你分析得很正确，我们再来看下面这张图：

文章插图

你说的这种情况就像图中展示的那样，学号为102011的李四，他的学号经过哈希函数的计算也得出了1，那么也要放到数组中为1的位置，可是这个位置之前已经被张三占了啊，这怎么办？这种情况就是哈希冲突或者也叫哈希碰撞。
既然出现了这情况，不能不管李四啊，总得给他找个位置啊，怎么找呢？
小白：我猜肯定有什么方法可以给李四找位置
处理哈希冲突庆哥：那必须滴啊，有什么方法呢？其实关于哈希冲突的解决办法有好几种嘞，但是我这里只介绍两种主要的方法，一个是开放寻址法，一个是拉链法。
那什么是开放寻址法呢？我们继续来看图：

文章插图

我觉得看图就足以说明问题了，这里所说的开放寻址法其实简单来说就是，既然位置被占了，那就另外再找个位置不就得了，怎么找其他的位置呢？这里其实也有很多的实现，我们说个最基本的就是既然当前位置被占用了，我们就看看该位置的后一个位置是否可用，也就是1的位置被占用了，我们就看看2的位置，如果没有被占用，那就放到这里呗，当然，也有可能2的位置也被占用了，那咱就继续往下找，看看3的位置，一次类推，直到找到空位置。
对了，JAVA中的ThreadLocal就是利用了开放寻址法。
小白：啥是ThreadLocal啊
庆哥：咋滴，你不知道啊，没事，给你一篇文章，看了包装你再也不学ThreadLocal了，因为看完这篇，你就再也忘不掉啦，链接直达，走起：再也不学ThreadLocal了，看这一篇就忘不掉了！（万字总结）
小白：嗯嗯，我会好好看看的。那什么是拉链法啊？
庆哥：拉链法也是比较常用的，像之前你说的HashMap就是使用了这种方法，那这个方法是怎么个回事呢？我们继续来看图：

文章插图

之前说的开放寻址法采用的方式是在数组上另外找个新位置，而拉链法则不同，还是在该位置，可是，该位置被占用了咋整，总不能打一架，谁赢是谁的吧，当然不是这样，这里采用的是链表，什么意思呢？就像图中所示，现在张三和李四都要放在1找个位置上，但是张三先来的，已经占了这个位置，待在了这个位置上了，那李四呢？解决办法就是链表，这时候这个1的位置存放的不单单是之前的那个Entry了，此时的Entry还额外的保存了一个next指针，这个指针指向数组外的另外一个位置，将李四安排在这里，然后张三那个Entry中的next指针就指向李四的这个位置，也就是保存的这个位置的内存地址，如果还有冲突，那就把又冲突的那个Entry放在一个新位置上，然后李四的Entry中的next指向它，这样就形成了一个链表。