首页 > > 程序设计 > Java技术 >

HashMap (JDK1.8) 分析

2020-01-18 16:02:11来源：博客园阅读 ()

HashMap (JDK1.8) 分析

一、HashMap(JDK1.8)

1、基本知识、数据结构

（1）时间复杂度：用来衡量算法的运行时间。
　　参考：https://blog.csdn.net/qq_41523096/article/details/82142747

（2）数组：采用一段连续的存储空间来存储数据。查找方便，增删麻烦。

（3）链表：采用一段不连续的存储空间存储数据，每个数据中都存有指向下一条数据的指针。即 n 个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点。增删方便，查找麻烦，

（4）红黑树：一种自平衡的二叉查找树，时间复杂度 O(log n)。

（5）散列表、哈希表：结合数组与链表的优点。通过散列函数计算 key，并将其映射到散列表的某个位置（连续的存储空间）。对于相同的 hash 值（产生 hash 冲突），通常采用拉链法来解决。简单地讲，就是将 hash(key) 得到的结果作为数组的下标，若多个key 的 hash(key) 相同，那么在当前数组下标的位置建立一个链表来保存数据。

（6）HashMap：基于哈希表的 Map 接口的非同步实现（即线程不安全），提供所有可选的映射操作。底层采用数组 + 链表 + 红黑树的形式，允许 null 的 Key 以及 null 的 Value。不保证映射的顺序且不保证顺序恒久不变。

2、HashMap JDK1.8 底层数据结构

（1）采用数组 + 链表的形式。
　　HashMap 采用 Node 数组来存储 key-value 键值对，且数组中的每个 Node 实际上是一个单向的链表，内部存储下一个 Node 实体的指针。

transient Node<K,V>[] table;

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

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

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

（2）当前数组长度大于某个阈值（默认为 64），且链表长度大于某个阈值（默认为 8）时，链表会转为红黑树。

二、HashMap JDK1.8 源码分析

1、基本常量、成员变量

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

/**
* 最大数组容量, 默认为 2^30。
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 负载因子，默认为 0.75。
* 用于计算 HashMap 容量。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 树化的第一个条件：
* 链表转红黑树的阈值，默认为 8。
* 即链表长度大于等于 8 时，当前链表会转为红黑树进行存储。
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 红黑树转链表的阈值，默认为 6。
* 即红黑树节点小于等于 6 时，当前红黑树会转为链表进行存储。
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 树化的第二个条件：
* 树化最小容量，默认为 64。
* 当前数组长度大于等于 64 时，才可以进行 链表转红黑树。
*/
static final int MIN_TREEIFY_CAPACITY = 64

/**
* 数组，用于存储 Node<K, V> 链表
*/
transient Node<K,V>[] table;

/**
* 用于存储 Node<K, V> 的总个数
*/
transient int size;

/**
* 数组长度阈值，当超过该值后，会调整数组的长度。一般通过 capacity * load factor 计算
*/
int threshold;

/**
* 负载因子，用于计算阈值，默认为 0.75
*/
final float loadFactor;

/**
* 用于快速失败（fail-fast）机制，当对象结构被修改后会改变。
*/
transient int modCount;

2、核心构造方法

（1）源码：

/**
* 常用无参构造方法，以默认值构造 HashMap。
*/
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


