集合详解-HashMap

我们为什么需要剖析HashMap集合类?

• HashMap和HashTable有什么区别?
• HashMap中默认的初始化容量和加载因子是多少?如果加载因子设置的太小会出现什么问题?如果设置的太大或出现什么问题?
• HashMap中保存的元素是否可以包含null?保存的元素是否有序?
• HashMap是否是线程安全的?如果多线程操作HashMap会出现什么问题?

HashMap的主要结构

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

丛上图可以看出HashMap继承了AbstractMap类、实现了Map接口、Cloneable接口以及Serializable序列化接口。

• Map ：定义了集合类最基础的功能，包括size()、isEmpty()、get()、put()、containsKey()、containsValue()方法。
• AbstractMap：实现了一些比较基本的方法，但是通过查看HashMap类发现AbstractMap中的方法在HashMap都实现了重写。暂不清楚这个抽象类的作用在此。
• Cloneable：我们都知道实现Cloneable的接口都可以使用clone方法实现深复制或浅复制，但HashMap有点不一样，它可以被称为浅复制，但又不是笼统意义的浅复制，为什么这么说，等我们分析到clone方法的时候再做详细的解释。
• Serializable：不需要说，表示可序列化和反序列化。

HashMap中主要的属性和方法：

属性

默认的属性

//HashMap中默认初始化的数组table大小（16）.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//HashMap中数组table最大的允许值.
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子，不建议修改此值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表大小满足或超过该值时升级为红黑树，实际上table数组大小要满足MIN_TREEIFY_CAPACITY的大小才会升级为红黑树，否则只是扩容
static final int TREEIFY_THRESHOLD = 8;
//红黑树大小满足或小于该值时退化为链表
static final int UNTREEIFY_THRESHOLD = 6;
//链表升级为红黑树table数组的大小，如果小于该值，则选择的是扩容而不是树化
static final int MIN_TREEIFY_CAPACITY = 64;

普通属性

// HashMap是由数组+链表+红黑树组成，这个便是HashMap中数组，如果HashMap中的元素能够均匀的分布在数组table上,则这个HashMap是非常高效的.  
transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

// HashMap中所包含的元素个数
transient int size;

// HashMap操作修改的次数，这个是实现fail-fast快速失败机制的主要属性.
transient int modCount;

/**
* HashMap中元素个数是否超过阈值，如果超过该值则需要重新扩容HashMap的数组table大小。
* threshold的取值方式为: threshold= loadFactor * cap.
* cap的值为实际的数组table的大小.
*/
int threshold;

