源码阅读——HashMap

讲解之前，先测试下你对hashMap的理解

1：说说HashMap 底层数据结构是怎样的？

2：谈一下HashMap的特性？

3：使用HashMap时，当两个对象的 hashCode 相同怎么办？

4：HashMap 的哈希函数怎么设计的吗？

5：HashMap遍历方法有几种？

6：为什么采用 hashcode 的高 16 位和低 16 位异或能降低 hash 碰撞？hash 函数能不能直接用 key 的 hashcode？

7：解决hash冲突的有几种方法？

8：为什么要用异或运算符？

9.：HashMap 的 table 的容量如何确定？

10：请解释一下HashMap的参数loadFactor，它的作用是什么

11：说说HashMap中put方法的过程

12：当链表长度 >= 8时，为什么要将链表转换成红黑树？

13：new HashMap(18);此时HashMap初始容量为多少？

14：说说resize扩容的过程

15：说说hashMap中get是如何实现的？

16：拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

17：说说你对红黑树的了解

18：JDK8中对HashMap做了哪些改变？

19：HashMap 中的 key 我们可以使用任何类作为 key 吗？

20：HashMap 的长度为什么是 2 的 N 次方呢？

21：HashMap，LinkedHashMap，TreeMap 有什么区别？

22：说说什么是 fail-fast？

23：HashMap 和 HashTable 有什么区别？

24：HashMap 是线程安全的吗？

25：如何规避 HashMap 的线程不安全？

26：HashMap 和 ConcurrentHashMap 的区别？

27：为什么 ConcurrentHashMap 比 HashTable 效率要高？

28：说说 ConcurrentHashMap中 锁机制

29：在 JDK 1.8 中，ConcurrentHashMap 为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

30：能对ConcurrentHashMap 做个简单介绍吗？

31：熟悉ConcurrentHashMap 的并发度吗？

no bb , show code;

先看1.6的代码，1.7和这个差不多，都是头插法，代码上有点小优化，影响不大

> since jdk1.6
 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        // 调用此方法进行数据存储
        addEntry(hash, key, value, i);
        return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        // threshold 在hashmap构造函数里面199行  threshold = (int)(capacity * loadFactor); 这货等于数组长度默认16*075的负载因子
        if (size++ >= threshold)
            // 考点：扩容是2倍扩容
            resize(2 * table.length);
    }

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        //new一个新数组进行扩容，新数组大小是上面传进来的2倍旧数组
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

    // 很详细的扩容注释，看不懂就没办法了
    void transfer(Entry[] newTable) {
        //原始数组赋值给新数组，用于遍历循环
        Entry[] src = table;
        //获取新数组的长度，用于计算下标
        int newCapacity = newTable.length;
        //遍历旧数组，用于获取每个e给新数组赋值
        for (int j = 0; j < src.length; j++) {
            //获取当前e
            Entry<K,V> e = src[j];
            if (e != null) {
                //处理过的e会在旧数组清空，上面一句判空控制空的无法进入
                src[j] = null;
                do {
                    //获取链表上的下一个next:e;用于while循环处理，依次处理链表上每个节点
                    Entry<K,V> next = e.next;
                    //进行下标计算，第二个参数是新数组长度
                    int i = indexFor(e.hash, newCapacity);
                    //头插法，旧数组的e放进新数组前，需要将e的 next指向新数组的e1；不然链表就断了，
                    e.next = newTable[i];
                    //当前的e复制给新数组，完成转换
                    newTable[i] = e;
                    //将Entry<K,V> next = e.next;  暂存的next赋给e，用于下一次遍历时e
                    e = next;
                } while (e != null);
            }
        }
    }

在看1.8的代码

数据结构，侵删.jpg

//这个代码是hashMap构造函数，传入的大小不是2的幂次方，就行修正，最终肯定是2的幂次方
 static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
//看下1.8的数据结构
//HashMap 293行定义的Node结构，这货就是链表无疑了，看代码，是单向链表哦，只有next
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

//1814行，这个就是红黑树的结构定义
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

 /**
   * The table, initialized on first use, and resized as
   * necessary. When allocated, length is always a power of two.
   * (We also tolerate length zero in some operations to allow
   * bootstrapping mechanics that are currently not needed.)
   */
//HashMap里面的数组
transient Node<K,V>[] table;

*******************通过以上结构说明1.8里面是数组+红黑树+单向链表*******************
            *******************下面开始正式分析*******************
//这儿是入口，先看下hash方法
 public V put(K key, V value) {
        //这方法可以看看：hash（）
        return putVal(hash(key), key, value, false, true);
    }

 //这儿接受参数类型是object，说明会自动装箱
 static final int hash(Object key) {
        int h;
        // integer类型的hashcode都是他自身的值，即h=key
        // h >>> 16为无符号右移16位，低位挤走，高位补0；^ 为按位异或，即转成二进制后，相异为1，相同为0，由此可发现，当传入的值小于  2的16次方-1 时，调用这个方法返回的值，!!!都是自身的值!!!
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

//onlyIfAbsent是true的话，覆盖key时不要改变现有的值;  evict为true的话，留给子类，如linkedHashMap的扩展方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //tab为空，初始化没有放入值的情况
        if ((tab = table) == null || (n = tab.length) == 0)
            //初始化数组，并获取扩容后的长度
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            //说明当前数组上面是没有存值的，没有任何node，直接new一个放进去
            tab[i] = newNode(hash, key, value, null);
        else {
            //不为空，说明坑已经有人了，说明需要放进当前数组位置的链表或者红黑树后面了
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //需要放入的元素的key一样，先临时变量暂存下， 677行进行覆盖替换
                e = p;
            else if (p instanceof TreeNode)
                //说明当前节点已经是红黑树了
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                //不是红黑树，都能走到这个逻辑，那肯定是链表，所以遍历链表，为啥链表慢就体现出来了，最坏时间复杂度O(n)
                for (int binCount = 0; ; ++binCount) {
                    //这个判断可以看出来是放到末尾的，尾插法，和上文分析的1.6头插法不一样
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //把新节点放到末尾后，进行了是否需要转红黑树的判断，看清楚条件，大于等于7开始转？不是的，方法里面还有个条件哦
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           //链表转红黑树了，treeifyBin方法里面还要判断数组的长度，小于64 是不会转红黑树的，只是扩容
                            treeifyBin(tab, hash);
                        break;
                    }
                    //遍历链表过程中，任一一个节点的key和要存储的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;
                // 如果入参onlyIfAbsent为false,将laovalue值覆盖掉
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //每次put后都会判断集合的大小是否大于负载因子，大于就扩容
        if (++size > threshold)
            resize();
        //留给子类，如linkedHashMap的扩展方法
        afterNodeInsertion(evict);
        return null;
    }

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //通过向左位移1位将数组的大小*2
            //同时扩容的标准12也需要变成24，也就是oldThr<<1
            //这里采用位移也是因为效率高
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //初始化走的这儿，明显可以看出初始大小默认16；满12开始扩容
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //正儿八经的数组创建
        //为啥这儿new，说明构造函数只是申明大小，负载因子等，真实的数组创建是put才做的哦???还有红黑树和compute方法
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //数组索引下标下面没有元素
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //数组索引下标下面有元素，且元素类型为红黑树
                    else if (e instanceof TreeNode)
                        //这里面迁移到新集合后，如果元素个数少于6个，红黑树会转换为链表
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //数组索引下标下面有元素，且元素类型为链表
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

如果要看concurrentHashMap，往这儿跳《源码阅读——ConcurrentHashMap》

附：开头问题的答案：
《HashMap的31连环炮，我倒在第5个上》