JAVA HashMap源码浅析

引言

HashMap在键值对存储中被经常使用，那么它到底是如何实现键值存储的呢？

一 Entry

Entry是Map接口中的一个内部接口，它是实现键值对存储关键。在HashMap中，有Entry的实现类，叫做Entry。Entry类很简单，里面包含key，value，由外部引入的hash，还有指向下一个Entry对象的引用，和数据结构中学的链表中的note节点很类似。

Entry类的属性和构造函数:

final K key;  V value;  Entry<K,V> next;  int hash;  /**   * Creates new entry.   */  Entry(int h, K k, V v, Entry<K,V> n) {   value = v;   next = n;   key = k;   hash = h;  }

二 HashMap的初始化

//HashMap构造方法  public HashMap(int initialCapacity, float loadFactor) {   if (initialCapacity < 0)    throw new IllegalArgumentException("Illegal initial capacity: " +               initialCapacity);   if (initialCapacity > MAXIMUM_CAPACITY)    initialCapacity = MAXIMUM_CAPACITY;   if (loadFactor <= 0 || Float.isNaN(loadFactor))    throw new IllegalArgumentException("Illegal load factor: " +               loadFactor);   this.loadFactor = loadFactor;   threshold = initialCapacity;   init();  }

这是HashMap的构造函数之一，其他构造函数都引用这个构造函数进行初始化。参数InitialCapacity指的是HashMap中table数组最初的大小，参数loadFactory指的是HashMap可容纳键值对与数组长度的比值（举个例子：数组长度默认值为16，loadFactory默认值为0.75，如果HashMap中存储的键值对即Entry多于12，则会进行扩容，扩容后大小为当前数组长度的2倍）。在构造函数中不会对数组进行初始化，只有在put等操作方法内会进行判断是否要初始化或扩容。

三 table数组

如图中的[key，value]就是Entry对象来实现的，而table数组是用来存放Entry对象的。

//数组的初始化：  private static int roundUpToPowerOf2(int number) {   return number >= MAXIMUM_CAPACITY     ? MAXIMUM_CAPACITY     : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  }  private void inflateTable(int toSize) {   // Find a power of 2 >= toSize   int capacity = roundUpToPowerOf2(toSize);   threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);   table = new Entry[capacity];   initHashSeedAsNeeded(capacity);  }

在put等方法中发现数组未进行初始化时会调用InflateTable方法进行初始化，输入参数为初始设置的InitialCapacity，实际上他会调用roundUpToPowerOf2方法返回一个比初始容量大的最小的2的幂数（其中一个原因是在得到Entry所在数组位置时方便）。

四 put方法

public V put(K key, V value) {   if (table == EMPTY_TABLE) {    inflateTable(threshold);   }   if (key == null)    return putForNullKey(value);   int hash = hash(key);   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;  }  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;  }  void addEntry(int hash, K key, V value, int bucketIndex) {   if ((size >= threshold) && (null != table[bucketIndex])) {    resize(2 * table.length);    hash = (null != key) ? hash(key) : 0;    bucketIndex = indexFor(hash, table.length);   }   createEntry(hash, key, value, bucketIndex);  }  void createEntry(int hash, K key, V value, int bucketIndex) {   Entry<K,V> e = table[bucketIndex];   table[bucketIndex] = new Entry<>(hash, key, value, e);   size++;  }

//hash方法  final int hash(Object k) {   int h = hashSeed;   if (0 != h && k instanceof String) {    return sun.misc.Hashing.stringHash32((String) k);   }   h ^= k.hashCode();   // 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);  }