浅谈HashMap，LinkedHashMap，ConcurrentHashMap、synchronizedMap（一.HashMap）

╰+攻爆jí腚メ 2022-05-28 10:08 195阅读 0赞

本文旨在记录自己所学，自己理解，并不深入。

## 为什么Map要以Hash（键值对）方式存储 ##

我们都知道Map是以键值对的方式存储的，但是想过没有，为什么要有这种方式？这种方式的优点是什么？想知道这点，我们要知道数组、链表的特性。

<table> 
 <thead> 
  <tr> 
   <th>数组</th> 
   <th align="center">链表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>静态分配内存（栈中），大小固定</td> 
   <td align="center">动态分配内存（堆中），大小可变</td> 
  </tr> 
  <tr> 
   <td>内存中连续存放</td> 
   <td align="center">内存地址可能是分散的，所以必须通过上一节点中的信息找能找到下一个节点。</td> 
  </tr> 
  <tr> 
   <td>插入、删除操作不方便，因为插入、删除操作会导致大量元素的移动。</td> 
   <td align="center">插入、删除操作方便，不会导致元素的移动，因为元素增减，只需要调整指针。</td> 
  </tr> 
  <tr> 
   <td>数组支持随机访问</td> 
   <td align="center">不支持随机访问</td> 
  </tr> 
  <tr> 
   <td>数组利用下标定位，时间复杂度为O(1)</td> 
   <td align="center">链表定位元素时间复杂度O(n)</td> 
  </tr> 
 </tbody> 
</table>

所以我们可以总结出一句话：数组适合查找操作，链表适合增删操作。那么问题来了，我既想要查找想数组一样快，增删也想要链表的速度，怎么办？好办，数组加链表就可以了，取二者优点。所以Hash表（键值对）就出现了。  
Hash表的数据结构：  
![Hash表的数据结构][Hash]  
数组位置的判断是根据我们要插入的元素以某种规则生成的Hash值。我们发现，不相同的数据通过hash函数得到相同的key值。这时候，就产生了hash冲突。Map解决冲突的方式是拉链法。拉链法的思想在产生冲突的hash地址指向一个链表，将具有相同的key值的数据存放到链表中。所以为什么要有Hash表，Hash表是什么我们也大概清楚。其实解决Hash冲突有很多办法，Map中只用到了拉链法。其他的请参考大牛博客吧。  
**虽然JDK马上要更新到10了，但是现在用的最多的还是8，所以我们以下的代码都是基于JDK1.8**

## HashMap ##

HashMap的存储结构知道了，我们就直接看源码吧。

### 属性 ###

/** * 默认初始化大小为16。在HashMap中大量使用位运算的地方。 */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /** * 最大容量是2的30次幂 */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /** * 默认填充因子（加载因子）。这个值代表在一定空间下，多少数据查询速率最快。 * 在初始化HashMap的时候可以进行更改。 */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /** * 因为在1.8之后，HashMap引入了红黑树的概念。 * 所以当链表长度大于8的时候，链表将会转换为红黑树，加快查询速度 */
        static final int TREEIFY_THRESHOLD = 8;
    
        /** * 当链表长度小于6的时候，红黑树将会转换为链表。 */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /** * 翻译： * 当桶中的bin被树化时最小的hash表容量。（如果没有达到这个阈值， * 即hash表容量小于MIN_TREEIFY_CAPACITY，当桶中bin的数量太多时会执行 * resize扩容操作）这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。 * 我的理解是： * 当哈希表中的容量大于这个值时，表中的桶才能进行树形化 * 否则桶内元素太多时会扩容，而不是树形化 * 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD。 * 也就是说：链表树化有两个条件：哈希表中的容量大于64，且链表上长度大于8。 */
        static final int MIN_TREEIFY_CAPACITY = 64;
    
        /** * 存放元素的最小单元。总是2的幂次倍。 * Node对象实现了Map.Entry<>。 */
        transient Node<K,V>[] table;
    
        /** * 存放元素集合。 */
        transient Set<Map.Entry<K,V>> entrySet;
    
        /** * map的大小，并不是数组的长度 */
        transient int size;
    
        /** * 每次扩容和更改map结构的计数器。如果出现多线程对同一Map集合进行操作， * 导致modCount不一样，那么就会产生fail-fast错误， * 报concurrentmodificationexceptions异常错误。 */
        transient int modCount;
    
        /** * 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容 */
        int threshold;
    
        /** * 加载因子 */
        final float loadFactor;

### 构造方法 ###

