search

bigwolftime / gitmentCommentsPlugin

0 stars 0 forks source link

HashMap #25

Open bigwolftime opened 3 years ago

bigwolftime commented 3 years ago

https://index1024.gitee.io/xblog/HashMap/

一. 概要

JDK8 版本的 HashMap 相对于 JDK7 有了一些优化, 比较明显的就是引入了红黑树的数据结构, 提升查询效率.

  1. HashMap:

日常使用频次较高的结构. 非线程安全, 如果有线程安全的需求, 可以考虑使用 Collections.synchronizedMap() 或者 ConcurrentHashMap. 允许 key 为 null(最多只能有一个), 允许 value 为 null. 键值对的插入顺序与遍历顺序不固定.

  1. HashTable:

遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary 类，并且是线程安全的. 任一时间只有一个线程能写 Hashtable，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁(分段锁是 JDK7 的实现方式, JDK8 抛弃了此种方式, 使用 CAS + Synchronized 原理实现).

  1. LinkedHashMap:

属于 HashMap 的子类, 底层使用链表实现, 可保存键值对的插入顺序.

  1. TreeMap:

实现 SortedMap 接口, 默认根据”键”进行排序(也可自定义比较器).

二. HashMap 的实现

图中有一个数组 table, 当键值对插入时, 会根据 key 进行 hashCode() 计算, 然后一系列操作后确定数组的索引位置(下面介绍), 然后键值对会封装成 Node 对象存储到 table 数组中. Node 的代码如下:

  1. Node

// Node 是 HashMap 内部类, 实现 Entry 接口 static class Node<K, V> implements Entry<K, V> { final int hash; final K key; V value;

    /**
    *  下一个元素的地址. 用于解决 hash 冲突
    *  hash 冲突的解决办法一般有: 链地址法和开放地址法(我所见过的一些组件, hash 冲突使用的基本都是链地址, 开放地址法暂未遇到过)
    *
    *  hash 冲突一般与这些因素有关:
    *   1. hash 函数: 一个好的 hash 函数, 基本可以保证数据均匀分布, 冲突最少, 以达到最好的性能;
    *   2. table 数组容量: 若容量较小, 即使使用优秀的 Hash 函数, 也会有大概率的冲突.
    */
    HashMap.Node<K, V> next;

    Node(int hash, K key, V value, HashMap.Node<K, V> next) {}
    public final K getKey() {}
    public final V getValue() {}
    public final String toString() {}
    public final int hashCode() { return Objects.hashCode(this.key) ^ Objects.hashCode(this.value); }
    public final V setValue(V newValue) {}
    public final boolean equals(Object o) {
        if (o == this) {
            return true;
        } else {
            if (o instanceof Entry) {
                Entry<?, ?> e = (Entry)o;
                if (Objects.equals(this.key, e.getKey()) && Objects.equals(this.value, e.getValue())) {
                    return true;
                }
            }

            return false;
        }
    }
}
  1. 初始化参数

// 默认的 table 数组容量 static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认的负载因子值 static final float DEFAULT_LOAD_FACTOR = 0.75F;

/**

// HashMap 中实际的 Node 个数(注意和 table.length, threshold 区别) transient int size; // 记录 HashMap 内部结构发生变化的次数, 用于迭代的快速失败. transient int modCount;

// 当前可容纳键值对的最大值, 达到此阈值则需扩容 int threshold;

/**

此外, 数组的长度也有要求, 需要保证为 table.length = 2 的 n 次幂, 采用这种设计主要是优化: 取模和扩容的过程.

  1. 确定桶索引位置

对 map 中的 key 进行曾删改查, 第一步就是要根据 key 确定数组的哪个索引位置.

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

// jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的 static int indexFor(int h, int length) { // 由于取模计算消耗较大, 这里可以用位运算 h & (length-1) 代替 (h % length). 此处就是数组长度是 2 的幂次的好处. return h & (length-1); }

上面的 hash() 方法: (h = key.hashCode()) ^ (h >>> 16). 首先计算 key 的 hashCode(int_32), 然后和 hashCode 的高 16bit 异或计算, 当数组的长度较小, 也可保证高低位都参与到计算中, 同时不会有大的开销. 如下图:

  1. put()

JDK8 HashMap 的 put 流程可参考下图, 非常详细.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 判空. new HashMap() 执行后, 并不会为 table 数组初始化空间, 而是等调用 put 时判断.
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算 index
    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))))
            // 节点已经存在, 覆盖 value
            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 已存在, 覆盖 value
                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();
    afterNodeInsertion(evict);
    return null;
}
  1. resize()

当需要对数组进行初始化, 或者当前已有的 Node 节点数 size 已达到 threshold 时, 则需要调用 resize() 进行扩容. 由于 JDK8 中引入了红黑树, 逻辑稍复杂, 所以此处分析 JDK7 的 resize() 方法, 本质上区别不大.

数组是连续的内存空间, 长度一旦定义, 后续无法进行修改, 所以此处的数组扩容指的是: 开辟出一个新的, 更大的空间, 用来存储数据, 原数组中的元素会重新 hash 计算 put 到新数组中.

/**

/**

举例(JDK7):

HashMap 数组的大小为 2, 负载因子为 1(threshold = loadFactor * table.length = 2), hash 函数为: key % table.length 插入三个键值对: (3, A), (7, B), (5, C). 第一个键值对 (3, A) 中 3 % 2 = 1 即插入到数组索引位为 1 的桶, 同理: 键值对 (7, B) 和 (5, C) 也会落到索引为 1 的位置, 并且在 JDK7 中采用头插法, 那么全部插入后如图中最上面一行:

插入 (5, C) 键值对后, 此时节点数 size > threshold(扩容阈值), 会进入扩容过程. 上面图中剩余的 3 行就是扩容的过程. 由此看出, 扩展之后元素要么在原来的位置, 要么在原位置上移动 2 次幂的位置, 具体的解释如下图:

图中的 (a),(b) 分别表示扩容前, 后桶的计算. 扩容后的 (n - 1) 较扩容前的 (n - 1) 多出了一个最高位 1(从右向左第5位), 然后可以通过 key1(hash) 对应的第5位与 (n - 1) 的第5位做按位与运算, 如果是0, 则索引不变, 如果是1, 则索引变为原来的 2 的幂次, 这样在扩容的过程中 就省去了 hash 的计算. 这是数组长度位 2 的幂次的第二点好处.

还有一个结论, 因为是头插法, 扩容之后的链表节点顺序与原来是完全相反的. 但是 JDK8 这里采用了尾插法, 相对顺序还是一样的, 即不会倒置.

  1. 线程安全性

线程安全性是针对 HashMap 面试考点较多的地方, 例如: HashMap 是否线程安全? 放在多线程中使用有什么结果? 环形链表的怎么回事?

首先 HashMap 无法保证线程安全, 有多线程的场景可以考虑使用 Collections.synchronizedMap() 或 ConcurrentHashMap.

可能造成死循环的代码(JDK7)

public class HashMapInfiniteLoop {

private static HashMap<Integer,String> map = new HashMap<Integer,String>(2, 0.75f);

public static void main(String[] args) {
    map.put(5,
bigwolftime commented 3 years ago

OK