Java HashMap 内部实现机制学习

public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode());//1.对key的hash code计算hash值 for (Entry<K,V> e = table[indexFor(hash, table.length)]; //2.调用indexFor 方法获取对应数组元素下标 e != null; e = e.next) { //3.获取数组里面的指定元素后,然后对该链表进行遍历 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) //4.找到"相同"的key后,则返回 return e.value; } return null; }?
1. // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } ?
2. return h & (length-1); }//通过位与,16-1的二进制为1111 1111 然后 去 h的后8个bit 作为 数组的下标,这样可以迅速找到该hash值对应的数组索引?
3. public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; //返回被替换的值 } } modCount++; addEntry(hash, key, value, i);//当前面一直没有匹配的key后,则把该k/v键值对放到map中 return null; }?
4. void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //此时如果发生hash冲撞时,链表中的顺序和放入元素的顺序相反 if (size++ >= threshold) //当大于阈值时,即 容量*因子 resize(2 * table.length); }?
5. void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); //需要将当前map中的元素复制到新的数组中 table = newTable; threshold = (int)(newCapacity * loadFactor); }?
6. void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) {//遍历每个数组 Entry<K,V> e = src[j]; //找到第i个数组元素 if (e != null) { src[j] = null; //及时将不需要的元素置为空,对GC友好. do { Entry<K,V> next = e.next; //假设该链表中的元素是 "Aa"->"BB" ,那么next值为"BB" int i = indexFor(e.hash, newCapacity); //获取新数组元素位置,因为newCapacity变了,所以该元素在newTable中的顺序一般也会发生改变 e.next = newTable[i]; //将e.next置为null newTable[i] = e; //然后将 newTable[i] 为 "Aa","Aa".next的值是null e = next; //此时e为"BB" TIPS:在实际分析时,可以从源码复制HashMap和AbstractMap 进行debug,便于看到HashMap内部的数据变化 } while (e != null); } } }?