Jdk 1.7

一、数据结构

HashMap中的数据结构是数组+单链表的组合，以键值对（key-value）的形式存储元素的，通过put() 和 get() 方法存储和获取对象。

image.png

二、实现原理

成员变量

源码分析：

/** 初始容量，默认为16 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** 最大初始容量，2^30 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** 负载因子，默认0.75，负载因子越小，hash冲突机率越低（当容量达到75%时就进行扩容操作） */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** 初始化一个Entry的空数组，数组还没有进行扩容操作的时候，共享的一个空表对象 */
static final Entry<?, ?>[] EMPTY_TABLE = {};
/** 将初始化好的空数组赋值给table，table数组是HashMap实际存储数据的地方，并不在EMPTY_TABLE数组中（进行扩容时，长度必须为2的n次方） */
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
/** HashMap实际存储的元素个数 */
transient int size;
/** 临界值（HashMap实际存储的大小），公式为(threshold = capacity * localFactor)  用于判断是否需要调整HashMap的容量 */
int threshold;
/** 负载因子 */
final float loadFactor;
/** HashMap的结构被修改的次数，用于迭代器 */
transient int modCount;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

构造方法

源码分析：

// 指定初始容量和负载因子
public HashMap(int initialCapacity, float loadFactor) {
  // 判断设置的容量和负载因子合不合理
  if(initialCapacity < 0) 
      throw new IllegaArgumenyException("Illegal initial capacity：" + initialCapacity);
  if(initialCapacity > MAXIMUM_CAPACITY)
      initialCapacity = MAXIMUM_CAPACITY;
  if(loadFactor <= 0 || Float.isNaN(loadFactor))
      throw new IllegalArgumentException("Illegal load factor：" + loadFactor);
  // 设置负载因子，临界值此时为容量大小，后面第一次 put时由inflateTable(int toSize)方法计算设置
  this.loadFactor = loadFactor;
  // 初始容量
  threshold = initialCapacity;
  // 不做任何操作
  init();
}
// 指定初始容量
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 使用默认的容量大小和负载因子，并调用其他的构造方法
public HashMap() {
  this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 参数为指定的Map集合对象
public HashMap(Map<? extends K, ? extends V> m) {
  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
  inflateTable(threshold);
  putAllForCreate(m);
}

内部类/内部方法

private static class Holder {
  /**
   *  Table capacity above which to switch to use alternative hashing.
   */
  static final int ALTERNATIVE_HASHING_THRESHOLD;
  static {
    String altThreshold = java.security.AccessController.doPrivileged(new sun.security.action.GetPropertyAction("jdk.map.althashing.threshold"
));  // 读取
    int threshold;
    try {
      // 修改值
      threshold = (null != altThreshold) ? Intrger.parseInt(altThreshold) : ALTRENATIVE_HASHING_THRESHOLD_DEFAULT;
      // disable alternative hashing if -1
      if (threshold == -1) {
        // 设置Integet的最大值
        threshold = Integer.MAX_VALUE;
      }
      if (threshold < 0) {
        throw new IllegalArgumentException("value must be positive integet.");
      }
    } catch (IllegArgumentException failed) {
      throw new Error("Ill");
    }
    // 赋值 返回
    ALTERNATIVE_HASHING_THRESHOLD = threshold;
  }
}
// 选择合适的容量值，最好是number的2的幂数
private static int roundUpToPowerOf2(int number) {
  // assert number >= 0 : "number must be non-negative";
  return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 扩充表，HashMap初始化时是一个空数组，此方法执行重新复制操作，创建一个新的Entry[]
private void inflateTable(int toSize) {
  // Find a power of 2 >= toSize
  // capacity为2的幂数，大于等于toSize
  int capacity = roundUpToPowerOf2(toSize);
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  // 新建数组，并重新赋值
  table = new Entry[capacity];
  // 修改hashSeed
  initHashSeedAsNeeded(capacity);
}
// 与虚拟机设置有关，改变hashSeed的值
final boolean initHashSeedAsNeeded(int capacity) {
  boolean currentAltHashing = hashSeed != 0;
  boolean useAltHashing = sum.music.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  boolean switching = currentAltHashing ^ useAltHashing;
  if (switching) {
    hashSeed = useAltHashing ? sum.misc.Hashing.randomHashSeed(this) : 0;
  }
  return switching;
}
// 计算k的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();// 等同于h = 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);
}

put方法

put() 过程：

image.png

put() 源码分析：

public V put(K key, V value) {
  // 如果table引用指向成员变量EMPTY_TABLE，那么初始化HashMap（设置容量、临界值，新的Entry数组引用）
  if(table == EMPTY_TABLE) {
    inflateTable(threshold);
  }
  // 若"key为null"，则将该键值对添加到table[0]处，遍历该链表，如果有key为null，则将value替换。没有就创建新Entry对象放在链表表头。
  // 所以table[0]的位置上，永远最多存储一个Entry对象，形成不了链表。 key为null的Entry存在这里。
  if(key == null)
    return putForNullKey(value);
  // 若"key部位null"，则计算该key的哈希值
  int hash = hash(key);
  // 搜索指定hash值在对应table中的索引
  int i = indexFor(hash, table.length);
  // 循环遍历table数组上的Entry对象，判断该位置上的key是否已存在
  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))) {
      // 如果这个key对应的键值对以及存在，就用新的value代替老的value，然后退出！！！
      V oldVlue = e.value;
      e.value = value;
      e.recordAccess(this); // 空方法
      return oldVlue;
    }
  }
  // 修改次数 +1
  modCount++;
  // table数组中没有key对应的简直对，就将key-value添加到table[i]处
  addEntry(hash, key, value, i);
  return null;
}

