欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HashMap和ConcurrentHashMap的实现原理和冲突解决 博客分类: java

程序员文章站 2024-03-06 18:01:14
...

本篇源码来自JDK1.8.

 

Java的位运算和取模取余操作说明:

 

位运算(&)效率要比取余运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

 

X % 2^n = X & (2^n - 1)

2^n表示2的n次方,也就是说,一个数对2^n取余 == 一个数和(2^n - 1)做按位与运算

假设n为3,则2^3 = 8,表示成2进制就是1000。2^3 -1 = 7 ,即0111。

此时X & (2^3 - 1) 就相当于取X的2进制的最后三位数。

 

右移和取模

从2进制角度来看,X / 8相当于 X >> 3,即把X右移3位,此时得到了X / 8的商,而被移掉的部分(后三位),则是X % 8,也就是余数。

 

HashMap的初始化:

可以是无参数的初始化,也可以指定初始大小和加载因子。

第一次添加元素时,进行第一次扩容,设置一个大小为16的数组,其中包含的元素为Node<K,V>,扩容的临界值为0.75 * 16 = 12,即等到大小超过12时再次进行扩容。

Node<K,V>结点包含4个元素:

 Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;//next用于处理有冲突的情况,
        }

扩容时,会把旧的数组中的元素,重新计算索引,放入新的数组中。

newTab[e.hash & (newCap - 1)] = e;//根据元素的hash值与当前的容量-1,进行位元素,相当于取余操作

  

扩容时,新的size计算,新的容量=旧的容量*2:

 if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }

 

HashMap初始化时,如果指定了一个集合,或者指定了一个初始大小,则会自动计算出一个比它大的最近的2^n值作为初始化数组的大小。计算数组大小的方法如下:

 static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

 

 

 

HashMap的put方法:

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);//通过key,获取一个hash值
    }

 

    获取hash值的算法,用key的hashcode值高16位于低16位进行异或操作。

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

 

HashMap中解决冲突的方法, 先用线性链表来保存冲突,如果冲突链表长度超过8,则使用红黑树结构。

 

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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//put时,没有冲突,直接新建一个Node。
            tab[i] = newNode(hash, key, value, null);
        else {  //如果此处有Node,则解决冲突
            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 {
                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;
                    }
                    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;
    }

 

put方法(新增元素)总结:

计算元素数组下标的方法:通过元素Key的hash值与数组容量取余。

hash值相同,则产生冲突。但是hash值相同,不一定key相同。

1,通过key值获取一个hash值。

2,判断当前是否达到临界值,确定是否扩容,扩容则会把当前的容量扩大一倍。扩容时,会重新根据元素的hash值和新的数组容量,计算元素的数组下标。

3,新建一个Node结点,计算数组下标,放入对应的位置,如果有冲突,则添加进链表或者红黑树。产生冲突时,如果新增的Node结点的key与之前的key相同,则返回之前的key对应的value值。

 

根据Key值获取对象:

 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) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))//判断hash和equals,都相等,则获取成功;
                return first;
            if ((e = first.next) != null) {//否则从链表中往下寻找。
                if (first instanceof TreeNode)  //如果是红黑树,则从红黑树中获取Node.
                    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;
    }

 

 

由于HashMap的扩容需要重新计算各个已有元素的hash值,并重新调整数组下标,是一个耗时的操作,因此最好初始化时就指定HashMap的容量initialCapacity。

initicalCapacity = (需要存储的元素个数/负载因子) + 1。  负载因子默认为0.75。如果不确定存储的元素个数,设置初始大小为16(默认值)。

 

只有当HashMap中一次性添加一个集合putAll(),或者初始化指定容量大小时,才会通过算法计算容量大小,保证容量大小为2的n次幂。 put操作,如果容量为空,则初始化为16,容量不够,则只会简单的把当前容量扩大一倍。HashMap的容量因此能一直保持为2的N次幂大小。

 

ConcurrentHashMap:

ConcurrentHashMap的初始化时如果指定大小initialCapacity

则以initialCapacity + (initialCapacity >>> 1) + 1 开始调整,计算出比它大的最近的2^n值作为初始大小

 

public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }
 

 JDK 8之后,ConcurrentHashMap的实现原理与之前有较大的变化:

它摒弃了Segment(锁段)的概念,改用了Synchronized 和 CAS原理来实现并发。它的底层与HashMap一致,仍然采用数组+链表+红黑树的结构。

 

第一次插入数据时,进行初始化数组initTable();

putVal方法中有一个无限循环:

for (Node<K,V>[] tab = table;;),只有操作成功才会跳出循环。

这其实是因为并发操作时,有时需要不断自旋等待。  

 

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();//初始化数组,
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
               //利用CAS算法,设置位置i的元素node
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)//如果正在扩容,移动元素,则加入帮助扩容
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {//节点插入链表或者插入红黑树时,进行同步
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
  

 

 

获取几个相关参数的内存地址,使用CAS操作直接进行修改。

 

 // Unsafe mechanics
    private static final sun.misc.Unsafe U;
    private static final long SIZECTL;
    private static final long TRANSFERINDEX;
    private static final long BASECOUNT;
    private static final long CELLSBUSY;
    private static final long CELLVALUE;
    private static final long ABASE;
    private static final int ASHIFT;

    static {
        try {
            U = sun.misc.Unsafe.getUnsafe();
            Class<?> k = ConcurrentHashMap.class;
            SIZECTL = U.objectFieldOffset
                (k.getDeclaredField("sizeCtl"));
            TRANSFERINDEX = U.objectFieldOffset
                (k.getDeclaredField("transferIndex"));
            BASECOUNT = U.objectFieldOffset
                (k.getDeclaredField("baseCount"));
            CELLSBUSY = U.objectFieldOffset
                (k.getDeclaredField("cellsBusy"));
            Class<?> ck = CounterCell.class;
            CELLVALUE = U.objectFieldOffset
                (ck.getDeclaredField("value"));
            Class<?> ak = Node[].class;
            ABASE = U.arrayBaseOffset(ak);//获取数组第一个元素在内存中的偏移位置
            int scale = U.arrayIndexScale(ak);//获取数组中元素的增量地址
              //将arrayBaseOffset和arrayIndexScale配合使用,可以获取数组中每个元素的偏移位置
            if ((scale & (scale - 1)) != 0)
                throw new Error("data type scale not a power of two");
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (Exception e) {
            throw new Error(e);
        }
    }
 

 

相关的几个CAS操作的方法:

  static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

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

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

 

 

EnumMap使用

EnumMap是专门为枚举类型量身定做的Map实现。

EnumMap要求其Key必须为Enum类型,它只能接收同一枚举类型的实例作为键值且不能为null。

EnumMap使用数组来存放与枚举类型对应的值,由于枚举类型实例的数量相对固定并且有限,所以使用EnumMap不会涉及到数组扩容,性能会更加高效。