/**
 * HashMap 核心构造方法，根据 初始化容量 以及 负载因子创建 HashMap.
 * @param  initialCapacity 初始化容量
 * @param  loadFactor      负载因子
 * @throws IllegalArgumentException 非法数据异常
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 如果初始化容量 小于 0 ，则会抛出 非法数据 异常
    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;
    
    // 若上述条件均成立，则保存 数组长度的阈值（2的整数次幂）。
    this.threshold = 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;
}

（2）分析：
　　上例的构造函数，根据初始化容量以及负载因子去创建 HashMap，没有去实例化 Node 数组，数组的实例化需要在 put 方法里实现。
　　数组长度阈值通过 tableSizeFor() 方法实现，能返回一个比给定容量大的且最小的 2 的次幂的数。比如 initialCapacity = 21， tableSizeFor() 返回的结果为 32。

3、hash(key)

　　用于计算 key 的 hash 值。
（1）源码：

/**
* 计算 key 的 hash 值的方法
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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

// 获取某个 key 所在位置时，通过 (table.length - 1) & hash(key) 去计算数组下标
table[(table.length - 1) & hash(key)]

（2）分析
　　采用高 16 位与低 16 位异或，然后再进行移位运算。主要是为了减少冲突。

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

(length - 1) & hash(key)

【举例：】
    假设某个值经过 hashCode 计算后为：
        1111 0101 1010 0101 1101 1110 0000 0000
    数组长度为 16，那么 length -1 = 15，如下：
        0000 0000 0000 0000 0000 0000 0000 1111
    此时进行 (length - 1) & hash(key) 操作后，
        1111 0101 1010 0101 1101 1110 0000 0000
        &
        0000 0000 0000 0000 0000 0000 0000 1111
        =
        0000 0000 0000 0000 0000 0000 0000 0000
    即只要 hashCode 计算出的值最后四位为0，得到的结果就一定为 0，此时冲突会大大提高。
    
    采用 高16位 与 低16位 异或，计算为：
        1111 0101 1010 0101 1101 1110 0000 0000
        ^
        0000 0000 0000 0000 1111 0101 1010 0101
        =
        1111 0101 1010 0101 0010 1011 1010 0101
     此时进行 (length - 1) & hash(key) 操作后，
         1111 0101 1010 0101 0010 1011 1010 0101
         &
         0000 0000 0000 0000 0000 0000 0000 1111
         =
         0000 0000 0000 0000 0000 0000 0000 0101
     此时计算出来的，是hashcode结果的后几位的值，这样就可以减少冲突的发生。

4、put、putVal

方法作用：
　　Step1：给 HashMap 的数组初始化。
　　Step2：定义链表转为红黑树的条件。
　　Step3：定义数据存储的动作（存储的方式：链表还是红黑树）。

（1）分析 put 过程
　　Step1：put 内部调用 putVal() 方法。
　　Step2：先判断数组是否为 null 或者长度为0，是的话，则调用 resize 方法给数组扩容。
　　Step3：对 key 进行 hash 并执行位运算（(length - 1) & hash(key)），得到数组下标。若不冲突，即当前数组位置不存在元素，直接在此处添加一个节点即可。
　　Step4：若冲突，即当前数组位置存在元素，则根据节点的情况进行判断。
　　　　如果恰好是第一个元素，则进行替换 value 的操作。
　　　　如果不是第一个元素，则判断是否为红黑树结构，是则添加一个树节点。
　　　　如果不是红黑树结构（即链表），则采用尾插法给链表插入一个节点，链表长度大于等于 8 时，将链表转为红黑树结构。
　　Step5：若 Node 长度大于阈值，还得重新 resize 扩容。

（2）源码：

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

// 插入数据的操作
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
* 真正的插入数据的方法。
* @param key 的 hash 值
* @param key
* @param value
* @param onlyIfAbsent为 true，插入数据若存在值时，不会进行修改操作
* @param evict if false, the table is in creation mode.
* @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;
    
    // 如果 Node 数组为 null 或者 长度为 0 时，即 Node 数组不存在，则调用 resize() 方法，重新获取一个调整大小后的 Node 数组。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        
    // 如果当前数组元素没有值，即不存在 哈希冲突的情况，直接添加一个 Node 进去（多线程时，此处可能导致线程不安全）。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 存在哈希冲突的情况下，需要找到 插入或修改 的节点的位置，然后再操作（插入或修改）
        Node<K,V> e; K k;
        
        // Step1:找到节点的位置1
        // 判断第一个节点 是不是我们需要找的，判断条件： 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) {
                // 第一个条件判断得知 第一个节点不是我们要的，所以可以直接从第二个节点开始（p.next），然后遍历得第三、四个节点。
                if ((e = p.next) == null) {
                    // 如果第二（三、四。。。）个节点没有值，直接添加一个 Node 即可，此时的 e 为 null。
                    p.next = newNode(hash, key, value, null);
                    
                    // 如果链表长度大于等于 8，则转为红黑树 ，并结束遍历操作
                    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;
            }
        }
        
        // 当 e 不为 null 时，对值进行修改，并将旧值返回
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 此处是 空实现，LinkedHashMap使用
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // 添加节点的后续操作
    // 修改次数加1
    ++modCount;
    
    // 当Node节点数 size 大于 阈值时，需要执行 resize 方法调整数组长度。
    if (++size > threshold)
        resize();
    // 此处是 空实现，LinkedHashMap使用
    afterNodeInsertion(evict);
    
    // 添加节点成功，返回 null
    return null;
}

5、resize

　　用于给数组扩容。
（1）resize 过程
　　Step1：计算新数组的阈值、新数组的长度。
　　Step2：给新数组复制。对于链表节点采用 e.hash & oldCap 去确定元素的位置，新位置只有两种可能（在原位置、或者在原位置的基础上增加旧数组长度）

【举例：】
    e.hash = 10 = 0000 1010,     oldCap = 16 = 0001 0000
则  e.hash & oldCap = 0000 0000 = 0

    e.hash = 18 = 0001 0010,     oldCap = 16 = 0001 0000
则  e.hash & oldCap = 0001 0000 = 16

当 e.hash & oldCap == 0 时，新位置为 原数据所在的位置。即 table[j]
当 e.hash & oldCap != 0 时，新位置为 原数据所在的位置 + 原数组的长度。即 table[j + oldCap]

（2）源码：

/**
* 给数组扩容
*/
final Node<K,V>[] resize() {
    // Step1：判断数组是否需要扩容，若需要则扩容
    // 记录原数组
    Node<K,V>[] oldTab = table;
    
    // 记录原数组长度，若为 null，则为 0， 否则为 数组的长度
    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;
        }
        // 若数组长度2倍扩容仍小于最大容量，则阈值加倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 原数组为null，若旧阈值大于0， 则数组长度为 阈值大小
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 原数组为 null，旧阈值小于等于0， 则数组长度、阈值均为默认值
    else {               // zero initial threshold signifies using defaults
        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 = newThr;
    
    // Step2:将原数组的数据复制到新数组中（重新计算元素新的位置）
    @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;
                // 如果原数组节点中只有一个值，那么直接复制到新数组
                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;
                        // 判断节点是否需要移动，位运算 为 0 则不移动
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 位运算不为 0，需移动
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将链表的尾节点置 null，并将头节点放到新位置
                    if (loTail != null) {
                        loTail.next = null;
                        // 新位置为 原始位置
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 新位置为 原始位置 + 原始数组长度
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

6、get、getNode

　　用于获取节点的 value 值。
（1）分析 get 的过程
　　Step1：先获取节点，内部调用 getNode() 方法。
　　Step2：判断数组是否为 null 或者长度为0，是则直接返回 null。对 key 进行 hash 并执行位运算（(length - 1) & hash(key)），得到数组下标，若当前数组下标位置数据为null，也返回 null。
　　Step3：若当前数组下标位置有值。
　　　　若恰好是第一个元素，直接返回第一个节点即可。
　　　　若不是第一个元素，则判断是否为红黑树结构，是则返回树节点。
　　　　若不是树结构，则遍历链表，返回相应的节点。

（2）源码：

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

/**
* 真正获取 value 的操作
*/
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 数组长度为 0 或者为 null，或者 节点不存在，直接返回一个 null
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 若恰好为 第一个节点，则返回第一个节点
        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;
}

三、常见面试题

1、为什么使用数组 + 链表 + 红黑树的数据结构？

　　数组用于确定数据存储的位置，链表用来解决哈希冲突（当冲突时，在当前数组对应的位置形成一个链表）。当链表的长度大于等于 8 时，需要将其转为红黑树，查询效率比链表高。
　　采用数组 + 链表的数据结构，可以结合数组寻址的优势以及链表在增删上的高效。

2、HashMap 什么情况下会扩容？

　　当数组长度超过阈值时（loadFactor * capacity），默认负载因子（loadFactor）为 0.75，数组（capacity）长度为 16。
　　此时的阈值为 16 * 0.75 = 12，即只要数组长度大于 12 时，就会发生扩容（resize）。数组、阈值扩大到原来的 2 倍。即当前数组长度为 16，扩容后变为 32，阈值为 24。

3、数组扩容为什么长度是 2 的次幂？

　　为了实现高效、必须减少碰撞，即需要将数据尽量均匀分配，使每个链表长度大致相同。数据 key 的哈希值直接使用肯定是不行的，可以采用取模运算，即 hash(key) % length，得到的余数作为数组的下标（ table[hash(key) % length] ）。
　　但是取模运算的效率没有移位运算高（(length - 1) & hash(key)）。length 指的是数组的长度。

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

JDK 1.8 源码给的实现是 
    (length - 1) & hash(key)， // 计算数组下标值
    table[(length - 1) & hash(key)] // 定位到数组元素的位置
也即 
    (length - 1) & hash(key) == hash(key) % length,

想要上面等式成立， length 必须满足 2 的次幂（效率最高）， 即 length = 2^n。

为什么必须满足 2 的次幂？
    因为只有 2 的次幂， length - 1 的二进制位全为1，使得 hash(key) 后几位都进行 &1 操作， 这样得到的结果等同于 hash(key) 后几位的值。
    即 (length - 1) & hash(key) == hash(key) % length
    如果 不为 2 的次幂，那么可能存在 某些值永远都不会出现的情况。

举个例子：
【hash(key) = 9, length = 16】
    此时 hash(key) % length = 9 % 16 = 9
    (length - 1) & hash(key) = 15 & 9 = 1111 & 1001 = 1001 = 9
    hash(key) % length == (length - 1) & hash(key)
    
【hash(key) = 27, length = 16】
    此时 hash(key) % length = 27 % 16 = 11
    (length - 1) & hash(key) = 15 & 27 = 01111 & 11011 = 1011 = 11
    hash(key) % length == (length - 1) & hash(key)
    
【hash(key) = 9, length = 15】
    此时 hash(key) % length = 9 % 15 = 9
    (length - 1) & hash(key) = 14 & 9 = 1110 & 1001 = 1000 = 8
    hash(key) % length !== (length - 1) & hash(key)
数组长度为 15 时，length -1 = 1110，此时不管如何，最后一位均不可能为 1，也即 1001、1101等这些值永远都获取不到。

4、String 中的 hashCode 方法

　　参考：https://segmentfault.com/a/1190000010799123。
　　以 31 为权，对每一个字符的 ASCII 码进行运算。
　　选用 31 的原因，31 * i = 32 * i - i = (i << 5) - i，31 可以被虚拟机优化成位运算，效率更高。

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

5、HashMap 线程不安全？举个例子？

　　HashMap 采用尾插法将数据插入链表的尾部，但其 putVal 方法是线程不安全的。putVal 方法中有段代码如下：

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

　　当线程 A 与线程 B 同时进行 put 操作时，且两个值的 key 经过 hash() 是一致的，即占用同一个数组元素。若此时数组元素为 null，线程 A 执行到这段代码的时候，发现该位置数据为 null，则触发一次 newNode 操作，这时线程 B 恰好也执行到这，同样触发一次 newNode 操作，这时不管是线程 A 还是线程 B成功，都会覆盖当前元素，即线程不安全。
JDK 7 用的头插法，会造成死循环（没有过多研究，有时间再补充）。

6、HashMap、HashTable、ConcurrentHashMap的区别

（1）HashMap 是线程非安全的，允许存在 null 的 key 以及 null 的 value。且只有一个为 null 的key，可以存在多个为 null 的 value。HashMap 的效率比 HashTable 高
（2）HashTable 是线程安全的，不允许存在 null 值。
（3）ConcurrentHashMap 是线程安全的 HashMap，并发能力比 HashTable 强。

原文链接:https://www.cnblogs.com/l-y-h/p/12210482.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有