今天看Java并发编程实践时，看到关于为计算结果建立高效、可伸缩的高效缓存的时候，书中首先用了HashMap做缓存容器（我们在项目中也常使用），在读取缓存值时会存在线程安全的问题，下面这段代码是我们项目里的业务代码：
1 private static Map<String, Set<Long>> domainOrderIdMap = Maps.newHashMap(); 2 private Set<Long> getOrderIdSet(String domain) { 3 // 需要过滤的订单id集合 4 Set<Long> filterOrderIdsSet; 5 if (domainOrderIdMap.get(domain) == null) { 6 synchronized (this) { 7 filterOrderIdsSet = Sets.newHashSet(); 8 String filterOrderIdsStr = CommonConfigUtil.getItem(domain); 9 if(StringUtils.isNotBlank(filterOrderIdsStr)) { 10 String[] filterOrderIdsArr = StringUtils.split(filterOrderIdsStr, "|"); 11 for(String orderId : filterOrderIdsArr) { 12 filterOrderIdsSet.add(Long.parseLong(orderId)); 13 } 14 } 15 domainOrderIdMap.put(domain, filterOrderIdsSet); 16 } 17 } else { 18 filterOrderIdsSet = domainOrderIdMap.get(domain); 19 } 20 return filterOrderIdsSet; 21 }
这段代码很简单，domain作为key，对应的id Set<Long>作为value。取Set的时候先判断该domain在缓存中存在不存在，不存在则从文件读取domain对应的id set，加入到缓存中并返回该set。其中生成domain的对应的value的逻辑由于涉及到写缓存所以加上锁。这段代码除了当两个线程用同一个domain去命中，同时为空的时候会进行两次计算并重复写入缓存的问题外（这种情况出现的次数不是很多），看似就没任何问题了，但是还有一个问题，我们从源码里面慢慢找出这个问题：
先看一下HashMap的get方法：
1 public V get(Object key) { 2 if (key == null) 3 return getForNullKey(); 4 int hash = hash(key.hashCode()); 5 for (Entry<K,V> e = table[indexFor(hash, table.length)]; 6 e != null; 7 e = e.next) { 8 Object k; 9 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 10 return e.value; 11 } 12 return null; 13 }
当key为null时找到对应的value，getForNullKey方法如下：
1 private V getForNullKey() { 2 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 3 if (e.key == null) 4 return e.value; 5 } 6 return null; 7 }
当key为null时，认为null的hash值为0，在链表里面查找是否存在值为null的key，存在则返回，不存在则返回null（从这个方法里面我们可以看到HashMap的key是支持null的）。现在回到get方法：
如果key不为null，则对key对应的hashCode值进行hash（hash函数如下）：
1 static int hash(int h) { 2 // This function ensures that hashCodes that differ only by 3 // constant multiples at each bit position have a bounded 4 // number of collisions (approximately 8 at default load factor). 5 h ^= (h >>> 20) ^ (h >>> 12); 6 return h ^ (h >>> 7) ^ (h >>> 4); 7 }
这个方法看着不是很明白，但肯定是为了尽量提高hash值分散的程度，而且值很大。
得到hash值之后就需要得到这个hash值对应的数组的index，用到了indexFor:
1 static int indexFor(int h, int length) { 2 return h & (length-1); 3 }
这个方法就是把hash值和数组长度-1值进行按位与，hash值很大，但是初始数组长度就是16，如何把一个很大的值映射到一个较小的数内，jdk提供的这个方法应该是效率最高的吧。
回到get方法，得到数组的index之后就需要取出数组槽中的链表的首值，并进行遍历，如果出现hash值相等且key相等的Entry
e，则返回e.value，否则返回null。
至此，get方法分析完成了，其中对Entry对象还不是很了解，下面先分析Entry对象：
1 static class Entry<K,V> implements Map.Entry<K,V> { 2 final K key; 3 V value; 4 Entry<K,V> next; 5 final int hash; 6 7 /** 8 * Creates new entry. 9 */ 10 Entry(int h, K k, V v, Entry<K,V> n) { 11 value = v; 12 next = n; 13 key = k; 14 hash = h; 15 } 16 ... 17 }
这是一个静态内部类，具有四个属性：key，value，指向链表下一个值得指针以及key对应的hash值，还有就是带有四个域参数的构造函数。从代码里面我们可以知道这是一个带有链表结构的类（同学说这是一个循环链表，到目前为止还没看出来，继续看）。
分析完了Entry，就该put方法了，这是应该是最重要的：
1 public V put(K key, V value) { 2 if (key == null) 3 return putForNullKey(value); 4 int hash = hash(key.hashCode()); 5 int i = indexFor(hash, table.length); 6 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 7 Object k; 8 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 9 V oldValue = e.value; 10 e.value = value; 11 e.recordAccess(this); 12 return oldValue; 13 } 14 } 15 // 这个变量做什么的？ 16 modCount++; 17 addEntry(hash, key, value, i); 18 return null; 19 }
逻辑也比较简单，先判断key是否为null，是则执行putForNullKey，不是则和get方法类似（取key对应的hash值再获取该值对应的数组index）；其次取到数组中的index对应槽中的链表的首元素，进行遍历，如果命中则返回该key对应的value（可以看到用新value代替了旧value）；如果在链表里没有找到则添加Entry，代码如下：
1 void addEntry(int hash, K key, V value, int bucketIndex) { 2 Entry<K,V> e = table[bucketIndex]; 3 table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 4 if (size++ >= threshold) 5 resize(2 * table.length); 6 }
从代码中可以看出新增一个Entry是放在链表的第一个位置的，Key-Value对的数目+1，如果大于设置的阈值（12=16*0.75），进行数组扩容（x2）：
1 void resize(int newCapacity) { 2 Entry[] oldTable = table; 3 int oldCapacity = oldTable.length; 4 if (oldCapacity == MAXIMUM_CAPACITY) { 5 threshold = Integer.MAX_VALUE; 6 return; 7 } 8 9 Entry[] newTable = new Entry[newCapacity]; 10 transfer(newTable); 11 table = newTable; 12 threshold = (int)(newCapacity * loadFactor); 13 }
如果数组的size已经达到最大容量，则扩容的阈值变最大值，以后不会再进行扩容；如果没有达到最大容量，则新建一个扩容后的数组用来存放Entry，并且把就数组里的值重新映射到新数组中，更新域数组指针（指向新数组），最后更新最大容量。这段代码中最重要的就是旧数组到新数组的转换：
1 void transfer(Entry[] newTable) { 2 Entry[] src = table; 3 int newCapacity = newTable.length; 4 for (int j = 0; j < src.length; j++) { 5 Entry<K,V> e = src[j]; 6 if (e != null) { 7 src[j] = null; 8 do { 9 Entry<K,V> next = e.next; 10 int i = indexFor(e.hash, newCapacity); 11 e.next = newTable[i]; 12 newTable[i] = e; 13 e = next; 14 } while (e != null); 15 } 16 } 17 }
我们可以看到Entry链表并非为循环链表。
读完所有的代码后，我们可以看到最关键的地方，在从hashmap里面get值时，即使存在该key，但是取出来仍旧为null的现象，原因就是：
1 if (e != null) { 2 src[j] = null;
当Entry数组需要扩容时，这个线程把旧数组内的所有值都转移到了新数组里面，并且把旧数组的值设置为null。因此文章开头描述的那段代码是有问题的，最简单的处理方法就是把锁的粒度放大一行。
原文：http://www.cnblogs.com/peiyuc/p/3576456.html