/**
* 加载因子，用于计算threshold的大小
* 如果该值太大，则会造成HashMap中元素已经非常多，但却满足不了扩容机制，导致查询速度变慢.
* 如果该值设置太小，则会造成HashMap在新增了一小部分元素之后，就选择扩容，从而导致操作速度变慢以及空间的浪费。
* 默认的加载因子0.75是经过很多次验证比较好的一个值，因此不建议修改此值。
* /
final float loadFactor;

注意：

1. 链表的大小不是超过默认的树化大小(8)就一定会树化，还需要满足数组table大小超过最小的数组树化大小(64)，只有这两个值满足时，才会升级为红黑树，否则只是扩容数组table的大小。

2. 加载的因子(loadFactor)的值不要轻易修改，若设置太大会造成查询速度的变慢；若设置的太小则会造成空间浪费以及多次扩容。

方法

构造方法

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

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

public HashMap(int initialCapacity, float loadFactor) {
    //若客户自定义的初始化容量太小，则会造成抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    //若定义的初始化容量大于默认最大的数组容量，则将初始化容量赋值为最大的容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //若加载因子小于0或者不是有效的数字，则会抛出异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    //计算HashMap的阈值
    this.threshold = tableSizeFor(initialCapacity);
}

    上边的代码就是初始化HashMap的方法，其它的都很简单，但是我不知道大家有没有发现问题?

• 传入了初始化的容量，为什么没有初始化HashMaptable的数组table大小?
• 之前说过threshold的取值(threshold=loadFactor*cap),但是这里已经传入了cap和loadFactor，为什么不直接计算呢?

当时也是一脸懵逼，但是看了之后的代码和搜索资料才明白，代码的作者是真的牛逼啊，分分钟给跪下的节奏。那么到底牛逼在什么地方，我们就先分析下tableSizeFor(initialCapacity)这个方法……

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

    初看这个方法觉得好头大，这到底是要干什么，一堆的右移位补0和异或操作，到底是需要实现什么？ 经过查资料发现，这段代码的主要目的是获取大于输入参数(cap)且小于最接近2的n次方幂的值返回，例如输入的是10，返回的是16。感觉有点高大上啊，对于一些运算，进行位移操作，从而加快运行的速度，当然这个还不是牛逼的地方，只能算开胃菜，为后边牛逼的地方打基础，我们继续学习后边比较牛逼的代码……

普通方法

• put(K key, V value)：插入元素

key, V value)：插入方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

    /**
    * Implements Map.put and related methods
    *
    * @param    hash           key的hash值
    * @param    key            键
    * @param    value          值
    * @param    onlyIfAbsent   是否改变已存在键的值
    * @param    evict          未知
    * @return 返回存在键的旧值或者null
    */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断数组是否初始化，若未初始化，先调用resize()方法进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据key的hash值和数组大小取余，计算数组下标上是否含有元素，若不存在元素则创建Node
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //判断传入键的hash值和已存在的hash值是否相等，若想等，则获取旧的元素
        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;
            }
        }
        //判断HashMap中是否存在相等的元素，如果存在相等的元素并且允许更换值，则使用新value替换旧value
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //这个方法在HashMap中没有实现，但是在LinkedHashMap做了相应的实现，用于实现HashMap中的元素根据操作实现顺序性。
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //增加修改次数，快速失败机制的实现方式
    ++modCount;
    //如果HashMap中的元素数量超过阈值，则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

    上述代码是插入元素的整体逻辑，包括数组的初始化、替换旧的值、添加新元素到数组/链表/红黑树、树化、扩容等。我们知道在初始化HashMap时并没有初始化数组table，那么在第一次进入插入元素时，肯定会执行resize()方法，我们看看resize()方法做了什么操作。

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;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //如果原有的HashMap阈值大于0(该情况针对于初始化HashMap时传入了数组初始化大小)，则将阈值赋值给数组初始化大小，
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
        //该情况针对于初始化HashMap时未传参数的情况。数组的初始化大小为默认的数组大小，阈值=默认的数组大小*默认的加载因子
        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"})
    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;   //帮助GC
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((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;
}

上边的代码比较长，但是别着急，我们一步步来进行分析。

• 首先看第一个if (oldCap > 0)判断，如果满足该条件说明HashMap中的数组table已经进行初始化过了，此时的HashMap中元素的数量超过了threshold的值，需要对table数组的大小进行扩容。扩容分为两种情况：

  • 如果旧的数组大小已经大于或等于默认最大数组的大小，则将threshold置为Integer的允许的最大值，这里主要为了将阈值调到最大，防止马上新增一个元素之后又来进行扩容。
  • 若不满足上述条件，则将旧数组的大小*2赋值给新的数组。如果新数组大小小于默认的最大的数组大小并且新数组大小大于默认的数组大小，则调整阈值为新数组的大小。
    从上述代码可以看到HashMap的数组扩容一般为原来大小的2倍。

• 第二个else if(oldThr > 0)判断，若满足该条件说明，table数组还没有初始化过以及在初始化HashMap实例时是带有参数的。这里的oldThr应该是之前所说的tableSizeFor()的值。这里做法也比较简单，就是将阈值赋值给新数组的大小。

• 进入else判断，新数组的大小取默认的数组大小(16),阈值则是上述所说的(loadFactor*defaultCapity).

• 又是if(newThr == 0): 这个判断我没有想到什么情况会出现这种问题，这个之后在查找查找资料？

• 之前都是进行HashMap扩容的操作，扩容操作之后我们需要将之前存在的元素重新分布到新的数组上，具体的转移逻辑如下，这也是之前所说代码真正牛逼的地方。

  • 如果table数组下标所对应的元素为null，则跳过

  • 如果table数组下标所对应的元素只有一个，不是链表或者红黑树，则根据hash值和新数组大小计算新的下标进行转移。

  • 如果table数组下表所对应的元素是树节点时，暂不做分析。

  • 不满足上述条件时，则表明该下标对应的是个链表，遍历链表上的每一个元素，然后进行转移到新数组上。在我想法中，我可以像插入元素时候一样，根据元素的hash值和新数组大小取余获得元素新下标位置进行转移，但是我发现代码不是如此，这便是HashMap代码的牛逼之处……

    假设旧的数组大小为16(二进制为00010000，减1二进制为00001111),
    新的数组大小为32(二进制为00100000，减1二进制为00011111),
    有两个元素hash值为5(00000101)和21(00010101)，在旧的数组上下标为5和5,
    在新数组时元素5的下标位置为00000101和00011111逻辑与为00000101(值为5)，元素21新的下标位置为00010101(值为21)。

    多试几个数据发现，只需要看原来的hash值新增的那个bit是1还是0就好了，(即看上述的从右往左数第5位是否为0), 是0的话该元素的数组索引就没有变，是1的话就说明该元素的索引位置是”旧的下标”+oldCap的值。

  • 通过上述的操作，可以将下标对应的链表元素均匀的分布到新的数组中，要么在原位置，要么在旧的下标+oldCap的位置中，这样整个旧的数组遍历下来就可以均匀到分布到整个新的数组中。

  • 最后返回新的数组。
    注意：虽然本章没有分析1.7的源码，但是还是做一下对比：
    1: 相对于1.7来说，1.8的HashMap不需要重新计算hash，
    2: 相对于1.7来说，1.8的HashMap采用尾插法的方式，有效的避免了并发死锁的问题。

分析完了HashMap的插入元素的方法，我先做个小小的总结：

1. HashMap是在第一次插入元素的时候进行的初始化，初始化的操作具体分为三种情况：
   • 没有传入初始容量: 取默认的数组大小和加载因子，阈值threshold=loadFactor*initCap；
   • 传入初始容量，未传加载因子：阈值取大于并最接近传入的初始容量2的n次方的值，数组大小取阈值；
   • 传入初始容量以及加载因子：和上述一致
2. HashMap扩容的大小一般是旧数组大小的2倍
3. HashMap扩容转移元素时，采用的是尾插法的方式。
4. HashMap的扩容还是比较耗时的，因此我们应该一开始就设置好我们的初始容量，例如我们需要存入1000个元素，我们可以设置new HashMap(1000)来设置，HashMap内部实际为new HashMap(1024)，但是事实上这也不是最合适的大小，因为我们知道当HashMap中的元素超过1024*0.75的时候，即大约768时，就会扩容，因此我们最开始设置大小应为超过1024，设置为2048。

• get(K key):获取元素

key)

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

