HashMap源码学习笔记

发表于2018-06-13

Java中HashMap源码学习笔记。1.8 / 1.7 中设计思路比较

1
2
3
4
HashMap<String, String> map = new HashMap<>();
        map.put("key", "value");
        String v = map.get("key");
        System.out.println(v);

jdk1.7

1
2
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始桶容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子

  • 1.确定数组下标

    1
    2
    int hashCode = hash(key)
    int index = hashCode % table.length

  • 2.put hash冲突

    1
    2
    3
    对于每一个新的元素，首先放到链表头部块 (效率最快)
        --> 导致由于是单向链表所以上面的节点找不到
        -->解决办法 讲新的链表赋值给head头部(相当于整个链表下移)

  • 3.优化
    对于2的整次幂的任意数X ---> hashCode % X == hashCode & (X -1)

  • 4.扩容

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    扩容后的节点复制操作
        void transfer(Map.Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Map.Entry<k, v> e : table) {
                while (null != e) {
                    Map.Entry<k, v> next = e.next();
                    //计算扩容后的下标
                    int i = indexFor(e.hash, newCapacity);
                    //将整个e节点指向扩容后新的数组对应链表头节点
                    e.next = newTable[i];
                    //将新的链表下移
                    newTable[i] = e;
                    //e重新指向原始链表的下一个节点(准备进行下一次移动操作)
                    e = next;
                }
            }
        }

  • 扩容的问题

    1
    2
    3
    4
    5
    1.扩容后新链表的元素与之前链表元素位置颠倒
    2.多线程下扩容的并发死锁问题  是因为线程共享链表 并且扩容后链表倒置
    如何避免 
    - 1.使用CurrentHashMap 
    - 2.new HashMap(15,1) 指定已知容量和负载因子

  • 问题思考

  1. 为什么要找一个2的整次幂的数作为桶的容量
    1
    为了计算下标效率更高 位运算效率更高
  2. 计算hashCode时为什么要进行右移以及异或操作
    1
    2
    3
    4
    5
    6
    7
    例如：由于上面的思路中2的整次幂数-1 高位全部为0 低位全部为1
          15: 0000 1111
           &
           h: 0110 0111
           =  0000 0111
    只有低位参与了下标计算,hash碰撞的几率会会很大,导致hashMap链表高度过高,效率降低
    所以右移之后将高位移到低位 再进行异或运算,这样计算出来的下标值更均匀,hash碰撞几率更低
  3. HashMap中key可以为null吗
    1
    可以只有一个 key为null直接put
  4. 计算扩容后数组的大小
    1
    2
    3
    4
    设传入大小为L
        计算： L -1 | L >>> 1  L >>> 2  L >>> 4  L >>> 8  L >>> 16
        原理： 最高1位 依次右移得到以低位全为1的树 即 2的n次方 -1
        最终结果 + 1

jdk1.8

数组 + 链表 + 红黑树

  • hash计算 通过hashCode()的高16位异或低16位实现 更加散列

    1
    2
    3
    4
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

  • 两个变量

    1
    2
    3
    4
    // 当链表长度大于8时转为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    //当红黑树高度小于6转为链表
    static final int UNTREEIFY_THRESHOLD = 6;

    1.8 往链表插值时直接插入到链表的尾部（区别与1.7）因为反正需要遍历，而这样做可以避免链表死锁

  • 关键代码分析

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
                //当前数组位置没有元素，直接放入
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
            //当前数组位置已有元素
                HashMap.Node<K,V> e; K k;
                //key相同直接相当于更新
                if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                    // 如果当前数组位置是红黑树
                else if (p instanceof HashMap.TreeNode)
                    e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    for (int binCount = 0; ; ++binCount) {
                    当前链表节点为尾部节点  直接放到尾部
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        //当前节点不为空key相同 更新操作
                        if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            //判断当前长度是否大于阈值 进行扩容
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

1.8 扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
do {
                       next = e.next;
                       //为0不变为1则下标为结果加上oldLength
                       if ((e.hash & oldCap) == 0) {
                           if (loTail == null)
                               loHead = e;
                           else
                               loTail.next = e;
                           loTail = e;
                       }
                       else {
                           if (hiTail == null)
                               hiHead = e;
                           else
                               hiTail.next = e;
                           hiTail = e;
                       }
                   }

注意:
在1.8中扩容是的算法有所变化，之前的 hash & newTable.length -1 改为 (e.hash & oldCap) == 0

总结

JDK源码中确实有许多代码设计精致的地方值得我们取挖掘学习. coding…