【数据结构】超详细！从HashMap到ConcurrentMap，我是如何一步步实现线程安全的！

客官°小女子只卖身不卖艺 2024-03-30 12:53 36阅读 0赞

## 什么是HashMap？ ##

在了解 `HashMap` 之前先了解一下什么是 `Map`；

### 什么是Map？ ###

**定义**

`Map` 是一个用于存储 Key-Value 键值对的集合类，也就是一组键值对的映射，在 Java 中 `Map` 是一个接口，是和 `Collection` 接口同一等级的集合根接口；

**存储结构**

![1f681dbbada2b2599484e90f5ff34e68.png][]

上图看起来像是数据库中的关系表，有类似的两个字段，KeySet（键的集合）和 Values（值的集合），每一个键值对都是一个 **Entry**；

**特点**

1.  没有重复的 key；
    
     *  key 用 `set` 保存，所以 key 必须唯一；
     *  `Map` 基本上是通过 key 来获取 value，如果有两个相同的 key，计算机将不知道取哪个值，如果 `put` 了两个相同的 key，后一个则会覆盖前一个的 value 值；在源码的注释中已经说明：
        
        ![587292441c349591527ce9c8192a7526.png][]
        
        大致翻译一下：
        
        > 将该 map 中的指定值与指定键关联(可选操作)。如果映射先前包含键的映射，则旧值将被指定的值替换。(当且仅当 `{@link #containsKey(Object) m.containsKey(k)}` 返回 true 时，映射 m 被称为包含键k的映射。)
2.  每个 key 只能对应一个 value，多个 key 可以对应一个 value（这就是映射的概念，最经典的例子就是射箭，一排的射手和一排的箭靶，每个射手只有一根箭，那么一个射手只能射中一个箭靶，而每个箭靶可能被不同射手射中，箭就是映射）；
3.  key，value 都可以是任何引用类型的数据，包括 `null`，但只能是引用类型；
4.  Map 取代了古老的 Dictionary 抽象类（简单了解一下）；

### HashMap定义 ###

把任意长度的输入（预映射），通过一种函数 `hashCode()`，变换成固定长度的输出，该输出就是**哈希值** `hashCode`，这种函数就叫做**哈希函数**，而计算哈希值的过程就叫做**哈希**；

哈希的主要应用是哈希表和分布式缓存，注意，哈希算法和哈希函数不是一个东西，哈希函数是哈希算法的一种实现；

HashMap 是用哈希表（数组（桶）加单链表）+ 红黑树实现的 map 类，但是不同版本的 JDK 实现 HashMap 的原理有所不同：

*  JDK 1.6 - 1.7 采用位桶 + 链表实现；
 *  JDK 1.8 采用位桶 + 链表 + 红黑树实现，当链表长度超过阈值 “8” 时，将链表转换为红黑树；

下面以 JDK 1.8 为版本进行讲解；

### HashMap底层原理 ###

**体系结构**

HashMap 是一个用于存储 Key-Value 键值对的集合，每一个键值对也叫做 Entry。HashMap 新增一个元素时，会先计算 key 的 hash 值，找到存入数组（桶）的位置，如果该位置已经有节点（链表头），则存入该节点的最后一个位置（链表尾），所以 HashMap 就是一个数组（桶），数组上每一个元素都是一个节点（节点和所有下一个节点组成一个链表）或者为 `null`（HashMap 数组每一个元素的初始值都是 `null`），显然同一个链表上的节点 hash 值都一样。

![c9ec70e30634fb334732fab8aa226d8c.png][]

**源码解读**

首先看到的是 HashMap 的构造器：

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        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;
        this.threshold = tableSizeFor(initialCapacity);
    }

注释中已经说得很清楚了，`Constructs an empty <tt>HashMap</tt> with the specified initial capacity and load factor.`，这个构造器主要是用来初始化桶的数量和装载因子；

接下来往前看，看一下几个比较重要的常量，`DEFAULT_INITIAL_CAPACITY`，`MAXIMUM_CAPACITY`，`DEFAULT_LOAD_FACTOR`；

![8026b1edfe8426ec406555399e505c81.png][]

可以看到桶的初始容量默认为16，值得注意的是，桶的初始容量和扩容后的容量必须是 2n，所以桶的最大容量就是230，即 `1 << 30`；

默认负载系数为 0.75，负载系数也称为负载因子，是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。经过大量的实验证明， HashMap 的默认负载因子为0.75最宜；

当表中超过75%的位置已经填入元素，这个表就会用双倍的桶数自动地进行再散列(rehashed)，可以通过构造函数初始化；

这里进行扩展一下，便于理解：

--------------------

由于 HashMap 特殊的存储结构，因此 HashMap 在获取指定元素前需要把 key 经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率极高，说白了就是 HashMap 用了拉链法的哈希表，也有称之为桶数组的；

下面看到 JDK 1.8 中的源码部分：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    /**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {}
    
    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

当我们通过 `put()` 方法输入键值对后，虽然我们只输入了键值对，但他却传递了五个参数，源码注释已经很清楚了，就不多解释了，接下来看到 hash 算法，将键 key 传入，如果 key 为 ``

[1f681dbbada2b2599484e90f5ff34e68.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9a0ac88b785a490aaf12c318103b15f0.png
[587292441c349591527ce9c8192a7526.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8ede588377f14e6cbe9ed9dd5bf826d3.png
[c9ec70e30634fb334732fab8aa226d8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6d2927023e9d406fb66b336d841e8a1a.png
[8026b1edfe8426ec406555399e505c81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/604936844b3e4e7994508f8efc19775b.png