根据以上代码可知：

• 当我们给put()方法传递键和值时，HashMap会由key来调用hash()方法，返回键的hash值，计算Index后用于找到bucket（哈希桶）的位置来存储Entry对象。
• 如果两个对象的key的hash值相同，那么他们的bucket位置也相同，但equals()不相同，添加元素时会发生hash碰撞，也叫hash冲突，HashMap使用链表来解决碰撞问题。
• 分析源码可知，put() 时，HashMap会先遍历table数组没用hash值和equals()判断数组中是否存在完全相同的key对象，如果这个key对象在table数组中以及存在，就用新的value代替老的value。如果不存在，就创建一个新的Entry对象添加到table[i]处。
• 如果该table[i]以及纯真其他元素，那么新的Entry对象将会存储在bucket链表的表头，通过next指向原有的Entry对象，形成链表结构（hash碰撞解决方案）。

// key = null对应的操作，key为null，存放在entry[]中的0号位置，并用新值替换旧值
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);
      retuen oldValue;
    }
  }
  modCount++;
  addEntry(0, null, value, 0);
  return null;
}
// 私有方法，添加元素
private void putForCreate(K key, V value) {
  // 计算hash值
  int hash = null == key ? 0 : hash(key);
  // 计算在HashMap中的存储位置
  int i = indexFor(hash, table.length);
  // 遍历i所在位置的链表
  for (Entry<K, V> e = table[i]; e != null; e = e.next) {
    Object k;
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
      e.value = value;
      return ;
    }
  }
  // 创建Entry链表，存放链表
  createEntry(hash, key, value, i);
}
// 将传入的map添加到HashMap中
private void putAllForCreate(Map<? extends K, ? extends V> m) {
  for (Map.Entry<? extends K, ? extends V> e : e.entrySet()) {
    putForCreate(e.getKey(), e.getValue());
  }
}
// 将传入map参数中的元素全部添加到HashMao中
public void putAll(Map<? extends K, ? extends V> m) {
  int numKeysToBeAdded = m.size();
  if (numKeysToBeAdded == 0) {
    return ;
  }
  if (table == EMPTY_TABLE) {
    inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
  }
  // 判断是否需要扩容
  if (numKeysToBeAdded > threshold) {
    int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
    if (targetCapacity > MAXIMUM_CAPACITY)
      targetCapacity = MAXIMUM_CAPACITY;
    int newCapacity = table.length;
    while (newCapacity < targetCapacity) 
      newCapacity <<= 1;
    if (newCapacity > table.length) 
      resize(newCapacity);
  }
  // 添加元素
  for (Map<? extends K, ? extends V> e : m.entrySet())
    put(e.getKey(), e.getValue()); 
}

