基于哈希表的 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;          }        }