HashMap/ConcurrentHashMap详解

╰半夏微凉° 2022-05-24 12:55 179阅读 0赞

一、HashMap

1.HashMap本质是一个数组，数组的每个元素都是一个单链表。

java源码中，这个数组就是table，其定义如下：

transient Node<K,V>[] table;//table数组，每个数组元素都是一个链表，链表由0个或多个节点组成

节点类定义如下，注释中解释此类：

//静态内部类的特点：在创建静态内部类的实例时，不必创建外部类的实例
    static class Node<K,V> implements Map.Entry<K,V> {//Entry是Map接口中的一个内部接口
        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() {//此Node类的hashCode方法
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) {//重新设置节点Value，返回旧Value
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    
        public final boolean equals(Object o) {//判断节点相等的方法，
            if (o == this)//同一个对象，返回true
                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;//键和值都相等则返回true
            }
            return false;
        }
    }

2.HashMap的重点方法

（1）hash方法

hash()用来计算一个键对应的hash值，

（HashMap中的hashCode方法用来返回HashMap对象的hash值，跟这里研究的hash()没有一毛钱关系）

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

key.hashCode()函数调用的是key键值类型自带的哈希函数，它返回一个32位int类型的散列值。

考虑到2进制32位带符号的int表值范围从-2147483648到2147483648，前后加起来大概40亿的映射空间。一个40亿长度的数组，内存是放不下的！

所以散列值一般只会用到后面的位，但是如果只取到最后几位的话，碰撞会很严重。于是就有了“扰动函数”——右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了**混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。**

**hash()的返回值是一个低16位经过扰动处理的int类型**，还是不会直接拿来用的。源码中每次使用键的hash值时都会通过这种方式：

n = tab.length
    tab[(n - 1) & hash]

由resize()方法（Initializes or doubles table size）可知，数组长度必为2的整数次幂，因此(n - 1) & hash相当于低位掩码。

那么为什么不用取余呢？因为散列值的大小必须在\[0,length-1\]中，而取余的结果可能是负数。

那么为什么不用取余再取绝对值呢？因为对于Integer.MIN，Math.abs()会返回一个负值。

另外，从这里也可以得出一个结论：**对于HashMap的同一个链表中各个节点的key的hash值不一定相同。**

（2）get()

//获取键对应的值
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    //根据哈希值和键获取对应的值对象
    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值找到对应的链表头节点
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))//如果要找的key和第一个node的key是同一个对象or equals，则返回第一个节点
                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))))//如果hash值相等且key对象是同一个或equals，返回
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap在JDK1.8中新增的操作：桶的树形化——在Java 8 中，如果一个桶中的元素个数超过 TREEIFY\_THRESHOLD(默认是 8 )，就使用红黑树来替换链表，从而提高速度。

*  TREEIFY\_THRESHOLD
 *  UNTREEIFY\_THRESHOLD
 *  MIN\_TREEIFY\_CAPACITY

值及作用如下：

//一个桶的树化阈值
    //当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点
    //这个值必须为 8，要不然频繁转换效率也不高
    static final int TREEIFY_THRESHOLD = 8;
    
    //一个树的链表还原阈值
    //当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
    //这个值应该比上面那个小，至少为 6，避免频繁转换
    static final int UNTREEIFY_THRESHOLD = 6;
    
    //哈希表的最小树形化容量
    //当哈希表中的容量大于这个值时，表中的桶才能进行树形化
    //否则桶内元素太多时会扩容，而不是树形化
    //为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
    static final int MIN_TREEIFY_CAPACITY = 64;

（3）put()

public V put(K key, V value) {
        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;
        if ((tab = table) == null || (n = tab.length) == 0)//table不存在则先初始化之
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//如果链表为null则新建一个节点（nextNode指向自己）
            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))))//验证要存的键值对是否等于头节点
                e = p;
            else if (p instanceof TreeNode)//处理数组该处元素为树的情况
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//遍历链表插入<K,V>
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);//不存在此key，新加入一个节点并验证是否需要树化
                        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))))//存在此key
                        break;
                    p = e;//相当于p = p.next
                }
            }
            if (e != null) { //处理存在此key的情况：更新value并返回旧value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);// Callbacks to allow LinkedHashMap post-actions
                return oldValue;
            }
        }
        ++modCount;//modCount用于记录HashMap的修改次数
    /**由于HashMap不是线程安全的,所以在迭代的时候,会将modCount赋值到迭代器的expectedModCount属性中,然后进行迭代,
    *如果在迭代的过程中HashMap被其他线程修改了,modCount的数值就会发生变化,
    *这个时候expectedModCount和ModCount不相等,
    *迭代器就会抛出ConcurrentModificationException()异常
    **/
        if (++size > threshold)//数组大小到达临界值则会double size
            resize();
        afterNodeInsertion(evict);// Callbacks to allow LinkedHashMap post-actions
        return null;//key存在时返回oldValue,不存在时返回null
    }