Entry 数据结构源码（HashMap内部类）：

static class Entry<K, V> implements Map.Entry<K, V> {
  final K key;
  V value;
  /** 指向下一个元素的引用（链表后置节点） */
  Entry<K, V> next;
  int hash;
  /**
   * 构造方法为Entry赋值
   */
  Entry(int h, K k, V v, Entry<K, V> n) {
    value = v;
    next = n;  // 头插法：newEntry.next = e
    key = k;
    hash = h;
  }
  ...
  ...
}

形成单链表的核心代码如下：

/**
 *  将Entry添加到数组bucketIndex位置对应的哈希桶中，并判断数组是否需要扩容
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
  // 如果数组长度大于等于容量*负载因子，并且要添加的位置为null
  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);
}
/**
 *  在链表中添加一个新的Entry对象在链表的表头
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
  // 取出原bucket链表
  Entry<K, V> e = table[bucketIndex];
  // 头插法
  table[bucketIndex] = new Entry<>(hash, key, value, e);
}

什么是链表?

       链表是由一系列非连续的节点组成的存储结构，简单分类的话，连边又可以分为单向链表和双向链表，而单向/双向链表又可分为循环链表和非循环链表。

1.单向链表

       单向链表是通过每个节点的指针指向下一个节点从而连接起来的结构，最后一个节点的next指向null。

image.png

2.单向循环链表

       单向循环链表和单向链表不同的是，最后一个节点的next不是指向null，而是指向head节点，形成一个"环"。

image.png

3.双向链表

       双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点的next指向null。

image.png

4.双向循环链表

       双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成了一个"环"。LinkedList就是基于双向循环链表设计的。

image.png

put() 方法执行过程：

image.png

get方法

如果两个不同的key的hashCode相同，两个值对象存储在同一个bucket位置，要获取value，我们调用get()方法，HashMap会使用key的hashCode找到bucket位置，因为HashMap在链表中存储的是Entry键值对，所以找到bucket位置之后，会调用key的equals()方法，按顺序遍历链表的每个Entry，直到找到想获取的Entry为止。——如果恰好要搜索的Entry位于该Entry链表的最末端（该Entry是最早放入带bucket中），那么HashMap必须循环到最后才能找到该元素。
get() 方法源码如下：

public V get(Object key) {
  // 若key为null，遍历table[0]处的链表（实际上要么没有元素，要么只有一个Entry对象），取出key为null的value
  if(key == null)
    return getForNullKey(key);
  // 若key不为null，用key获取Entry对象
  Entry<K, V> entry = getEntry(key);
  // 若链表中找到的Entry不为null，返回该Entry中的value
  return null == entry ? null : entry.getValue();
}
// 返回null键的值
private V getForNullKey() {
  if (size == 0) {
    return null;
  }
  for (Entry<K, V> e = table[0]; e != null; e = e.next) {
    if (e.key == null)
      return e.value; 
  }
  return null;
}
// 是否包含键位key的元素
public boolean containsKey(Object key) {
  return getEntry(key) != null;
}
// 返回键为key的entry，不存在返回null
final Entry<K, V> getEntry(Object key) {
  // 判断HashMap中是否存在Entry元素
  if(size == 0) {
    return null;
  }
  // 计算key的hash值
  int hash = (key == null) ? 0 : hash(key);
  // 计算key在数组中对应位置，遍历该位置的链表
  for(Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
    Object k;
    // 若key完全相同，返回链表中对应的Entry对象
    if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) 
      return e;
  }
  // 链表中没有找到对应的key，返回null
  return null;
}

三、hash算法

可以看出，在HashMap中找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合体，所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表。

源码分析：

/**
 * Return index for hash code h.
 */
