面试必备之HashMap底层设计与实现详解

public HashMap(int initialCapacity, float loadFactor) {
　　　　　// initialCapacity代表初始化HashMap的容量，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal initial capacity: " +
 initialCapacity);
 if (initialCapacity > MAXIMUM_CAPACITY)
 initialCapacity = MAXIMUM_CAPACITY;
　　　　 // loadFactor代表它的负载因子，默认是是DEFAULT_LOAD_FACTOR=0.75，用来计算threshold临界值的。
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
 throw new IllegalArgumentException("Illegal load factor: " +
 loadFactor);
 // Find a power of 2 >= initialCapacity
 int capacity = 1;
 while (capacity < initialCapacity)
 capacity <<= 1;
 this.loadFactor = loadFactor;
 threshold = (int)(capacity * loadFactor);
 table = new Entry[capacity];
 init();
 }

// 计算二次Hash 
int hash = hash(key.hashCode());
// 通过Hash找数组索引
int i = indexFor(hash, table.length);

 /**
 * Returns a hash code for this string. The hash code for a
 * <code>String</code> object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using <code>int</code> arithmetic, where <code>s[i]</code> is the
 * <i>i</i>th character of the string, <code>n</code> is the length of
 * the string, and <code>^</code> indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return a hash code value for this object.
 */
 public int hashCode() {
 int h = hash;
 if (h == 0 && value.length > 0) {
 char val[] = value;
 for (int i = 0; i < value.length; i++) {
 h = 31 * h + val[i];
 }
 hash = h;
 }
 return h;
 }

static int hash(int h) {
 // 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);
 }

/**
 * Returns index for hash code h.
 */
 static int indexFor(int h, int length) {
 return h & (length-1);
 }

 int h=15,length=16;
 System.out.println(h & (length-1));
 h=15+16;
 System.out.println(h & (length-1));
 h=15+16+16;
 System.out.println(h & (length-1));
 h=15+16+16+16;
 System.out.println(h & (length-1));

System.out.println(Integer.parseInt("0001111", 2) & Integer.parseInt("0001111", 2));
System.out.println(Integer.parseInt("0011111", 2) & Integer.parseInt("0001111", 2));
System.out.println(Integer.parseInt("0111111", 2) & Integer.parseInt("0001111", 2));
System.out.println(Integer.parseInt("1111111", 2) & Integer.parseInt("0001111", 2));

 static int hash(int h) {
 // 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);
 }

 /**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
 * (A <tt>null</tt> return can also indicate that the map
 * previously associated <tt>null</tt> with <tt>key</tt>.)
 */
 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);
 return null;
 }

 /**
 * Offloaded version of put for null keys
 */
 private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
 }

private abstract class HashIterator<E> implements Iterator<E> {
 Entry<K,V> next; // next entry to return
 int expectedModCount; // For fast-fail
 int index; // current slot
 Entry<K,V> current; // current entry
 HashIterator() {
 expectedModCount = modCount;
 if (size > 0) { // advance to first entry
 Entry[] t = table;
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 }
 public final boolean hasNext() {
 return next != null;
 }
 final Entry<K,V> nextEntry() {
　　　　　　　　// 这里就是关键
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Entry<K,V> e = next;
 if (e == null)
 throw new NoSuchElementException();
 if ((next = e.next) == null) {
 Entry[] t = table;
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 current = e;
 return e;
 }
 public void remove() {
 if (current == null)
 throw new IllegalStateException();
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Object k = current.key;
 current = null;
 HashMap.this.removeEntryForKey(k);
 expectedModCount = modCount;
 }
 }

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);
 if (size++ >= threshold)
 resize(2 * table.length);
 }

 public V get(Object key) {
 if (key == null)
 return getForNullKey();
 int hash = hash(key.hashCode());
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
 e != null;
 e = e.next) {
 Object k;
 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
 return e.value;
 }
 return null;
 }

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);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
 }

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];
 if (e != null) {
 src[j] = null;
 do {
 Entry<K,V> next = e.next;
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;
 } while (e != null);
 }
 }
 }