4.hashmap例题

[https://www.cnblogs.com/coderxuyang/p/3718856.html][https_www.cnblogs.com_coderxuyang_p_3718856.html]

初始容量设为400/3=134，hashmap会自动变为大于134的最小2^n，即256.

二、ConcurrentHashMap

锁分段技术（java1.8之前）：HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。

1.关键属性

// ConcurrentHashMap核心数组
        transient volatile Node<K,V>[] table;
    
        // 扩容时才会用的一个临时数组
        private transient volatile Node<K,V>[] nextTable;
        
        /**
         * table初始化和resize控制字段
         * 负数表示table正在初始化或resize。-1表示正在初始化，-N表示有N-1个线程正在resize操作
         * 当table为null的时候，保存初始化表的大小以用于创建时使用，或者直接采用默认值0
         * table初始化之后，保存下一次扩容的的大小，跟HashMap的threshold = loadFactor*capacity作用相同
         */
        private transient volatile int sizeCtl;
    
        // resize的时候下一个需要处理的元素下标为index=transferIndex-1
        private transient volatile int transferIndex;
    
        // 通过CAS无锁更新，ConcurrentHashMap元素总数，但不是准确值
        // 因为多个线程同时更新会导致部分线程更新失败，失败时会将元素数目变化存储在counterCells中
        private transient volatile long baseCount;
    
        // resize或者创建CounterCells时的一个标志位
        private transient volatile int cellsBusy;
    
        // 用于存储元素变动
        private transient volatile CounterCell[] counterCells;

2.CAS（比较并交换）

Unsafe.compareAndSwapXXX方法是jdk.internal.misc.Unsafe类中的方法，Unsafe类用于执行低级别、不安全操作的方法集合。

private static final Unsafe U = Unsafe.getUnsafe();

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
        return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

CAS的含义是：“我认为V的值应该是A，如果是，那么将V的值更新为B；否则，不修改并告诉V的值实际是多少"

CAS方法都是native方法，可以保证原子性，并且效率比synchronized高。

3.spread方法

ConcurrentHashMap中没有hash()方法，取而代之的是spread方法。spread方法解释：

static final int HASH_BITS = 0x7fffffff;//用来屏蔽符号位
    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;//先对低16位进行扰动处理，然后屏蔽符号位，结果为32位int型非负数
    }
    int h = spread(key.hashCode());//调用
    e = tabAt(tab, (n - 1) & h)//和hash()一样，不会直接使用，根据数组长度只取低位哈希值

4.get()

get操作不需要锁。除非读到的值是空的才会加锁重读。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE);//获取传入的哈希值对应的节点
    }
    /**
    *数组元素定位：
    *
    *Unsafe类中有很多以BASE_OFFSET结尾的常量，比如ARRAY_INT_BASE_OFFSET，ARRAY_BYTE_BASE_OFFSET等，
    *这些常量值是通过arrayBaseOffset方法得到的。arrayBaseOffset方法是一个本地方法，可以获取数组第一个元素的偏移地址。
    *Unsafe类中还有很多以INDEX_SCALE结尾的常量，比如 ARRAY_INT_INDEX_SCALE ， ARRAY_BYTE_INDEX_SCALE等，
    *这些常量值是通过arrayIndexScale方法得到的。arrayIndexScale方法也是一个本地方法，
    *可以获取数组的转换因子，也就是数组中元素的增量地址。
    *将arrayBaseOffset与arrayIndexScale配合使用，可以定位数组中每个元素在内存中的位置。
    **/
    ABASE = U.arrayBaseOffset(Node[].class);//获取数组第一个元素的偏移地址
    int scale = U.arrayIndexScale(Node[].class);//获取数组中元素的增量
    if ((scale & (scale - 1)) != 0)//scale不是2的整数次方则出错
        throw new Error("array index scale not a power of two");
    ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);//scale非0位的位数
    
    
    public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