/**
* @param    hash        键的Hash码
* @param    key         键
* @return   Node        返回元素Node
*/
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //判断table数组是否为空并且数组的大小大于0，然后判断与hash值逻辑与的下标是否含有元素，若元素不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //判断数组上的元素是否和传入的hash值相等，相等的话继续判断地址是否相等或者两个键equals,满足以上条件的则返回数组上的元素。
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //不满足数组的元素上相等时，则判断该元素是否是树节点，如果是树节点，则查找树。   
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //遍历链表，查看链表上是否存在相等的元素。
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

上边的代码非常的简单，获取HashMap中键对应的值时，主要也是根据hash值和键值来获取。具体的逻辑如下：

• a.首先判断数组大小是否为空，若为空则返回空。
• b.根据键的hash值获取所在数组上的下标，如果该索引上元素为空，则返回空。
• c.判断该索引上的元素的hash值是否相等，若想等继续判断键的地址是否相等或两个键的值是否相等，若想等，则返回该元素Node，否则继续执行
• d.判断是否满足该数组索引上的元素是否是树节点，如果是树节点，则查找树，这个就不在此分析，可以通过前序遍历、中序遍历、后序遍历来查找。
• e.当不满足上述条件时，这说明该数组索引上的是链表结构，需要遍历链表的元素然后判断，满足之后进行返回该元素。

