ConcurrentHashMap的put方法
public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); //基于key,计算hash值 int hash = hash(key); //因为一个键要计算两个数组的索引,为了避免冲突,这里取高位计算Segment[]的索引 int j = (hash >>> segmentShift) & segmentMask; //判断该索引位的Segment对象是否创建,没有就创建 if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment s = ensureSegment(j); //调用Segmetn的put方法实现元素添加 return s.put(key, hash, value, false); }ConcurrentHashMap的ensureSegment方法
//创建对应索引位的Segment对象,并返回 private Segment<K,V> ensureSegment(int k) { final Segment<K,V>[] ss = this.segments; long u = (k << SSHIFT) + SBASE; // 需要创建的Segment对象的下标索引 Segment<K,V> seg; //获取,如果为null,即创建 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { //以0角标位的Segment为模板 Segment<K,V> proto = ss[0]; // use segment 0 as prototype int cap = proto.table.length; float lf = proto.loadFactor; int threshold = (int)(cap * lf); HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap]; //获取,如果为null,即创建 if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // 二次检查 //创建 Segment<K,V> s = new Segment<K,V>(lf, threshold, tab); //自旋方式,将创建的Segment对象放到Segment[]中,确保线程安全 while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s)) break; } } } //返回 return seg; }Segment的put方法
final V put(K key, int hash, V value, boolean onlyIfAbsent) { //尝试获取锁,获取成功,node为null,代码向下执行 //如果有其他线程占据锁对象,那么去做别的事情,而不是一直等待,提升效率 //scanAndLockForPut 稍后分析 HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue; try { HashEntry<K,V>[] tab = table; //取hash的低位,计算HashEntry[]的索引 int index = (tab.length - 1) & hash; //获取索引位的元素对象 HashEntry<K,V> first = entryAt(tab, index); for (HashEntry<K,V> e = first;;) { //获取的元素对象不为空 if (e != null) { K k; //如果是重复元素,覆盖原值 if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { oldValue = e.value; if (!onlyIfAbsent) { e.value = value; ++modCount; } break; } //如果不是重复元素,获取链表的下一个元素,继续循环遍历链表 e = e.next; } else { //如果获取到的元素为空 //当前添加的键值对的HashEntry对象已经创建 if (node != null) node.setNext(first); //头插法关联即可 else //创建当前添加的键值对的HashEntry对象 node = new HashEntry<K,V>(hash, key, value, first); //添加的元素数量递增 int c = count + 1; //判断是否需要扩容 if (c > threshold && tab.length < MAXIMUM_CAPACITY) //需要扩容 rehash(node); else //不需要扩容 //将当前添加的元素对象,存入数组角标位,完成头插法添加元素 setEntryAt(tab, index, node); ++modCount; count = c; oldValue = null; break; } } } finally { //释放锁 unlock(); } return oldValue; }Segment的scanAndLockForPut方法
该方法在线程没有获取到锁的情况下,去完成HashEntry对象的创建,提升效率
但是这个操作个人感觉有点累赘了
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { //获取头部元素 HashEntry<K,V> first = entryForHash(this, hash); HashEntry<K,V> e = first; HashEntry<K,V> node = null; int retries = -1; // negative while locating node while (!tryLock()) { //获取锁失败 HashEntry<K,V> f; // to recheck first below if (retries < 0) { //没有下一个节点,并且也不是重复元素,创建HashEntry对象,不再遍历 if (e == null) { if (node == null) // speculatively create node node = new HashEntry<K,V>(hash, key, value, null); retries = 0; } else if (key.equals(e.key)) //重复元素,不创建HashEntry对象,不再遍历 retries = 0; else //继续遍历下一个节点 e = e.next; } else if (++retries > MAX_SCAN_RETRIES) { //如果尝试获取锁的次数过多,直接阻塞 //MAX_SCAN_RETRIES会根据可用cpu核数来确定 lock(); break; } else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { //如果期间有别的线程获取锁,重新遍历 e = first = f; // re-traverse if entry changed retries = -1; } } return node; } 1.3.2 模拟多线程的代码流程