有点看不下去了，以后再写吧。

LinkedHashMap

这篇不错：

[https://blog.csdn.net/justloveyou\_/article/details/71713781][https_blog.csdn.net_justloveyou_article_details_71713781]

linkedhashmap的特色是有序（插入顺序或读取顺序），考点是LRU！！

## LinkedHashMap 与 LRU(Least recently used，最近最少使用)算法 ##

到此为止，我们已经分析完了LinkedHashMap的存取实现，这与HashMap大体相同。**LinkedHashMap区别于HashMap最大的一个不同点是，前者是有序的，而后者是无序的。为此，LinkedHashMap增加了两个属性用于保证顺序，分别是双向链表头结点header和标志位accessOrder。**我们知道，header是LinkedHashMap所维护的双向链表的头结点，而accessOrder用于决定具体的迭代顺序。实际上，accessOrder标志位的作用可不像我们描述的这样简单，我们接下来仔细分析一波~  
　　  
　　我们知道，当accessOrder标志位为true时，表示双向链表中的元素按照访问的先后顺序排列，可以看到，虽然Entry插入链表的顺序依然是按照其put到LinkedHashMap中的顺序，但put和get方法均有调用recordAccess方法（put方法在key相同时会调用）。recordAccess方法判断accessOrder是否为true，如果是，则将当前访问的Entry（put进来的Entry或get出来的Entry）移到双向链表的尾部（key不相同时，put新Entry时，会调用addEntry，它会调用createEntry，该方法同样将新插入的元素放入到双向链表的尾部，既符合插入的先后顺序，又符合访问的先后顺序，因为这时该Entry也被访问了）；当标志位accessOrder的值为false时，表示双向链表中的元素按照Entry插入LinkedHashMap到中的先后顺序排序，即每次put到LinkedHashMap中的Entry都放在双向链表的尾部，这样遍历双向链表时，Entry的输出顺序便和插入的顺序一致，这也是默认的双向链表的存储顺序。因此，当标志位accessOrder的值为false时，虽然也会调用recordAccess方法，但不做任何操作。

注意到我们在前面介绍的LinkedHashMap的五种构造方法，前四个构造方法都将accessOrder设为false，说明默认是按照插入顺序排序的；而第五个构造方法可以自定义传入的accessOrder的值，因此可以指定双向循环链表中元素的排序规则。特别地，**当我们要用LinkedHashMap实现LRU算法时，就需要调用该构造方法并将accessOrder置为true。**

参考：

[http://www.importnew.com/16301.html][http_www.importnew.com_16301.html]

[https://www.zhihu.com/question/20733617/answer/111577937][https_www.zhihu.com_question_20733617_answer_111577937]

[https://blog.csdn.net/u011240877/article/details/53358305][https_blog.csdn.net_u011240877_article_details_53358305]

[https://www.cnblogs.com/snowater/p/8087166.html][https_www.cnblogs.com_snowater_p_8087166.html]

[https://www.cnblogs.com/mickole/articles/3757278.html][https_www.cnblogs.com_mickole_articles_3757278.html]

[http://www.bubuko.com/infodetail-1612665.html][http_www.bubuko.com_infodetail-1612665.html]

[https_www.cnblogs.com_coderxuyang_p_3718856.html]: https://www.cnblogs.com/coderxuyang/p/3718856.html
[https_blog.csdn.net_justloveyou_article_details_71713781]: https://blog.csdn.net/justloveyou_/article/details/71713781
[http_www.importnew.com_16301.html]: http://www.importnew.com/16301.html
[https_www.zhihu.com_question_20733617_answer_111577937]: https://www.zhihu.com/question/20733617/answer/111577937
[https_blog.csdn.net_u011240877_article_details_53358305]: https://blog.csdn.net/u011240877/article/details/53358305
[https_www.cnblogs.com_snowater_p_8087166.html]: https://www.cnblogs.com/snowater/p/8087166.html
[https_www.cnblogs.com_mickole_articles_3757278.html]: https://www.cnblogs.com/mickole/articles/3757278.html
[http_www.bubuko.com_infodetail-1612665.html]: http://www.bubuko.com/infodetail-1612665.html