HashMap源码分析

HashMap

&运算0&0=0  1&1=1  其他有0为0

也是有扩容的情况

这个的原理是一个数组 然后其中的每个元素存放的都是链表。当一个添加一个hash值相同的节点时候最新的节点会放在数组中，其他的节点会往后移动。

链表的节点，可以很清楚的知道是一个单链表。

HashMap的创建，仅仅是定义了数组的默认的长度，并没有创建数组，是在put()中创建的数组。

 

hashMap的put方法，首先是在inflateTable中创建数组

然后通过计算hash值，并且通过hash值进行计算在数组中的索引值。判断当前的是数组的位置上是否为空，如果不为空，就进行遍历链表，进行计算当前的链表上的每个节点。如果hash值相同，并且key值相同，那么就将值进行替换。

如果没有找到相同的节点，那么就添加新的节点 调用addEntry()方法

在这里会判断当前的数组是否能满足要求否则就进行扩容

这个进行遍历数组，并且进行遍历数组中的每个节点，和链表上的每个节点，通过hash值重新计算这个节点应该在数组的哪个位置上。

最终通过createEntry()来创建节点，并且将原有的节点e传递过去,并将e放在新节点的next下面，然后将新的节点放在数组中。

 

 

那么get()方法就非常的简单了。

如果key= null ，那么也会遍历数组中下链表的节点key为null的节点，没有找到就返回了null

如果Key不为null，那么就进行遍历寻找，key值和hash值都相同的节点。

 

 

上面的代码是Android-25版本的源码，但是在26的源码上，虽然也是用的单链表，但是链表上最新的节点是放在链表的末尾，而不是在头部。并且使用的是红黑树的结构，但是没有发现有什么作用。