深入JDK源码之HashMap类

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap的实例有两个参数影响其性能： 初始容量 和 加载因子 。 容量 是哈希表中桶的数量， 初始容量 只是哈希表在创建时的容量。 加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

通常， 默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

HashMap的数据结构

HashMap用了一个名字为table的Entry类型数组；数组中的每一项又是一个Entry链表。

// 默认的初始化大小     static final int DEFAULT_INITIAL_CAPACITY = 16;     // 最大的容量     static final int MAXIMUM_CAPACITY = 1 << 30;     // 负载因子     static final float DEFAULT_LOAD_FACTOR = 0.75f;     // 储存key-value键值对的数组，一个键值对对象映射一个Entry对象     transient Entry[] table;     // 键值对的数目     transient int size;     // 调整HashMap大小门槛，该变量包含了HashMap能容纳的key-value对的极限，它的值等于HashMap的容量乘以负载因子     int threshold;     // 加载因子     final float loadFactor;     // HashMap结构修改次数,防止在遍历时，有其他的线程在进行修改     transient volatile int modCount;     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);          // Find a power of 2 >= initialCapacity         int capacity = 1;         // 使得capacity 的大小为2的幂，至于为什么，请看下面         while (capacity < initialCapacity)             capacity <<= 1;          this.loadFactor = loadFactor;         threshold = (int) (capacity * loadFactor);         table = new Entry[capacity];         init();     }

下面是用于包装key-value映射关系的Entry，它是HashMap的静态内部类：

static class Entry<K,V> implements Map.Entry<K,V> {         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;         }          public final K getKey() {             return key;         }          public final V getValue() {             return value;         }          public final V setValue(V newValue) {             V oldValue = value;             value = newValue;             return oldValue;         }          public final boolean equals(Object o) {             if (!(o instanceof Map.Entry))                 return false;             Map.Entry e = (Map.Entry)o;             Object k1 = getKey();             Object k2 = e.getKey();             if (k1 == k2 || (k1 != null && k1.equals(k2))) {                 Object v1 = getValue();                 Object v2 = e.getValue();                 if (v1 == v2 || (v1 != null && v1.equals(v2)))                     return true;             }             return false;         }          public final int hashCode() {             return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());         }          public final String toString() {             return getKey() + "=" + getValue();         }          /**          * This method is invoked whenever the value in an entry is          * overwritten by an invocation of put(k,v) for a key k that's already          * in the HashMap.          */         void recordAccess(HashMap<K,V> m) {         }          /**          * This method is invoked whenever the entry is          * removed from the table.          */         void recordRemoval(HashMap<K,V> m) {         }     }

HashMap的put和get及remove方法

// 根据key获取value     public V get(Object key) {         if (key == null)             return getForNullKey();         //根据key的hashCode值计算它的hash码         int hash = hash(key.hashCode());         //直接取出table数组中指定索引处的值         for (Entry<K, V> e = table[indexFor(hash, table.length)];          e != null;          //搜索该Entry链的下一个Entry         e = e.next) {             Object k;             //如果该Entry的key与被搜索key相同             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))                 return e.value;         }         return null;     }      private V getForNullKey() {         //key为null，hash码为0，也就是说key为null的Entry位于table[0]的Entry链上         for (Entry<K, V> e = table[0]; e != null; e = e.next) {             if (e.key == null)                 return e.value;         }         return null;     }     public V put(K key, V value) {         if (key == null)             return putForNullKey(value);         //根据key的hashCode值计算它的hash码         int hash = hash(key.hashCode());         //搜索指定hash值对应table中的索引值         int i = indexFor(hash, table.length);         for (Entry<K, V> e = table[i]; e != null; e = e.next) {             Object k;             //如果找到指定key与需要放入的key相等（hash值相同，通过equals比较返回true）             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                 V oldValue = e.value;                 //新的值覆盖旧值                 e.value = value;                 //这个方法是个空方法，可能是表示个标记，字面意思是表示记录访问                 e.recordAccess(this);                 //返回旧值                 return oldValue;             }         }          modCount++;         //如果i处索引处的Entry为null，表示此处还没有Entry         //将key、value添加到i索引处         addEntry(hash, key, value, i);         return null;     }      //key=null的键值对,默认存放table[0]的Entry链     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) {         Entry<K, V> e = table[bucketIndex];         table[bucketIndex] = new Entry<K, V>(hash, key, value, e);         if (size++ >= threshold)             resize(2 * table.length);     }     //根据键值移除key-value映射对象     public V remove(Object key) {         Entry<K, V> e = removeEntryForKey(key);         return (e == null ? null : e.value);     }      final Entry<K, V> removeEntryForKey(Object key) {         int hash = (key == null) ? 0 : hash(key.hashCode());         int i = indexFor(hash, table.length);         Entry<K, V> prev = table[i];         Entry<K, V> e = prev;          while (e != null) {             Entry<K, V> next = e.next;             Object k;             if (e.hash == hash                     && ((k = e.key) == key || (key != null && key.equals(k)))) {                 modCount++;                 size--;                 if (prev == e)                     table[i] = next;                 else                     prev.next = next;                 //空方法，表示移除记录                 e.recordRemoval(this);                 return e;             }             prev = e;             e = next;         }          return e;     }