clone():复制方法

public Object clone() {
    HashMap<K,V> result;
    try {
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
    result.reinitialize();
    result.putMapEntries(this, false);
    return result;
}
void reinitialize() {
    table = null;
    entrySet = null;
    keySet = null;
    values = null;
    modCount = 0;
    threshold = 0;
    size = 0;
}

      在开篇的时候说过HashMap的复制不能称之为严谨的深复制或者浅复制，为什么会这么说，我们先说明下深复制和浅复制的原理：深复制和浅复制都可以将一个对象的属性拷贝到另一个相同类型的对象中去，不同的是深复制会将对象中属性是对象或是数组的也重新复制一份；而浅复制只是复制了相同类型的对象，里边的属性也是引用之前原对象中属性的地址。
      了解了深复制和浅复制，我们再看下上边的代码。首先通过获取通过调用Object类的clone()方法实现浅复制，然后将新对象中的table数组引用、entrySet等属性值为空，继续通过调用插入集合的方法将原有HashMap中保存的元素插入到新对象中。
      为什么要这样做？我理解的是这样子做可以满足像原有的HashMap中插入新元素的时候，不会影响复制出来的对象。同理，像新对象插入元素的时候，不会影响原有对象。但是为什么说这样子还不是深复制，因为如果修改了HashMap存储元素的内容，两个对象都会发生改变，所以不是严谨的深复制和浅复制。

面试提问

1. HashMap是线程安全的吗？多线程操作时会出现什么问题？
   答：不是线程安全的。多线程插入元素的时候，可能会导致数据丢失。
2. HashMap默认的初始数组大小是多少？默认的加载因子是多少？设置大了和设置小了会有什么问题？
   答：数组默认是16，加载因子时0.75。若设置过大会造成对空间的利用更充分，但造成查询的效率较低;若设置过小的话，会造成插入一小部分元素就需要扩容，从而导致空间的浪费。
3. HashMap是在什么时候初始化的？一般扩容的大小是多少？
   答：在第一次插入元素的时候进行初始化。初始化会根据是否传入了初始容量而有不同的初始化逻辑。一般扩容的大小是原有的2倍。
4. HashMap为什么要求我们存储的元素需要实现hash()和equals方法？
   答：HashMap是通过hash值的比较来获取元素在数组上的位置，如果元素的hash值越不重复则在散列表中分散的越好，越均匀。
   • 如果两个元素的hash值相等， 则这两个元素不一定相等
   • 如果两个元素相等，则他们的hash值一定相等
   • 判断两个元素是否相等时，首先hash值是否相等，然后判断两个键是否相等，若想等则进行替换，若不相等则进行插入。
5. HashMap中使用hash值主要的目的是什么？
   答：加快获取元素下标的位置，判断元素是否相等，从而得到时间效率的提升。
6. 说一下HashMap插入元素和获取元素的逻辑？
   答：参考插入元素方法和获取元素方法的篇章。

总结

      这篇博客主要是写了一些关于HashMap常用的方法和经常会被问到的一些问题，当然许多方面都没有做分析，像获取树上的元素，怎么往红黑树中插入元素，以及树化等等，因为树相关的操作又是一个非常大的内容，之后会找个时间详细的学习下树和树的相关操作，包括树的查找、插入、二叉树的查找和插入、红黑树的查找和插入等等，敬请期待……
      最后，感谢各位的阅读，祝大家的技术节节高升……