static int indexFor(int h, int length) {
  // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
  // 根据hash与数组长度mod运算
  return h & (length - 1);
}

四、性能问题

HaspMap有两个参数影响其性能：初始容量和负载因子。均可以通过构造方法指定大小。

• 容量capacity是HashMap中bucket哈希桶（Entry的链表）的数量，初始容量只是HashMap在创建时的容量，最大设置初始容量是2^30，默认初始容量是16（必须为2的幂次方），解释一下，当数组长度为2的n次幂的时候，不同的key通过indexFor()方法算的数组位置相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，get()的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
• 负载因子loadFactor是HashMap在其容量自动增加之前可以达到多曼的一种尺度，默认值是0.75。

扩容机制

当HashMap的长度超出了负载因子与当前容量的乘积（默认为16*0.75=12）时，通过调用resize()方法重新创建一个原来HashMap大小的两倍的newTable数组，最大扩容到2^30+1，并将原先table的元素全部移到newTable里面，重新计算hash，然后再重新根据hash分配位置。这个过程叫做rehash，因此它调用hash方法找到新的bucker位置。

扩容机制源码分析：

void resize(int newCapacity) {
  // 拿到当前HashMap
  Entry[] oldTable = table;
  // 拿到当前HashMap容量
  int oldCapacity = oldTable.length;
  // 如果之前的HashMap已经扩充到最大了，那么就将临界值threshold设置为最大的int值
  if(oldCaoacity == MAXIMUM_CAPACITY) {
    threshold = Intrger.MAX_VALUE;
    retutn ;
  }
  // 根据新传入的newCapacity创建新Entry数组
  Entry[] newTable = new Entry[newCapacity];
  // 用来将原先table的元素全部移到newTable里面，重新计算hash，然后再重新根据hash分配位置
  transfer(newTable, initHashSeefAsNeeded(newCapacity));
  // 再将newTable赋值给table
  table = newTable;
  // 重新计算临界值，扩容公式（newCapacity * loadFactor）
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
  // 拿到扩容后的容量
  int newCapacity = newTable.length;
  // 遍历HashMap
  for(Entry<K, V> e : table) {
    while(null != e) {
      Entry<K, V> next = e.next;
      if(rehash) {
        e.hash = null == e.key ? 0 : hash(e.key);
      }
      // 重新根据新的数组长度计算位置（同一个bucket上元素hash相等，所以扩容后必然还在一个链表上）
      int i = indexFor(e.hash, newCapacity);
      // 头插法（同一位置上新元素总会被放在链表的头部位置），将newTable[i]的引用赋值给了e.next
      e.next = newTable[i];
      // 将元素放在数组中
      newTable[i] = e;
      // 访问下一个元素
      e = next;
    }
  }
}

扩容问题：

• 数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这个操作时机器消耗性能的/所以如果我们已经预知HashMap中元素的个数，那么预设初始容量能够有效的提高HashMap的性能。
• 重新调整HashMap大小，当多线程的情况下可能产生条件竞争。因为如果两个线程都发现HashMap需要重新调整大小了，他们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在了头部，这是为了避免尾部遍历（tail traversing）。如果条件竞争发生了，那么就死循环了。

五、线程安全

• HashMap 是非线程安全的。
• 在多线程环境下，推荐使用java.util.concurrent.ConcurrentHashMap，相对安全，效率高。

Jdk 1.8

HashMap 继承图

image.png

HashMap根据键的hashCode值存储数据，在绝大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但便利顺序却是不确定性的。HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap是非线程安全的，即任意时刻可以又多个线程同时写HashMap，可能回导致数据的不一致性。如果需要满足线程安全，可以使用Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

一、数据结构

HashMap是数组+链表+红黑树实现的。如图所示：

image.png

二、实现原理

