HashMap精选问答

野性酷女 2023-09-30 09:29 19阅读 0赞

### 关于HashMap ###

HashMap是`使用频率`最高的映射(键值对)数据类型。JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16]

### Map四大实现类：知多D ###

1.  `HashMap`：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap`最多只允许一条记录的键为null`，`允许多条记录的值为null`。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的`synchronizedMap`方法使HashMap具有线程安全的能力，或者使用`ConcurrentHashMap`。
2.  Hashtable：Hashtable是`遗留类`，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
3.  `LinkedHashMap`：LinkedHashMap是HashMap的一个子类，保存了记录的`插入顺序`，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
4.  `TreeMap`：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是`按key的升序排序`，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

### HashMap存储结构 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16 1]

1.  HashMap类中有一个非常重要的字段，就是`Node[] table`，即`哈希桶数组`，明显它是一个Node的数组。我们来看Node\[JDK1.8\]是何物。

static class Node<K,V> implements Map.Entry<K,V> {
        
            final int hash;    //用来定位数组索引位置
            final K key;
            V value;
            Node<K,V> next;   //链表的下一个node
    
            Node(int hash, K key, V value, Node<K,V> next) {
         ... }
            public final K getKey(){
         ... }
            public final V getValue() {
         ... }
            public final String toString() {
         ... }
            public final int hashCode() {
         ... }
            public final V setValue(V newValue) {
         ... }
            public final boolean equals(Object o) {
         ... }
    }

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

1.  HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。例如程序执行下面代码：

map.put("CSDN","MOSHOW");

系统将调用”CSDN”这个key的`hashCode(`)方法得到其`hashCode 值`（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算，下文有介绍）来定位该`键值对的存储位置`，有时两个key会定位到相同的位置，表示发生了`Hash碰撞`。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得`Hash碰撞的概率又小`，`哈希桶数组（Node[] table）占用空间`又少呢？答案就是好的`Hash算法和扩容机制`。

### HaspMap四个核心字段 ###

int threshold;             // 所能容纳的key-value对极限 
         final float loadFactor;    // 负载因子(默认值是0.75)是对空间和时间效率的一个平衡选择
         int modCount;  
         int size;  //HashMap中实际存在的键值对数量

首先，Node\[\] table的初始化长度`length(default=16)`，`Load factor 负载因子(default=0.75)`，`threshold`是HashMap所能容纳的最大数据量的Node(键值对)个数。`threshold = length * Load factor`。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。

结合负载因子的定义公式可知，`threshold`就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。`默认的负载因子0.75是对空间和时间效率的一个平衡选择`，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

`size`这个字段其实很好理解，`就是HashMap中实际存在的键值对数量`。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中，哈希桶数组table的长度`length大小必须为2的n次方(一定是合数)`，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说`素数导致冲突的概率要小于合数`，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在`JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）`时，链表就转换为红黑树，利用`红黑树快速增删改查`的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

### 红黑树 ###

一种平衡二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。  
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，`红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的`。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**红黑树的5个特性**：

1.  每个结点`要么是红的要么是黑的`。
2.  `根结点`是`黑`的。
3.  每个`叶结点`（叶结点即指树尾端NIL指针或NULL结点）都是`黑`的。
4.  如果一个结点是`红`的，那么它的`两个儿子都是黑`的。
5.  对于`任意结点`而言，其到叶结点树尾端`NIL指针的每条路径都包含相同数目的黑结点`。

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的`“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”`这一结论成立的原因。

### HashMap扩容机制 ###

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。`元素超过8会改为红黑树`，大幅优化性能。

需要注意的是，扩容是一个特别`耗性能`的操作，所以使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，`避免map进行频繁的扩容`。

大致步骤：

1.  判断是否超过最大容量，超过不扩张
2.  不超过就扩充为原来的两倍，并计算resize的上线
3.  搬新元素到新地址，重建索引
4.  判断是否红黑树，转红黑树；如果不是，优化hash计算

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;
            }
            // 没超过最大值，就扩充为原来的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {
                       // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 计算新的resize上限
        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) {
        
            // 把每个bucket都移动到新的buckets中
            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 {
         // 链表优化重hash的代码块
                        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;
                            }
                            // 原索引+oldCap
                            else {
        
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
        
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
        
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

### HashMap的put方法 ###

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
JDK1.8中的实现方法

public V put(K key, V value) {
        
        // 对key的hashCode()做hash
        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;
        // 步骤①：tab为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 步骤②：计算index，并对null做处理 
        if ((p = tab[i = (n - 1) & hash]) == null) 
            tab[i] = newNode(hash, key, value, null);
        else {
        
            Node<K,V> e; K k;
            // 步骤③：节点key存在，直接覆盖value
            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);
                         //链表长度大于8转换为红黑树进行处理
                        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;
    }

### ConcurrentHashMap ###

和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是`volatile`修饰的，保证了获取时的可见性。

原理上来说：`ConcurrentHashMap` 采用了`分段锁技术`，其中 `Segment` 继承于 `ReentrantLock`可重入锁（多次进入是获得锁，锁+1而不会造成死锁，退出的时候锁清0）。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/1366f293c37f4f639f5ec44c9cb6f7da.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATW9zaG936YOR6ZS0,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/6614dbf6e98544beaac9c8995296c2cb.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATW9zaG936YOR6ZS0,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/cd6f948063a34e40b864345182f272bf.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATW9zaG936YOR6ZS0,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATW9zaG936YOR6ZS0_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/6a188e689b5f4040a6d522955208da5d.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATW9zaG936YOR6ZS0,size_20,color_FFFFFF,t_70,g_se,x_16