转载

面试中的HashMap、Hashtable和ConcurrentHashMap，你知道多少？

前言

学过数据结构的读者们想必其实也都学过HashMap，面试官问你的时候，想来你都是很清楚的知道HashMap是怎样的一个构成？确实很简单，就是数组加链表嘛。那再问你Hashtable和HashMap的区别是什么？脑子也不用想，又能出来一个答案 线程安全和线程不安全 ,Hashtable不允许存在空值呗。那继续往深处问，HashMap是怎么做性能优化的？这个时候你是怎么样的反应呢？如果知道红黑树，那就能答出来；不知道的话那不是就凉了，因为这个时候连ConcurrentHashMap都需要放弃回答了！！！

部分图片引自JDK1.7 HashMap 导致循环链表

HashMap源码导读

其实思路大致都是相同的，所以这里只分析一个HashMap，先贴出他的几个常见用法。

HashMap hashMap = new HashMap();
hashMap.put(key, value);
hashMap.get(key);

主要从这个方面对HashMap的整个工作流程进行分析。

HashMap()

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 对数组的一个保护，不能超过int最大值范围
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

其实在无参构造方法，我们并没有看到所谓的数组的初始化，他只对我们的负载因子做了一个初始化，也就是我们一直常说的 0.75f ,但为什么是 0.75f 呢，只能说是一个经验值，也就是经验所致，因为 0.5f 时空间太浪费， 1f 时容易出现极端情况，当然也不是随便定的，设计师肯定是做了很多的测试的，但依旧是一个经验值，或者说是测试后的最优解。

回到我们之前的问题，既然我们学习的时候学到过HashMap是一个数组+链表。 那做第一个思考为什么初始化不见了？ 先带着这样的问题继续啊往下走。

先看看自己动手初始化容量构造函数，最后都会调用下方的 tableSizeFor() 方法。

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;
    }

本质意思就是把数值变成2的指数倍，这样的好处是计算方便处理。但是出现同样的问题，没有初始化，这里也只看到了容量。问题继续保留。

put(key, value)

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true); // 1
    }
// 由注释1直接调用的方法putVal()
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是一个空，因为在构造函数中，我们并没有看到他的初始化，那么必然要调用resize()方法。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; // 2，未能初始化而必然调用的方法
        if ((p = tab[i = (n - 1) & hash]) == null)
            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))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((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;
                    }
                    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(); // 2
        afterNodeInsertion(evict);
        return null;
    }
// 由注释2直接调用的方法
// 由多种方法调用到这里：
// 1. 尚未初始化
// 2. 保存的数据超出 容量 * 负载因子
// 3. 数据被删的不足以支持树形的时候
final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        // 。。。。
        // 此处对容量大小做了一系列的判定，为定义初始化容量为16
        // 。。。。
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        // 进行了整个的table进行一个初始化
        // 而这个table就是一个Node的数组
        // Node也就是链表的一个个节点，读者自己点进去观察就能看到next节点
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 。。。。。
    }

到这里我们就已经明白了，原来初始化的过程已经在这里进行了定义，这也就解决了我们的第一个问题了。 但是随之而来第二个问题，为什么要这样设计呢？ 这里给出我思考的一个答案，如果只创建了，却没有进行使用呢？那至少就会占去16个数据类型大小的内存，而这样的创建方法，就是对内存的一种保护机制。

第三个问题，为什么要转变成树形（当然它是有好听的名字的，叫做红黑树）？其实结构的转换为的不外乎几种原因效率问题、空间占用问题。如果使用链表查询，他的查询速度是 O(n) ，而红黑树的查询速度是 O(logn) 。但是红黑树带来的问题确实一个存储容量的问题，作为二叉树，他需要同时保存左右节点，而单链表只有一个节点，那么内存消耗的问题就出来了。树的构造问题能讲一篇博客，所以就不再这里讲先了。

get(key)

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

通过hash值来寻找我们对应的节点，那我们就需要先来看看这个hash是怎么计算的。

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

答案也是一目了然的，获得hashCode()值，然后低16位进行与高16位的异或运算。其实就是为了算出另一种样貌的hash值。 但是我们为什么要这么做呢？稍后给出一个解答。

那我们获得了hash值以后，就需要来找找我们的节点了。