ConcurrentHashMap
ConcurrentHashMap 结构
采用了分段锁的方法提高COncurrentHashMap并发，一个map里面有一个Segment数组——即多个Segment，一个Segment有一个HashEntry数组——即多个HashEntry。每个Segment持有一个锁，在put的时候会给Segment上锁，但是get的时候没有锁
初始化
// initialCapacity：map初始化大小// loadFactor：负载因子，当map中元素个数大于loadFactor*最大容量的时候进行refresh扩容// concurrencyLevel：并发级别，因为这个类是采用分段锁的机制实现的，该值表示分段数，需要规整为2的n次方——为了按位与计算segment数组的索引public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS; // Find power-of-two sizes best matching arguments int sshift = 0; int ssize = 1; // 有可能传入的concurrencyLevel不是2的n次方，向上规整为2的n次方 while (ssize < concurrencyLevel) { // sshift记录左移的次数 ++sshift; // 最终的segment个数——也就是并发级别 ssize <<= 1; } // 参与定位segment散列 this.segmentShift = 32 - sshift; // 参与定位segment散列 this.segmentMask = ssize - 1; if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // c为每个segment的容量 int c = initialCapacity / ssize; // 因为是整数除法，如果除不尽会去尾，加上1保证容量大于等于给定的值 if (c * ssize < initialCapacity) ++c; int cap = MIN_SEGMENT_TABLE_CAPACITY; while (cap < c) cap <<= 1; // create segments and segments[0] // 新建一个segment作为segment数组的第一个元素 // 这里没有初始化所有的segment，采用lazy-init的方式按需初始化 Segment s0 = new Segment (loadFactor, (int)(cap * loadFactor), (HashEntry [])new HashEntry[cap]); Segment [] ss = (Segment [])new Segment[ssize]; UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0] this.segments = ss;} put操作
public V put(K key, V value) { Segment s; if (value == null) throw new NullPointerException(); int hash = hash(key); // 定位segment，因为segment是ssize个，所以定位segment就是用hash值对ssize取模，使用位运算就是 // 将hash右移32-sshift位，因为hash是32位，ssize是sshift位 // 将得到的值和segment与运算，segment是ssize位全1二进制大小 int j = (hash >>> segmentShift) & segmentMask; if ((s = (Segment )UNSAFE.getObject // nonvolatile; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment // 因为是按需初始化，可能定位到的segment尚未初始化 s = ensureSegment(j); return s.put(key, hash, value, false);}final V put(K key, int hash, V value, boolean onlyIfAbsent) { // 获取锁，如果失败，会进行指定次数的尝试，超过指定次数以后会调用AbstractQueuedSynchronizer的acquire方法再次尝试获取，如果获取不到则阻塞 HashEntry node = tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue; try { HashEntry [] tab = table; // 与运算得到在hashEntry数组中中的位置 int index = (tab.length - 1) & hash; HashEntry first = entryAt(tab, index); for (HashEntry e = first;;) { if (e != null) { // 如果数组中该位置原来有值 K k; // 如果存在相同的key则替换旧值 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 { // 链表查找到最后发现不包含这个key if (node != null) // 如果scanAndLockForPut返回的node非空 node.setNext(first); else node = new HashEntry (hash, key, value, first); int c = count + 1; if (c > threshold && tab.length < MAXIMUM_CAPACITY) // 如果当前元素数大于threshold阈值则扩容 rehash(node); else setEntryAt(tab, index, node); ++modCount; count = c; oldValue = null; break; } } } finally { unlock(); } return oldValue;}private HashEntry scanAndLockForPut(K key, int hash, V value) { HashEntry first = entryForHash(this, hash); HashEntry e = first; HashEntry node = null; int retries = -1; // negative while locating node while (!tryLock()) { // 自旋过程中遍历链表是为了缓存预热，减少hash表经常出现的cache miss // 原代码注释 // we might as well help warm up the associated code and accesses as well HashEntry f; // to recheck first below if (retries < 0) { if (e == null) { if (node == null) // speculatively create node node = new HashEntry (hash, key, value, null); retries = 0; } else if (key.equals(e.key)) retries = 0; else e = e.next; } else if (++retries > MAX_SCAN_RETRIES) { // 超过次数之后阻塞 lock(); // 获得锁之后跳出循环 break; } // 当retries个位是0并且tabel这个位置的头改变了（和之前的first不一致了，说明其他线程修改了） else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) { // 如果链表头改变则重新开始查找 e = first = f; // re-traverse if entry changed retries = -1; } } return node;} hash算法
private int hash(Object k) { // 每次运行产生的随机种子 int h = hashSeed; if ((0 != h) && (k instanceof String)) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); // Spread bits to regularize both segment and index locations, // using variant of single-word Wang/Jenkins hash. h += (h << 15) ^ 0xffffcd7d; h ^= (h >>> 10); h += (h << 3); h ^= (h >>> 6); h += (h << 2) + (h << 14); return h ^ (h >>> 16);} get方法
public V get(Object key) { Segment s; // manually integrate access methods to reduce overhead HashEntry [] tab; int h = hash(key); long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; if ((s = (Segment )UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { // 因为Segment的table是votile，所以在读的时候不需要上锁 for (HashEntry e = (HashEntry ) UNSAFE.getObjectVolatile (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); e != null; e = e.next) { K k; if ((k = e.key) == key || (e.hash == h && key.equals(k))) return e.value; } } return null;}