Jdk1.7HashMap源码分析

上一篇 <<<数组拷贝的几种方式及和链表结构的对比
下一篇 >>>

---

JDK1.7的HashMap的底层结构：是由数组+链表构成的。

Entry链表：解决hash冲突，不同的key映射到了数组的同一索引处，则形成链表。
使用单向链表原因：链表的插入和删除操作速度很快。

Entry对象的作用

充当链表的作用，里面包含了key、value、hash和next节点信息，有next关联链表的先后顺序。

核心源码部分的分析

1. HashMap只允许一个为null的key。
2. HashMap的扩容：当前table数组的两倍
3. HashMap实际能存储的元素个数： capacity * loadFactor
4. HashMap在扩容的时候，会重新计算hash值，并对hash的位置进行重新排列， 因此，为了效率，尽量给HashMap指定合适的容量，避免多次扩容.

put()方法

如果添加的key值为null，那么将该键值对添加到数组索引为0的链表中，不一定是链表的首节点。
如果添加的key不为null，则根据key计算数组索引的位置：
数组索引处存在链表，则遍历该链表，如果发现key已经存在，那么将新的value值替换旧的value值
数组索引处不存在链表，将该key-value添加到此处，成为头节点。

put方法：
 1、初始化数组大小16，计算阈值16*0.75=12
 2、key:null的值存放在数组的第0下标，但第0个下标也可能会存放其他值
 3、计算key的hash值
 4、根据hash计算key所在的下标值
 5、如果下标值对应的链表中，存在key的hashcode和equals方法与当前的key都一致，则执行刷新的操作
 6、下标值不存在，或key值在链表中不存在，则执行添加Entry操作

put顺序：A、B、C，如果key的hash值一致，则链表中的顺序：(C)->next(B)->next(A)

get()方法

1. 如果key为null，那么在数组索引table[0]处的链表中遍历查找key为null的value
2. 如果key不为null，根据key找到数组索引位置处的链表，遍历查找key的value，找到返回value，若没找到则返回null

HashMap根据key查询键值对，在没有冲突的情况下时间复杂度为O(1).
在hashMap产生key冲突的情况下时间复杂度为O(n)。在JDK1.8的链表长度大于8且数组总长度大于64的情况下会转换为红黑树，时间复杂度变为Log(n)

HashMap7如何计算HashCode

int hash(Object k) {
    int h = 0;
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

如何理解HashCode碰撞问题

对象值可能不等，但hashcode可能相等，这种冲突就是hash碰撞的问题。
使用链表组装，加上equals一起判断即可解决HashCode碰撞问题。

HashMap为什么不用双向链表

因为单向的就够用了，而且双向也是需要维护的

HashMap中的链表和LinkedList中的链表有何区别

1、HashMap是单向链表，LinkedList是双向链表

//LinkedList节点信息
Node(Node<E> prev, E element, Node<E> next) {
   this.item = element;
   this.next = next;
   this.prev = prev;
}

//HashMap中的节点信息
Entry(int h, K k, V v, Entry<K,V> n) {
   key = k;
   hash = h;
   value = v;
   next = n;
}

2、其他

HashMap中存放的是节点数组，Entry<K,V>[] table，扩容有阈值
LinkedList只有节点信息，不存在扩容情况