/** * 同时指定初始化容量 以及 加载因子。 * 如果大小或者加载因子为负数，报错。 */
        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);
        }
    
        /** * 创建指定大小的HashMap，加载因子默认为0.75f， * 长度大小为参数大小，如果是负数，报错。 */
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /** * 默认构造函数，长度为16，填充因子为0.75f public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 新建一个哈希表，同时将另一个map m 里的所有元素加入表中。 * 默认加载因子以及足够大的容量。如果m为空，报NullPointerException。 */
        public HashMap(Map<? extends K, ? extends V> m) {
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

### 三个不实现的函数 ###

有三个函数我们要知道：

// Callbacks to allow LinkedHashMap post-actions
        void afterNodeAccess(Node<K,V> p) { }
        void afterNodeInsertion(boolean evict) { }
        void afterNodeRemoval(Node<K,V> p) { }

通过注释我们了解到，这三个是为了LinkedHashMap进行准备，HashMap中并没有对其进行实现。我们后面再说LinkedHashMap。

### putVal() ###

// 如果参数onlyIfAbsent是true，那么不会覆盖相同key的值value。
        // 如果evict是false。那么表示是在初始化时调用的
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            // tab存放当前的hash桶，p用作临时链表节点
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            // 判断当前hash桶是否为空。
            if ((tab = table) == null || (n = tab.length) == 0)
                // 如果时空的，直接扩容（初始化）hash桶，并记录长度n
                n = (tab = resize()).length;
            // 这里判断当前节点是否存在hash冲突，(n - 1) & hash 确定元素存放在哪个桶中。
            // 取目标桶节点p，判断是否为null。
            if ((p = tab[i = (n - 1) & hash]) == null)
                // 如果不存在创建新节点，放在目标桶中。
                tab[i] = newNode(hash, key, value, null);
                // 存在
            else {
                Node<K,V> e; K k;
                // 判断当前节点的hash值，key是否相等。相等的话，执行覆盖操作。
                // 这里也就是为什么hashMap不能存放相同的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) {
                        // 如果是链表尾部
                        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值与插入元素相等的结点
                // 针对已经存在key的情况做处理。
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    //onlyIfAbsent表示存在key相同时不做覆盖处理。这里作为判断条件
                    //当onlyIfAbsent为false或者oldValue为null时，进行覆盖操作。
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    // LinkedHashMap实现
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            // 结构性修改
            ++modCount;
            // 当HashMap中存在的node节点大于threshold时，hashmap进行扩容。
            if (++size > threshold)
                resize();
            // LinkedHashMap实现
            afterNodeInsertion(evict);
            return null;
        }

### getNode() ###

getNode()方法主要说一下当hashCode相同时，该如何获取。

final Node<K,V> getNode(int hash, Object key) {
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
                // 桶中第一项(数组元素)相等，也就是产生hash冲突，要查询数据在链表中
                // 此时我们要调用查询数据的equals方法，判断key是否相同。
                // 所以在扩展类（自定义类）重写HashCode和equals方法很有必要！！！！！
                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;
        }

还有hash()，tableSizeFor()，resize()暂时不写了，以后添加。

### 总结HashMap： ###

1.  我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到桶（数组）位置来储存Entry对象。这里关键点在于指出，HashMap是在桶中储存键对象和值对象，作为Map.Entry。
2.  当插入数据发生hash冲突时，会将该数据存储到冲突位置后面的链表中。
3.  如果插入数据的key相同，那么就会覆盖原来的值。
4.  因为链表上所有值的hash值是相同的，那么我们如何获取链表上的值，根据hashCode显然是不行的。根据源码此时我们要调用查询数据的equals方法，判断key是否相同。所以在扩展类（自定义类）重写HashCode和equals方法很有必要！！！！！
5.  hashMap在什么时候进行扩容，当实际大小(容量\*填充因子)超过临界值时，会进行扩容。
6.  fail-fast机制：每次扩容和更改map结构的计数器。如果出现多线程对同一Map集合进行操作，导致modCount不一样，那么就会产生fail-fast错误，报concurrentmodificationexceptions异常错误。这里不做详细说明。
7.  hashMap线程不安全体现：  
    1）两个线程同时增加key相同数据，导致一个线程添加数据失败。但是它并不知道。因为被覆盖了。同理删除和更改操作也会产生类似错误。同样，在多线程对Map进行更改的时候，会导致modCount不同，产生fail-faset错误。  
    2）扩容机制：当map需要扩容的时候，若两个线程同时对map进行扩容，那么在值转移（从oldTab转移到newTab）过程中，可能会形成循环链表。
8.  既然hash表的产生是为了查找速度快的同时，插入删除顺序也快。那么HashMap的插入，查找时间是多少？  
    1）put()：理论上来说当然是O(1)，我们只要找到对应的桶的位置就OK。但是实际上还有很多时间开销的，比如hash碰撞，另外hash的计算也要耗费CPU时间。所以一般我们认为它的时间复杂度是常数级的。  
    2）get()：从hashMap中获取一个数据大概分成4步：  
    ①先根据key值计算出hash值以及h值（h值是java实现中处理得到的更优的index索引值）  
    ②查找table数组中的h位置，得到相应的键值对链表。  
    ③根据key值，遍历键值对链表，找到相应的键值对。  
    ④从键值对中取出value值。  
    第①②⑤步的时间复杂度理论上是O（1）的，这个没有问题。那么只有③也是O（1）的时候，查找的时间复杂度也是O（1）的。那么，步骤3中链表的长度决定了整个hashmap容器的查找效率，这也是hashmap容器设计的关键。必须采用优秀的hash算法以减少“冲突”，使得链表的长度尽可能短，理想状态下链表长度都为1。  
    所以数据结构中，查找速度为O（1）的除了数组还有`Map<key,value>。`
9.  HashMap无序的表现在put设置的时候，hashmap定位数组索引是通过key值取哈希获得的。而key的哈希值是和和key本身的值相关。所以在put时，指定的索引就是无序的。  
    而在keyset进行遍历时，又是先遍历数组的，数组本身又是有序的。而且遍历数组后还有链表。本身hashmap的数据结构就有两层。所以取到的key值肯定不会有序。

[Hash]: /images/20220528/6019868f44c24ec0845da89dd31d26cb.png