目录

前言

存储陈二

存储张三（出现冲突）

存储李四、王五

存储monkey（出现冲突）

小结

---

前言

上一篇文章我们讲了，如何使用哈希算法、数组存储等

这篇文章，我们将介绍陈二以及其他值如何存储、hashmap是如何使用链表的等等

存储陈二

好，那么我们已经存了刘一，之后我们再去存陈二。它的存储位置为5，

我们可以知道数据结构，数组下标为5的位置，里面没有值，为空。OK，那我们就把陈二存储到这个上面。

存储张三（出现冲突）

那我们接着再去存张三，我们来看一下张三它的存储位置是什么？ 它的存储位置4，它的这个hash值是774889

OK，那我们现在来这里来看，那我们把这个张三这个节点呢？把它画出来，但是我们去存张三的时候。

发现它的下标等于4，那这个时候同学们我们可以发现什么？那此时此刻我们是不是出现了什么情况，

出现了我们这个冲突的问题吧，我们不一样的两个key，但是我们哈希出来这个值，都是下标等于4，那此时此刻应该怎么办？

那此时此刻就是出现哈希冲突，哈希冲突怎么去解决？是不是用链表来解决，OK，用链表。

那同学们，我们刚才在这里是不是存了两个值，一个是hash（哈希值），还有一个next，这个next其实就是链表的引用（c和c++叫指针），那怎么去存？

也就是说，我们这个张三呢，它会让这个刘一，让出这个位置来。然后怎么办呢？然后呢，我们张三，它为头节点。

OK，然后让我们这个张三的next去引用指向咱们这个刘一，大家应该能理解，能明白。

所以呢，我们张三这个next，存储的实际就是刘一的这个地址，这就是我们如何解决冲突的问题，也就是利用于我们链表的这个特性，

所以此时此刻在这个地方呢，它就已经不是数组了，而这两个节点，它们已经是咱们的链表。

OK，这里链表用黄色来进行标识。我们刚刚已经演示去如何去解决冲突了，那接下来我们再继续存下一个值。

存储李四、王五

李四的位置是多少？李四的位置是6，我们发现它目前为空，我们直接把李四的这个值呢，存储在我们这个6下面，

然后我们接着再去存王五，王五的位置是多少？王五的位置是0，OK，0的话，我们发现它也目前为空，

所以呢，它也可以直接去赋值下标等于0的这个位置。

、

存储monkey（出现冲突）

那我们接着再去存咱们这个monkey，我们来看monkey，我们算出这个值是多少，为4吧，那为4的话，

同学们，我们现在有点尴尬，为什么有点尴尬了？我现在在这里赋值一个值，我们这个值出现了什么情况？

我们这个下标等于4的已经有值了，也就是说我们这个monkey他又出现冲突了，那这个时候同学们，我们应该怎么办？

它这个哈希值它是个负数，我这里方便演示呢，就取8749，取后面四位8749，

刚才我们既然存张三的时候，发现有刘一，那我们就让这个张三的值，直接插到这个头部，

所以在我们的这个monkey这个值，出现冲突的时候，那我们现在这个monkey，也会让我们的这个张三呢，让出这块位置来。

然后呢，这个张三他也会让出这个位置来，然后呢，让我们的monkey占到这个位置，所以让我们的monkey指向咱们的这个张三，

然后我们的这个张张三呢，去指向我们的刘一，这就是怎么去存储的结构。

小结

那么我们现在呢？这6个元素通过我们的put的方法，通过哈希这个算法的实现，

那我们现在就可以把它存在我们的数组和这个链表上，这个地方非常非常的重要，

好，我们现在在这里呢，确实给大家讲的是1.7的，

待会给大家去讲1.8底层，是怎么去实现的，涉及到源码的分析等

包括头插法和尾插法，导致我们的CPU 100%这个问题怎么去解决啊？

OK，好，那刚才在这个地方是给大家去画图，一步一步给大家去梳理，把它的过程讲完了！