源码分析如下：

// Node<K, V> 类用来实现数组以及链表的数据结构
static class Node<K, V> implements Map.Entry<K, V> {
  // 保存节点的hash值
  final int hash;
  // 保存节点的key值
  final K key;
  // 保存节点的value值
  V value;
  // 指向链表结构下的当前节点的next节点，红黑树TreeNode节点中也有用到
  Node<K, V> next;
  // 构造函数
  Node(int hash, K key, V value, Node<K, V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
  }
  public final K getKey() {
  }
  public final V getValue() {
  }
  public final String toString() {
  }
  public final int hashCode() {
  }
  public final V setValue(V value) {
  }
  public final boolean equals(Object o) {
  }
}
public class LinkedHashMap<K, V> {
  static class Entry<K, V> extends Hash.Node<K, V> {
    Entry<K, V> before, after;
    Entry(int hash, K key, V value, Node<K, V> next) {
      super(hash, key, value, next);
    }
  }
}
// TreeNode<K, V>继承LinkedHashMap.Entry<K, V>，用来实现红黑树相关的存储结构
static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {
  // 存储当前节点的父节点
  TreeNode<K, V> parent;
  // 存储当前节点的左节点
  TreeNode<K, V> left;
  // 存储当前节点的右节点
  TreeNode<K, V> right;
  // 存储当前节点的前一个节点
  TreeNode<K, V> prev;
  // 存储当前节点的颜色（红色、黑色）
  boolean red;
  // 构造函数
  TreeNode(int hash, K key, V value, Node<K, V> next) {
    super(hash, key, value, next);
  }
}

成员变量

源码分析：

// 创建HashMap时未指定初始容量情况下的默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// HashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// HashMap 默认的装载因子，当HashMap中元素数量超过 容量*装载因子 时，进入resize()操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 用来确定何时将解决hash冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 用来确定合适将解决hash冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 当需要将解决hash冲突的链表转变为红黑树时，需要判断下此时的数组容量，若是由于数组容量太小（小于MIN_TREEIFY_CAPACITY）导致的hash冲突太多，则不进行链表转变为红黑树操作，转为利用resize()函数对HashMap扩容
static final int MIN_TREEIFY_CAPACITY = 64;
// 保存Node<K, V>节点的数组
transient Node<K, V>[] table;
// 由HashMap中的Node<K, V>节点构成的set
transient Set<Map.Entry<K, V>> entrySet;
// 记录HashMap当前存储的元素的数量
transient int size;
// 记录HashMap发生结构性变化的次数（value的夫噶不属于结构性变化）
transient int modCount;
// threshold 的值应等于table.length * loadFactor，size超过这个值时进行resize()扩容操作
int threshold;
// 记录HashMap装载因子
final float loadFactor;

构造方法

