Java集合-HashMap

2020-05-04

HashMap：哈希表

JDK1.8

HashMap的定义

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

以键值对<K,V>方式存储
实现了Cloneable，支持clone()
实现了java.io.Serializable，支持序列化操作

一步一步对HashMap进行分析

HashMap的一些属性

/**
 * 默认的初始容量-必须为2的幂。
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 2^4=16

/**
 * 最大容量，如果两个构造函数都使用参数隐式指定了更高的值，则使用该容量。必须是2的幂 <= 1 << 30（2^30）。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认加载因子/负载因子。
 * 作为一般规则，默认负载因子（.75）在时间和空间成本之间提供了很好的折衷。 较高的值会减少空间开销，但会增加查找成本（在HashMap类的大多数操作中都得到体现，包括get和put。设置其初始容量时，应考虑映射中的预期条目数及其负载因子，以最大程度地减少重新哈希操作的数量。如果初始容量大于最大条目数除以负载因子，则不会发生任何哈希操作。
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 链表->红黑树的阈值。
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 红黑树->链表的阈值。
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 链表->红黑树的最小容量。当HashMap的容量<64时，先进行扩容而不是链表转成红黑树。至少为4*TREEIFY_THRESHOLD(即64)，以避免调整大小和树化阈值之间的冲突。
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * Node数组.
 */
transient Node<K,V>[] table;

/**
 * 保存缓存的entrySet()。注意，AbstractMap字段用于keySet()和values()。
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * HashMap的键值对的数量
 */
transient int size;

/**
 * 对该HashMap进行结构修改的次数结构修改是指更改HashMap中的映射次数或以其他方式修改其内部结构（例如重新哈希）的修改。此字段用于使HashMap的Collection-view上的迭代器快速失败。（请参见ConcurrentModificationException）。
 */
transient int modCount;

/**
 * 扩容阈值(capacity * load factor)=>容量*负载因子
 */
int threshold;

/**
 * 加载因子/负载因子
 */
final float loadFactor;

HashMap的静态内部类Node

/**
 * 基本的节点类。
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //节点的哈希值
    final K key;    
    V value;
    Node<K,V> next; //下一个节点的指针

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    //hashCode()方法
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    //equals()方法
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

HashMap的hash()方法

/**
 * 计算下标时，能够参与到计算的有效二进制位仅仅是右侧(低位)和数组长度值对应的那几位，意味着发生碰撞的几率会高。通过移位和异或运算让hashCode的高位(左侧)能够参与到寻址计算中。采用这种方式是为了在性能、实用性、分布质量上取得一个平衡。有很多hashCode算法都已经是分布合理的了，并且大量碰撞时，还可以通过树结构来解决查询性能问题。所以用了性能比较高的位运算来让高位参与到计算下标运算中，位运算效率更高。
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashMap的构造函数

/**
     * 指定初始容量和负载因子的有参构造
     * @param  initialCapacity 初始容量
     * @param  loadFactor      负载因子
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //初始容量是否<0
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //如果初始容量>最大容量，则设置为最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //判断负载因子是否合法
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        //调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 指定初始容量的有参构造，负载因子默认0.75
     * @param  initialCapacity 初始容量
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 无参构造，初始容量默认16，负载因子默认0.75
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

    /**
     * 使用与指定Map相同的映射构造一个新的HashMap。 使用默认的加载因子（0.75）和足以将映射保存在指定Map中的初始容量创建HashMap。
     * @param   m 映射map
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    /**
     * 对于指定容量，计算出最接近于指定容量的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;
    }

在有参构造中，this.threshold = tableSizeFor(initialCapacity)，为什么赋值给threshold？请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。

HashMap的putMapEntries()方法，在Map类型的有参构造中用到

/**
 * Implements Map.putAll and Map constructor.
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size(); //得到m的大小
    if (s > 0) {
        //判断table是否为空
        if (table == null) { // pre-size
            //计算HashMap的最小需求容量，并判断该容量是否>最大容量，若是，则使用最大容量
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            //如果该容量>threshold，则调用tableSizeFor()计算出该容量的最小的2的幂
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        //若table不为空，即HashMap中已经有了数据，判断Map的大小是否超过了HashMap的阈值(threshold)，若是，则扩容
        else if (s > threshold)
            resize();
        //遍历，调用putVal()进行存放
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

HashMap的resize()方法

/**
 * 初始化或增加table大小。 如果table为空，则根据threshold属性的值去初始化HashMap的容量。如果不为空，则进行扩容，因为我们使用2的次幂来给HashMap进行扩容，所以每个桶里的元素必须保持在原来的位置或在新的table中以2的次幂作为偏移量进行移动。
 */
