HashMap中有一些我们容易忽视的点
1. 关于key的hash和equals
1public V put(K key, V value) { 2 if (table == EMPTY_TABLE) { 3 inflateTable(threshold); 4 } 5 if (key == null) 6 return putForNullKey(value); 7 int hash = hash(key); 8 int i = indexFor(hash, table.length); 9 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 10 Object k; 11 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 12 V oldValue = e.value; 13 e.value = value; 14 e.recordAccess(this); 15 return oldValue; 16 } 17 } 18 19 modCount++; 20 addEntry(hash, key, value, i); 21 return null; 22 }
由上述代码知道，hash值是用来确定bucketIndex，equals是用来和链表上的值比较，因此对于key是自定义的类，强烈建议重写hashCode和equals方法。此处也是容易引起内存泄露的点。
下面摘抄一段JDK里面的注释，
1/** 2 * Returns a hash code value for the object. This method is 3 * supported for the benefit of hash tables such as those provided by 4 * {@link java.util.HashMap}. 5 * <p> 6 * The general contract of {@code hashCode} is: 7 * <ul> 8 * <li>Whenever it is invoked on the same object more than once during 9 * an execution of a Java application, the {@code hashCode} method 10 * must consistently return the same integer, provided no information 11 * used in {@code equals} comparisons on the object is modified. 12 * This integer need not remain consistent from one execution of an 13 * application to another execution of the same application. 14 * <li>If two objects are equal according to the {@code equals(Object)} 15 * method, then calling the {@code hashCode} method on each of 16 * the two objects must produce the same integer result. 17 * <li>It is <em>not</em> required that if two objects are unequal 18 * according to the {@link java.lang.Object#equals(java.lang.Object)} 19 * method, then calling the {@code hashCode} method on each of the 20 * two objects must produce distinct integer results. However, the 21 * programmer should be aware that producing distinct integer results 22 * for unequal objects may improve the performance of hash tables. 23 * </ul> 24 * <p> 25 * As much as is reasonably practical, the hashCode method defined by 26 * class {@code Object} does return distinct integers for distinct 27 * objects. (This is typically implemented by converting the internal 28 * address of the object into an integer, but this implementation 29 * technique is not required by the 30 * Java<font size="-2"><sup>TM</sup></font> programming language.) 31 * 32 * @return a hash code value for this object. 33 * @see java.lang.Object#equals(java.lang.Object) 34 * @see java.lang.System#identityHashCode 35 */ 36 public native int hashCode();
2. rehash的条件
1void addEntry(int hash, K key, V value, int bucketIndex) { 2 if ((size >= threshold) && (null != table[bucketIndex])) { 3 resize(2 * table.length); 4 hash = (null != key) ? hash(key) : 0; 5 bucketIndex = indexFor(hash, table.length); 6 } 7 8 createEntry(hash, key, value, bucketIndex); 9 }
if条件告诉我们rehash的条件要同时满足两个：map中元素个数不小于阀值即容量*负载因子，对应的bucketIndex处有元素。
另外，如下代码作备忘，
1static int indexFor(int h, int length) { 2 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; 3 return h & (length-1); 4 }
3. 可以插入(null, null)吗
1Map<String, String> map = new HashMap<String, String>(); 2 map.put(null, null); 3 System.out.println(map.size()); // 1 4 5private V putForNullKey(V value) { 6 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 7 if (e.key == null) { 8 V oldValue = e.value; 9 e.value = value; 10 e.recordAccess(this); 11 return oldValue; 12 } 13 } 14 modCount++; 15 addEntry(0, null, value, 0); // hash = 0, bucketIndex = 0 16 return null; 17 }
注意，Hashtable和ConcurrentHashMap进行put时若value为null，将抛出NullPointerException。
4. table默认初始大小 - 16
1public HashMap(int initialCapacity, float loadFactor) { 2 // ... 3 4 this.loadFactor = loadFactor; // 0.75 5 threshold = initialCapacity; // 16 6 init(); // nothing 7 } 8 9public V put(K key, V value) { 10 if (table == EMPTY_TABLE) { 11 inflateTable(threshold); 12 } 13 // ... 14} 15 16private void inflateTable(int toSize) { 17 // Find a power of 2 >= toSize 18 int capacity = roundUpToPowerOf2(toSize); // 16 19 20 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 21 table = new Entry[capacity]; 22 initHashSeedAsNeeded(capacity); 23 } 24 25private static int roundUpToPowerOf2(int number) { 26 // assert number >= 0 : "number must be non-negative"; 27 return number >= MAXIMUM_CAPACITY 28 ? MAXIMUM_CAPACITY 29 : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; 30 }
5. 关于HashMap里的hash(Object key)方法
1final int hash(Object k) { 2 int h = hashSeed; 3 if (0 != h && k instanceof String) { 4 return sun.misc.Hashing.stringHash32((String) k); 5 } 6 7 h ^= k.hashCode(); 8 9 // This function ensures that hashCodes that differ only by 10 // constant multiples at each bit position have a bounded 11 // number of collisions (approximately 8 at default load factor). 12 h ^= (h >>> 20) ^ (h >>> 12); 13 return h ^ (h >>> 7) ^ (h >>> 4); 14 } 15 16/** 17 * Initialize the hashing mask value. We defer initialization until we 18 * really need it. 19 */ 20 final boolean initHashSeedAsNeeded(int capacity) { 21 boolean currentAltHashing = hashSeed != 0; 22 boolean useAltHashing = sun.misc.VM.isBooted() && 23 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); 24 boolean switching = currentAltHashing ^ useAltHashing; 25 if (switching) { 26 hashSeed = useAltHashing 27 ? sun.misc.Hashing.randomHashSeed(this) 28 : 0; 29 } 30 return switching; 31 }
6.从hashmap的put方法的具体逻辑来看，里面充斥着线程不安全因素：
1）map为空时，同时初始化map
2）hash冲突时，同时操作链表
3）同时rehash时造成机器load高
7.元素为什么放在链表的头部：因为单链表，放头部最快
8.LinkedHashMap的实现：继承于HashMap，内部的Entry也继承于HashMap.Entry，增加了属性before,after，另外，重写了get,addEntry,createEntry方法，提供了iterator相关方法。
9.TreeMap的实现，重点看put方法
1public V put(K key, V value) { 2 Entry<K,V> t = root; 3 if (t == null) { 4 compare(key, key); // type (and possibly null) check 5 6 root = new Entry<>(key, value, null); 7 size = 1; 8 modCount++; 9 return null; 10 } 11 int cmp; 12 Entry<K,V> parent; 13 // split comparator and comparable paths 14 Comparator<? super K> cpr = comparator; 15 if (cpr != null) { 16 do { 17 parent = t; 18 cmp = cpr.compare(key, t.key); 19 if (cmp < 0) 20 t = t.left; 21 else if (cmp > 0) 22 t = t.right; 23 else 24 return t.setValue(value); 25 } while (t != null); 26 } 27 else { 28 if (key == null) 29 throw new NullPointerException(); 30 Comparable<? super K> k = (Comparable<? super K>) key; 31 do { 32 parent = t; 33 cmp = k.compareTo(t.key); 34 if (cmp < 0) 35 t = t.left; 36 else if (cmp > 0) 37 t = t.right; 38 else 39 return t.setValue(value); 40 } while (t != null); 41 } 42 Entry<K,V> e = new Entry<>(key, value, parent); 43 if (cmp < 0) 44 parent.left = e; 45 else 46 parent.right = e; 47 fixAfterInsertion(e); 48 size++; 49 modCount++; 50 return null; 51 }
10. jdk7 ConcurrentHashMap的get,size,put方法
1public V get(Object key) { 2 Segment<K,V> s; // manually integrate access methods to reduce overhead 3 HashEntry<K,V>[] tab; 4 int h = hash(key); 5 long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE; 6 if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && 7 (tab = s.table) != null) { 8 for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile 9 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); 10 e != null; e = e.next) { 11 K k; 12 if ((k = e.key) == key || (e.hash == h && key.equals(k))) 13 return e.value; 14 } 15 } 16 return null; 17 } 18 19public int size() { 20 // Try a few times to get accurate count. On failure due to 21 // continuous async changes in table, resort to locking. 22 final Segment<K,V>[] segments = this.segments; 23 int size; 24 boolean overflow; // true if size overflows 32 bits 25 long sum; // sum of modCounts 26 long last = 0L; // previous sum 27 int retries = -1; // first iteration isn't retry 28 try { 29 for (;;) { 30 if (retries++ == RETRIES_BEFORE_LOCK) { 31 for (int j = 0; j < segments.length; ++j) 32 ensureSegment(j).lock(); // force creation 33 } 34 sum = 0L; 35 size = 0; 36 overflow = false; 37 for (int j = 0; j < segments.length; ++j) { 38 Segment<K,V> seg = segmentAt(segments, j); 39 if (seg != null) { 40 sum += seg.modCount; 41 int c = seg.count; 42 if (c < 0 || (size += c) < 0) 43 overflow = true; 44 } 45 } 46 if (sum == last) 47 break; 48 last = sum; 49 } 50 } finally { 51 if (retries > RETRIES_BEFORE_LOCK) { 52 for (int j = 0; j < segments.length; ++j) 53 segmentAt(segments, j).unlock(); 54 } 55 } 56 return overflow ? Integer.MAX_VALUE : size; 57 } 58 59public V put(K key, V value) { 60 Segment<K,V> s; 61 if (value == null) 62 throw new NullPointerException(); 63 int hash = hash(key); 64 int j = (hash >>> segmentShift) & segmentMask; 65 if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck 66 (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment 67 s = ensureSegment(j); 68 return s.put(key, hash, value, false); 69 } 70 71public V putIfAbsent(K key, V value) { 72 Segment<K,V> s; 73 if (value == null) 74 throw new NullPointerException(); 75 int hash = hash(key); 76 int j = (hash >>> segmentShift) & segmentMask; 77 if ((s = (Segment<K,V>)UNSAFE.getObject 78 (segments, (j << SSHIFT) + SBASE)) == null) 79 s = ensureSegment(j); 80 return s.put(key, hash, value, true); 81 } 82 83final V put(K key, int hash, V value, boolean onlyIfAbsent) { 84 HashEntry<K,V> node = tryLock() ? null : 85 scanAndLockForPut(key, hash, value); 86 V oldValue; 87 try { 88 HashEntry<K,V>[] tab = table; 89 int index = (tab.length - 1) & hash; 90 HashEntry<K,V> first = entryAt(tab, index); 91 for (HashEntry<K,V> e = first;;) { 92 if (e != null) { 93 K k; 94 if ((k = e.key) == key || 95 (e.hash == hash && key.equals(k))) { 96 oldValue = e.value; 97 if (!onlyIfAbsent) { 98 e.value = value; 99 ++modCount; 100 } 101 break; 102 } 103 e = e.next; 104 } 105 else { 106 if (node != null) 107 node.setNext(first); 108 else 109 node = new HashEntry<K,V>(hash, key, value, first); 110 int c = count + 1; 111 if (c > threshold && tab.length < MAXIMUM_CAPACITY) 112 rehash(node); 113 else 114 setEntryAt(tab, index, node); 115 ++modCount; 116 count = c; 117 oldValue = null; 118 break; 119 } 120 } 121 } finally { 122 unlock(); 123 } 124 return oldValue; 125 } 126 127/** 128 * Scans for a node containing given key while trying to 129 * acquire lock, creating and returning one if not found. Upon 130 * return, guarantees that lock is held. UNlike in most 131 * methods, calls to method equals are not screened: Since 132 * traversal speed doesn't matter, we might as well help warm 133 * up the associated code and accesses as well. 134 * 135 * @return a new node if key not found, else null 136 */ 137 private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) { 138 HashEntry<K,V> first = entryForHash(this, hash); 139 HashEntry<K,V> e = first; 140 HashEntry<K,V> node = null; 141 int retries = -1; // negative while locating node 142 while (!tryLock()) { 143 HashEntry<K,V> f; // to recheck first below 144 if (retries < 0) { 145 if (e == null) { 146 if (node == null) // speculatively create node 147 node = new HashEntry<K,V>(hash, key, value, null); 148 retries = 0; 149 } 150 else if (key.equals(e.key)) 151 retries = 0; 152 else 153 e = e.next; 154 } 155 else if (++retries > MAX_SCAN_RETRIES) { 156 lock(); 157 break; 158 } 159 else if ((retries & 1) == 0 && 160 (f = entryForHash(this, hash)) != first) { 161 e = first = f; // re-traverse if entry changed 162 retries = -1; 163 } 164 } 165 return node; 166 }