HashMap的hash算法和size大小调整

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.      */     // 根据hash码求的数组小标并返回，当length为2的幂时，h & (length-1)等价于h%(length-1)，这里也就是为什么前面说table的长度必须是2的幂     static int indexFor(int h, int length) {         return h & (length - 1);     }     // 调整大小     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);     }      /**      * Transfers all entries from current table to newTable.      */     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 {                                             //注意这里哈，HashMap不保证顺序恒久不变                                         //在这里可以找到答案                     Entry<K, V> next = e.next;                     int i = indexFor(e.hash, newCapacity);                     e.next = newTable[i];                     newTable[i] = e;                     e = next;                 } while (e != null);             }         }     }

HashMap与Set的关系

Set代表一种集合元素无序、集合元素不可重复的集合。如果只考察HashMap中的key，不难发现集合中的key有一个特征：所有的key不能重复，key之间无序。具备了Set的特征，所有的key集合起来组成一个Set集合。同理所有的Entry集合起来，也是一个Set集合。而value是可以重复的，不能组成一个Set集合，在HashMap源代码中提供了values()方法把value集合起来组成Collection集合。

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;         }      }      private final class ValueIterator extends HashIterator<V> {         public V next() {             return nextEntry().value;         }     }      private final class KeyIterator extends HashIterator<K> {         public K next() {             return nextEntry().getKey();         }     }      private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {         public Map.Entry<K, V> next() {             return nextEntry();         }     }     Iterator<K> newKeyIterator() {         return new KeyIterator();     }     Iterator<V> newValueIterator() {         return new ValueIterator();     }     Iterator<Map.Entry<K, V>> newEntryIterator() {         return new EntryIterator();     }     // Views      private transient Set<Map.Entry<K, V>> entrySet = null;      //把所有的key集合成Set集合     public Set<K> keySet() {         Set<K> ks = keySet;         return (ks != null ? ks : (keySet = new KeySet()));     }      private final class KeySet extends AbstractSet<K> {         public Iterator<K> iterator() {             return newKeyIterator();         }          public int size() {             return size;         }          public boolean contains(Object o) {             return containsKey(o);         }          public boolean remove(Object o) {             return HashMap.this.removeEntryForKey(o) != null;         }          public void clear() {             HashMap.this.clear();         }     }     //把所有的values集合成Collection集合     public Collection<V> values() {         Collection<V> vs = values;         return (vs != null ? vs : (values = new Values()));     }      private final class Values extends AbstractCollection<V> {         public Iterator<V> iterator() {             return newValueIterator();         }         public int size() {             return size;         }         public boolean contains(Object o) {             return containsValue(o);         }          public void clear() {             HashMap.this.clear();         }     }       //把所有的Entry对象集合成Set集合     public Set<Map.Entry<K, V>> entrySet() {         return entrySet0();     }      private Set<Map.Entry<K, V>> entrySet0() {         Set<Map.Entry<K, V>> es = entrySet;         return es != null ? es : (entrySet = new EntrySet());     }      private final class EntrySet extends AbstractSet<Map.Entry<K, V>> {         public Iterator<Map.Entry<K, V>> iterator() {             return newEntryIterator();         }         public boolean contains(Object o) {             if (!(o instanceof Map.Entry))                 return false;             Map.Entry<K, V> e = (Map.Entry<K, V>) o;             Entry<K, V> candidate = getEntry(e.getKey());             return candidate != null && candidate.equals(e);         }         public boolean remove(Object o) {             return removeMapping(o) != null;         }         public int size() {             return size;         }         public void clear() {             HashMap.this.clear();         }     }

Fail-Fast策略（速错）

HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛ConcurrentModificationException，这就是所谓fail-fast策略（速错），这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了。

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;         }      }