final Node<K,V>[] resize() {
    //旧table
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  //获取旧table的长度
    int oldThr = threshold; //旧阈值
    int newCap, newThr = 0; //新容量、新阈值
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {   //判断旧容量是否>最大容量，若是，阈值设置为Integer最大值，并返回旧table
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新容量为旧容量的2倍且<最大容量且旧容量>=默认容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; //阈值设置为旧阈值的2倍
    }
    else if (oldThr > 0) //旧table为空，旧阈值>0，则新容量设置为旧阈值
        newCap = oldThr;
    else {  //旧table为空，旧阈值<=0，则新容量设置为默认容量，新阈值设置为默认负载因子*默认容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //经上面处理后，如果新阈值=0，则计算出新阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //将新阈值赋值给threshold，为新初始化的HashMap来使用
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //初始化一个长度为新容量大小的Node数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //给table重新赋值
    table = newTab;
    if (oldTab != null) {   //如果原来的HashMap中有值，则遍历
        //对旧table中的元素转移到新table中，链表中的Node转移到新table中时，位置可能保持不变或者位置变为<原位置+oldCap>，采用尾插法
        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)
                    ((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;
                        //根据hash&oldCap的结果的不同，决定元素在扩容时是放在原位还是放在位置移动oldCap的位置。
                        if ((e.hash & oldCap) == 0) {   //放原位
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {  //放原位+oldCap的位置
                            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) {   //高位，放原位+oldCap的位置
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap的putVal()方法

/**
     * Implements Map.put and related methods.
     * @param hash 
     * @param key 
     * @param value 
     * @param onlyIfAbsent 如果为true，请不要更改现有值
     * @param evict 如果为false，则表处于创建模式。
     * @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;
        //若HashMap为空，则调用resize()扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;    //得到扩容后的长度
        //若放置的位置没有Node，则初始化一个Node放置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //若放置的位置有Node
        else {
            Node<K,V> e; K k;
            //判断两个hash是否相同，并且两个key是否指向同一个内存空间，若是，则覆盖
            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;
                    }
                    //如果链表中存在键值对的key和我们要存入的键值对的key相同的Node，则跳出循环，此时e = p.next
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key //如果e不为空,此处的e为我们要存放value的键值对
                V oldValue = e.value;   //取出旧值
                //如果onlyIfAbsent为false或者oldValue为null则进行覆盖，默认onlyIfAbsent为false
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e); //这个为linkedHashMap中才有意义，HashMap为空方法
                return oldValue;    //返回旧值
            }
        }
        ++modCount; //结构化修改次数+1
        if (++size > threshold) //判断是否需要扩容
            resize();
        afterNodeInsertion(evict);  //这个为linkedHashMap中才有意义，HashMap为空方法
        return null;
    }

JDK1.7与JDK1.8

不同之处	JDK1.7	JDK1.8
存储结构	Entry类+数组+链表	Node类/TreeNode类+数组+链表/红黑树
hash的计算	较复杂，使用了9次扰动处理=4次位运算+5次异或	较简单，使用了2次扰动处理=1次位运算+1次异或
扩容时的元素转移	重新计算hash，不保证元素还在原位，效率低	只计算存放位置，放在原位置/原位置+oldCap
转移方式	头插法，逆序，链表死循环	尾插法，不逆序&&不死循环

有关HashMap的一些问题

为什么容量必须是2^n？

在计算数组下标时，对2^n-1操作时它的二进制全为1，然后用hash对2^n-1进行按位与操作能快速得出数组下标，并且分布均匀。

链表->红黑树的阈值为什么是8而不是20？为什么不是7？

链表中元素的个数符合泊松分布，有8个元素的概率非常低，因此选择了8。
防止链表<->红黑树（红黑树->链表的阈值为6）之间出现频繁转换，效率降低。

如何解决hash冲突？

好的hash算法：hashCode() + 扰动处理(位运算+异或)
扩容机制：>=阈值时进行扩容
数据结构：1.7中的数组 + 链表，1.8中的数组 + 链表/红黑树
数据存储机制：发生冲突时，1.7采用拉链法 + 头插法，1.8采用拉链法 + 尾插法 + 红黑树

HashMap具备下述特点：

键-值（key-value）都允许为空
线程不安全、不保证有序、存储位置随时间变化。

为什么HashMap中String、Integer这样的包装类适合作为key键

final类型，保证了key的不可改变
内部重写了hashCode()和equals()，有效减小碰撞。
HashMap中的key若Object类型，则需实现哪些方法？
hashCode()：减小碰撞
equals()：检查存储位置上是否存在需要存储数据的键key，若存在，替换value，否则插入新数据