// 指定初始容量及装载因子
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.loadFacor = loadFactor;
  // 注意此种方法创建的HashMap初始容量的值存在threshold中
  // tableSizeFor(initialCapacity)方法返回值时最接近initialCapacity的2次幂，若制定容量为9，则实际HashMap的容量为16
  this.threshold = tableSizeFor(initialCapacity);
}
// 返回值时最接近initialCapacity的2次幂
static final int tableSizeFor(int capacity) {
  int n = capacity - 1;
  // >>>代表无符号右移
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUN_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// 指定初始容量，装载因子采用默认的0.75f
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 所有的参数均采用默认值
public HashMap() {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
}

put方法

源码分析：

// 指定节点key，value向HashMap中插入节点
public V put(K key, V value) {
  // 注意待插入节点时hash值的计算，调用了hash(key)函数
  // 实际调用了putVal()进行节点的插入
  return putVal(hash(key), key, value, false, true);
}
// hash值计算
static final int hash(Object key) {
  int h;
  // key的hash值计算时通过hashCode()的高16位异或或低16位实现：(h = key.hashCode()) ^ (h >>> 16)
  // 主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会由太大的开销
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public void putAll(Map<? extends K, ? extends V> map) {
  putMapEntries(map, true);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evicat) {
  // 获取插入的节点大小
  int s = m.size();
  if(s > 0) {
    // 如果是在创建HashMap的时候调用这个函数，则table一定为空
    if(table == null) {
      // 根据带插入的map的size计算要创建的HashMap的容量
    float ft = ((float)s / loadFactor) + 1.0F;
    int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
    // 将需要创建的HashMap的容量存于threshold中
    if(t > threshold)
      threshold = tableSizeFor(t);
    }
    // 判断插入的map的size，若size大于threshold，则先进行resize()
    else if(s > threshold)
      resize();
    for(Map.Entry<? extends K, ? exends V> e : m.entrySet()) {
      K key = e.getKey();
      V value = e.getValue();
      // 实际也是调用putVal()函数进行元素的插入
      putVal(hash(key), key, value, false, evict);
    }
  }
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
  Node<K, V> tab;
  Node<K, V> p;
  int n, i;
  if((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length; 
  // 根据hash值确定节点在数组中的插入位置，若此位置没有元素则进行插入，注意确定插入位置所用的计算方法为(n - 1) & hash，由于n一定是2的幂次，这个操作相当于hash % n
  if((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {  // else则说明插入位置存在元素
    Node<K, V> e;
    K k;
    // 比较原来元素与待插入元素的hash值与key值
    if(p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 若原来元素是红黑树节点，调用红黑树的插入方法：putTreeVal
    else if(p instanceof TreeNode)
      e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);  
    else {  // 证明原来的元素是链表的头节点，从此节点开始向后寻找合适插入位置
      for(int binCount = 0; ; ++binCount) {
        if((e = p.next) == null) {
          // 找到插入位置后，新建节点插入
          p.next = newNode(hash, key, value, null);
          // 若链表上节点超过TREEIFY_THRESHOLD - 1，将链表转变为红黑树
          if(binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash); 
          break;
        }
        if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e; 
      }
    }
    // 待插入元素在HashMap中已存在
    if(e != null) {
      V oldValue = e.value;
      if(!onlyIfAbsent || oldValue == null) 
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  // 标记结构变化+1
  ++modCount;
  if(++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null; 
}
/**  hash冲突发生的几种情况：
 *  1、两节点  key相同（hash值不一定相同），导致冲突。
 *  2、两节点  key不相同，由于hash函数的局限性导致hash值相同，导致冲突。
 *  3、两节点  key不相同，hash值不同，但hash值对数组长度取模后相同，导致冲突。
 */
final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) {
  Class<?> kc = null;
  boolean searched = false;
  TreeNode<K, V> root = (parent != null) ? root() : this;
  // 从根节点开始查找合适的插入位置（与二叉搜索树查找过程相同）
  for(TreeNode<K, V> p = root;;) {
    int dir, ph;
    K pk;
    if((ph = p.hash) > h) 
      // dir 小于0，接下来查找当前节点左孩子节点
      dir = -1;
    else if(ph < h)
      // dir大于0，接下来查找当前节点右孩子节点
      dir = 1;
    else if((pk = p.key) == k || (pk != null && k.equals(pk)))
      // 进入这个else if则代表hash值相同，key相同
      return p;
    /** 下面的几个else if所代表的含义 
     *  1、当前节点与待插入节点key不同，hash相同
     *  2、k是不可比较的，即k并未实现comparable<K>接口
     *    （若k实现了comparable<K>接口，comparableClassFor(k)返回的是k的class,而不是null）或者compareComparables(kc, k, pk)返回值为0
     *    （pk为空或者按照k.compareTp(pk)返回值为0，返回值为0可能是由于k的compareTo方法不当引起的，compareTo判断相等，而上个else if中equals判断不等）
     */
    else if((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k , pk)) == 0) {
      // 在以当前节点为跟的整个树上搜索是否存在待插入节点（只会搜索一次）
      if(!searched) {
        TreeNode<K, V> q, ch;
        searched = true;
        if(((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null))
          // 若树中存在待插入节点，直接返回
          return q; 
      }
      // 既然k是不可比较 的，那自己就指定一个比较方式
    dir = tieBreakOrder(k, pk);
    }
    TreeNode<K, V> xp = p;
    if((p = (dir <= 0) ? p.left : p.right) == null) {
      // 找到了待插入的位置，xp为待插入节点的父节点
      // 注意TreeNode节点中即存在树状关系，也存在链表关系，并且是双端链表
      Node<K, V> xpn = xp.next;
      TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
      if(dir <= 0)
        xp.left = x;
      else 
        xp.right = x;
      xp.next = x;
      x.parent = x.prev = xp;
      if(xpn != null)
        ((TreeNode<K, V>)xpn).prev = x;
      // 插入节点后进行二叉树的平衡操作
      moveRootToFront(tab, balanceInsertion(root, x));
      return null; 
    }
  }
}
static int tieBreakOrder(Object a, Object b) {
  int d;
  // System.identityHashCode() 实际是利用对象a，b的内存地址进行比较
  if(a == null || b == null || (d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)
     d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1);
  return d;
}

get方法

源码分析：

public V get(Object key) {
  Node<K, V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K, V> getNode(int hash, Object key) {
  Node<K, V> tab;
  Node<K, V> first, e;
  int n;
  K k;
  if((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
    if(first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    if((e = first.next) != null) {
      if(first instanceof TreeNode)
        // 若定位到的节点是TreeNode节点，则在树中进行查找
        return ((TreeNode<K, V>)first).getTreeNode(hash, key); 
      // 否则在链表中进行查找
      do {
        if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while((e = e.next) != null);
    } 
  } 
  return null;
}
final TreeNode<K, V> getTreeNode(int h, Object k) {
  // 从根节点开始，调用find方法进行查找
  return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
  TreeNode<K, V> p = this;
  do {
    int ph, dir;
    K pk;
    TreeNode<K, V> pl = p.left, pr = p.right, q;
    // 首先进行hash值的比较，若不同令当前节点变为它的左孩子节点或者右孩子节点
    if((ph = p.hash) > h)
      p = pl;
    else if(ph < h) 
      p = pr;
  // hash值相同，进行key值的比较
  else if((pk = p.key) == k || (k != null && k.equals(pk))) 
    return p;
  else if(pl == null) 
    p = pr;
  else if(pr == null) 
    p = pl;
  // 执行到该处，则表示hash值相同，key值不同
  // 若k是可比较的并且k.compareTo(pk)返回结果不为0即可进入下面的else if
  else if((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
    p = (dir < 0) ? pl : pr;
  // 若k是不可比较的或者k.compareTo(pk)返回结果为0则在整棵树中进行查找，先找右子树，右子树不存在则找左子树
  else if((q = pr.find(h, k, kc)) != null)
    return q;
  else 
    p = pl;
  } while(p != null);
  return null;
}

扩容机制

resize()方法中比较重要的就是链表和红黑树的rehash操作。
rehash的实现原理：

• 在扩容的时候，一般是把长度扩容为原来的2倍，元素的位置要么是在原位置，要么就是子啊原位置在移动2次幂的位置。如下图所示，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

  
  
  image.png
  
  

  元素在重新计算has之后，因为n变为2倍，那么n-1的mask范围在高位多1bit（红色），因此新的index就会发生这样的变化：

  
  
  image.png
  
  我们在扩容HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引就变成了“原索引+oldCap”，可以看看下图为16扩容为32的resize示意图：
  
  image.png
  
  

  整个算法很巧妙，既省去了重新计算hash值的时间，同时由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到了新的槽中了。

扩容机制源码分析：

final Node<K, V> resioze() {
  Node<K, V>[] oldTab = table;
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  int oldThr = threshold;
  int newCap, newThr = 0;
  /**
   *  1、resize()函数在size > threshold时被调用。
   *  oldCap大于0代表原来的table表非空，oldCap为原表的大小，
   *  oldThr(threshold)为oldCap * load_factor
   **/
  if (oldCap > 0) {
    if (oldCap >= MAXIMUN_CAPACITY) {
      threshold = Integer.MAX_VALUE;
      return oldTab;
    } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1;// double threshold
  }
  /**
   *  2、resize()函数在table为空时被调用。
   *  oldCap小于等于0且oldThr大于0，代表用户创建了一个HashMap，
   *  但是使用的构造函数为HashMap(int initialCapacity, float loadFactor) 或者HashMap(int initialCapacity) 或者HashMap(Map<? extends K, ? extends V> m)，
   *  导致oldTab为null，oldCap为0，oldThr为用户指定的HashMap的初始容量。
   **/
  else if (oldThr > 0)  // initial capacity was placed in threshold
    newCap = oldThr;
  /**
   *  3、resize()函数在table为空时被调用。
   *  oldCap小于等于0且oldThr等于0，用户调用HashMap构造函数创建的HashMap，所有值均采用默认值
   *  oldTabl(table) 表为空，oldCap为0，oldThr等于0
   **/
  else {  // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)
  }
  if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
  }
  threshold = newThr;
  Node<K, V>[] newTab = (Node<K, V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    // 把oldTab中的节点rehash到newTab中去
    for (int j = 0; j < oldCap; ++j) {
      Node<K, V> e;
      if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        // 若节点时单个节点，直接在neTab中进行重定位
        if (e.next == null)
          newTab[e.hash & (newCap - 1)] = e;
        //  若节点时TreeNode节点，要进行红黑树的rehash操作
        else if (e instanceof TreeNode)
          ((TreeNode<K, V>)e).split(this, newTab, j, oldCap);
        // 若是链表，进行链表的rehash操作
        else {  // preserve order
          Node<K, V> loHead = null, loTail = null;
          Node<K, V> hiHead = null, hiTail = null;
          Node<K, V> next;
          do{
            next = e.next;
            // 根据算法 e.hash & oldCap 判断节点位置 rehash后是否发生改变
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else 
                loTail.next = e;
              loTail = e;
            } else {
              if (hiTail == null)
                hiHead = e;
              else 
                hiTail.next = e;
              hiTail = e; 
            }
          } while((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            // rehash后节点新的位置一定为原来基础上加上oldCap
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}
// 对红黑树进行rehash操作
final void split(HashMap<K, V> map, Node<K, V>[] tab, int index,int bit) {
  TreeNode<K, V> b = this;
  // relink into lo and hi lists, preserving order
  TreeNode<K, V> loHead = null, loTail = null;
  TreeNode<K, V> hiHead = null, hiTail = null;
  int lc = 0, hc = 0;
  // 由于TreeNode节点之间存在双端链表的关系，可以利用链表关系进行rehash
  for(TreeNode<K, V> e = b, next; e != null; e = next) {
    next = (TreeNode<K, V>)e.next;
    e.next = null;
    if ((e.hash & bit) == 0) {
      if ((e.prev = loTail) == null)
        loHead = e;
      else 
        loTail.next = e;
      loTail = e;
      ++lc; 
    } else {
      if ((e.prev = hiTail) == null)
        hiHead = e;
      else 
        hiTail.next = e;
      hiTail = e;
      ++hc; 
    }
  }
  // rehash操作之后注意根据链表长度进行untreeify或者treeify操作
  if (loHead != null) {
    if (lc <= UNTREEIFY_THRESHOLD)
      tab[index] = loHead.untreeify(map);
    else {
      tab[index] = loHead;
      if (hiHead != null)  // else is already treeified
        loHead.treeify(tab);
    }
  }
  if (hiHead != null) {
    if (hc <= UNTREEIFY_THRESHOLD)
      tab[index + bit] = hiHead.untreeify(map);
    else {
      tab[index + bit] = hiHead;
      if (loHead != null)
        hiHead.treeify(tab);
    }
  }
}