理解HashMap（结合源码分析数据结构）

参考内容：

snailclimb.gitee.io/javaguide/#…

blog.csdn.net/zhouxcwork/…

HashMap

HashMap主要用来存放键值对，基于哈希表的Map接口实现，是常用的Java集合之一。

注意：

JDK1.8之前HashMap由数组+链表组成，即链表散列，数组为主体，链表主要为了解决Hash冲突存在；

JDK1.8之后HashMap的组成增加了红黑树，在满足下述两个条件之后会将链表结构转为红黑树，以此加快搜索速度；

链表转红黑树需要满足的两大条件：

1. 链表长度大于阈值（默认为8）
2. HashMap数组长度超过64

结合源码分析数据结构

HashMap使用哈希表存储键值对，创建了一个继承Map.Entry的静态内部类，每一个Node（Entry）对象表示存储在哈希表中的一个键值对。

HashMap数据结构源码如下：

static class Node<K,V> implements Map.Entry<K,V> {
    // key的hash值
    final int hash;
    // key对象
    final K key;
    // value对象
    V value;
    // 指向链表中下一个entry对象 null表示当前对象在链表底部
    Node<K,V> next;
    ...
}
复制代码

HashMap的扰动函数（即hash方法）：

static final int hash(Object key) {
    int h;
    // key.hashCode() 为key的散列值
    // ^ 按位异或 >>> 无符号右移
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
复制代码

HashMap的put方法：

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 判断当前元素存放的位置 n为数组长度（该运算表示取余）
    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))))
            // 插入元素与目标位置的元素的hash相等 key相同
            e = p;
        else if (p instanceof TreeNode)
            // key不同时 如果插入为树节点（红黑树），则直接插入结点
            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值是否相等 
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //  表示在桶中找到key值、hash值与插入元素相等的结点 覆盖操作
        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;
}
复制代码

链表转红黑树：

final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
    // HashMap数组长度超过64
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		resize();
	else if ((e = tab[index = (n - 1) & hash]) != null) {
		TreeNode<K,V> hd = null, tl = null;
		do {
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);
		if ((tab[index] = hd) != null)
			hd.treeify(tab);
	}
}
复制代码

深入阅读HashMap

HashMap的属性：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    // 序列号
    private static final long serialVersionUID = 362498820763181265L;
    // 默认的初始容量是16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大容量为2的30次方（容量大小必须为2的n次方）
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的填充因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 当桶(bucket)上的结点数大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    // 桶中结构转化为红黑树对应的table的最小大小
    static final int MIN_TREEIFY_CAPACITY = 64;
    // 存储元素的数组，总是2的幂次倍
    transient Node<k,v>[] table;
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    // 存放元素的个数，注意这个不等于数组的长度。
    transient int size;
    // 每次扩容和更改map结构的计数器
    transient int modCount;
    // 临界值 当实际大小(容量*填充因子) 超过临界值时，会进行扩容
    int threshold;
    // 加载因子
    final float loadFactor;
}
复制代码

loadFactor 加载因子

loadFactor为加载因子，用来控制数组存放数据的疏密程度。loadFactor趋近于1表示数组中entry越密集，趋近于1表示数组中entry越稀疏。loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

HashMap什么时候扩容？

Size>=threshold时扩容， threshold = capacity * loadFactor 临界值为数组长度*加载因子；例如HashMap默认的数组长度为16，加载因子为0.75，那么当数组长度>=12时需要考虑扩容。

HashTable与HashMap的区别

1. HashMap中K-V都允许为null，但要求key不重复为null（HashMap在实现时对null做了特殊处理，将null的hashCode值定为了0，从而将其存放在哈希表的第0个bucket中）；HashTable中K-V均不能为null；
2. HashMap采用数组+链表（红黑树）的数据结构，HashTable采用数组+链表的数据结构；
3. 出现Hash冲突时，如果链表节点数<8，HashMap会将新元素添加到链表末尾，而HashTable会将其添加到链表首位；
4. HashMap要求最大容量必须是2的n次方，HashTable的容量大小可为任意正整数；
5. HashMap中寻址方式为位运算与按位与，HashTable采用求余数；
6. HashMap无法保证线程安全，HashTable的get/put方法采用synchronized关键字进行方法同步；
7. HashMap默认容量为16，HashTable默认容量为11。

ConcurrentHashMap

ConcurrentHashMap数据结构为数组+链表（红黑树），锁的粒度为对每个数组元素（Node）加锁。

HashTable与ConcurrentHashMap的区别

• **Hashtable的任何操作都会把整个表锁住，是阻塞的。**好处是总能获取最实时的更新，比如说线程A调用putAll写入大量数据，期间线程B调用get，线程B就会被阻塞，直到线程A完成putAll，因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队，效率较低。

• **ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个表都锁住。同步读取操作则是完全非阻塞的。**好处是在保证合理的同步前提下，效率很高。坏处是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据，期间线程B调用get，则只能get到目前为止已经顺利插入的部分数据。

总结：ConcurrentHashMap不能完全取代HashTable，HashTable为强一致性，ConcurrentHashTable为弱一致性。ConcurrentHashMap适用于追求性能的场景，大多数线程都只做insert/delete操作，对读取数据的一致性要求较低。

注：建议补充HashMap的put方法的流程图加深印象