• 前言
• HashMap
• HashMap类继承图
• HashMap属性
• HashMap构造函数
  • HashMap(int initialCapacity, float loadFactor)
  • HashMap(Map<? extends K, ? extends V> m)
• HashMap常见Api解析
  • put(K key, V value)
  • putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
  • Node<K,V>[] resize()
  • get(Object key)
  • remove(Object key)
  • removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)
• HashMap与HashTable对比
• 总结

前言

本文基于jdk1.8

HashMap

先来看一下Java官方描述

• 基于哈希表的 Map 接口的实现。
• 允许使用 null 值和 null 键。
• 除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。
• 不保证映射的顺序，特别是它不保证该顺序恒久不变（扩容后元素在底层会重散列）。
• 迭代所需的时间与 HashMap实例的“容量”（桶的数量）及键-值映射数成比例。即初始容量设置得太高（或将负载因子设置得太低）对遍历的性能影响都很大。
  • 负载因子 = 总键值对数 / 箱子个数(数组元素)
• HashMap 的实例有两个参数影响其性能：初始容量 和负载因子。当元素个数超过当前容量(桶数)与负载因子的乘机时，哈希表会对其元素rehash，底层的桶数*2。
• 默认负载因子(0.75)，加载因子过高虽然减少了空间开销，但同时也增加了查询成本。在设置初始容量时应该考虑到Map中所要容纳的元素数量及其加载因子，以便最大限度地减少rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生rehash操作。
• 如果从一开始就知道有多少元素要存到Map中，最好一开始就指定好Map初始容量，尽量避免其rehash操作。性能会大大提高
• 此实现不是同步的。想要同步在一些列操作外手动同步，或者使用Map m = Collections.synchronizedMap(new HashMap(...));方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问

HashMap类继承图

• 实现了Serializable，Cloneable接口
• 继承了父类AbstractMap

image

HashMap属性

静态属性：

• DEFAULT_INITIAL_CAPACITY: 初始容量，也就是默认会创建 16 个箱子，箱子的个数不能太多或太少。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。
• MAXIMUM_CAPACITY: 哈希表最大容量，一般情况下只要内存够用，哈希表不会出现问题。
• DEFAULT_LOAD_FACTOR: 默认的负载因子。因此初始情况下，当键值对的数量大于 16 * 0.75 = 12 时，就会触发扩容。
• TREEIFY_THRESHOLD: 上文说过，如果哈希函数不合理，即使扩容也无法减少箱子中链表的长度，因此 Java 的处理方案是当链表太长时，转换成红黑树。这个值表示当某个箱子中，链表长度大于等于 8 时，有可能会转化成树。
• UNTREEIFY_THRESHOLD: 在哈希表扩容时，如果发现链表长度小于 6，则会由树重新退化为链表。
• MIN_TREEIFY_CAPACITY: 在转变成树之前，还会有一次判断，只有键值对数量大于 64 才会发生转换。这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。

成员属性：

image

• table：HashMap的链表数组。它在自扩容时总是2的次幂
• entrySet: HashMap实例中的Entry的Set集合。
• size: HashMap实例中映射的数量
• modCount: 这个HashMap被结构修改的次数
• threshold: 元素的阈值
• loadFactor: 哈希表的负载因子

HashMap简单总结：

• 存取无序
• 键值允许为NULL
• 非同步类
• 底层是哈希表
• 初始容量和装载因子是决定整个类性能的关键点。

HashMap构造函数

HashMap的构造函数共4个。

image

HashMap(int initialCapacity, float loadFactor)

我们可以看到loadFactor参数Java官方还对其进行了Float.NaN(0.0f/0.0f)的判断。可以说考虑的非常周到了

同时在构造函数的最后一行，在为threshold赋值的时候，调用了tableSizeFor()函数来对输入的初始容量进行判断，来保证该初始容量是2的整数次幂。

image

函数具体释义可参考：HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）

• 此时不经要想为什么是将2的整数幂的数赋给threshold？

首先我们先来了解一下threshold这个属性：

image

threshold这个成员变量是阈值，决定了是否要将散列表扩容充重散列。它的值应该是：(capacity * loadfactor）才对的。

• 那我们就更奇怪了，那这里还给他赋值干什么？

其实这里仅仅是对该值的一个初始化，tableSizeFor函数赋予了该值一个最接近initialCapacity值的2的整数幂的值，当调用putVul函数需要往元素容器中真正添加元素的时候，也就是真正创建哈希表的时候，该值才会在resize函数中根据一些条件判断来重新定义赋值的。

HashMap(Map<? extends K, ? extends V> m)

image

这个构造函数其实本质上和刚才我们所看的给初始容量和负载因子的构造函数一致。函数最终做的除了参数上可以看出来的，把一个Map实例中的元素都插入到HashMap实例中外，由于负载因子没有显示指定所以赋予了loadFactory默认值。

并且把具体的Map迭代放在了调用的putMapEntries函数中。从该函数注释中看出，该函数是服务于putAll函数和constructor构造函数的。

从putMapEntries函数注释中也可以看出，如果这个函数在初始化Map时被调用evict参数传入的是false。而如果这个函数是在afterNodeInsertion函数后调用的，那么则需要传入的是true。

从putMapEntries函数的具体代码实现上可以看出，其在Map第一次初始化的时候和我们刚才所看的构造函数一致，都是在真正构造HashMap前先为阈值赋予一个可靠地初值。然后才迭代入参map集合，将其元素都插入到HashMap中。

其余的构造函数都是大同小异。就不一一赘述了

总结：

从构造函数中我们可以看出，HashMap的构造函数其实工作就只有一个。赋值

• 赋值负载因子
• 赋值阈值

HashMap常见Api解析

put(K key, V value)

 /**
 * 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.
 *
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

可以看出put函数具体实现其实是调用了putVal函数。并且从注释中可以得知如果该映射存在，新值会替换掉旧值。

还可以看到的是传入了5个参数，我们来了解简单一下这5个参数。

 /**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {

注释很直白解释的很清楚，按序号来

1. key的哈希值
2. key
3. value
4. 如果映射存在不替换原值？
5. 如果是false，代表当前HashMap正处于创建阶段。

我们大概知道了这5个参数是干嘛的了，就可以针对第一个参数具体的去了解一下key的哈希值是如何计算得了。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里就比较疑惑了，为什么不直接用key类型对应的hashcode函数直接得到对应的哈希码呢？从这段代码可以看出来Java官方拿key的哈希码和其哈希码向右移位16位的结果进行异或操作。我们知道右移高位补0，由于哈希码返回的是一个4字节32位int类型的值。所以总共可以看成是高16位，低16位组成的。

而这里对其哈希码进行右移16位之后高位空缺补0，原高位到了现低位。然后再拿原哈希码与现哈希码进行异或操作，而我们知道任何数跟0异或都是其本身。所以可以看出Java官方最终目的，是想让哈希码原低16位与其高16位进行异或操作。而原高16位却不变，原来如此~

image

但为什么要这样呢？

其实这个与HashMap中元素插入时对应位置table数组下标的计算有关。

image

核心代码：

n = (tab = resize()).length;
i =（n-1） & hash

我们暂且不看resize函数，putVal函数在初次进来的时候该resize函数做的其实就是哈希表初始化的工作。由于DEFAULT_INITIAL_CAPACITY变量的存在，我们暂且认为该哈希表的大小length为16。即n=16

那么在计算元素插入位置的时候，由于底层是数组。所以真正存储的位置就是[0-15]。所以n-1。

而因为，table的length属性都是2的幂，因此i仅与hash值的低n位有关（此n非table.length，而是2的幂指数）
假设table.length=2^4=16。

image

由上图可以看到，32位的hash值只有低4位参与了运算。
仅有4位的异或很容易产生碰撞。但是由于table.length的大小只能由插入数据的多少来改变，而hash值得高16位又由于与操作置0了，所以设计人员相出一个好办法就是通过对key的hash值进行高16位与低16位异或来将高位与低位整合。这样不但可以保留原来key哈希值的差异性(高位地位同时作用)，同时来增加低16位2进制数值在计算时的差异性进而减少这种哈希冲突的情况。

参考：HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四）

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

接下来便可以继续分析真正的put函数了。

总结下来就是：

• 散列表初次put数组任为NULL时，调用resize函数(单独拉出来说)来初始化散列表
• 当根据元素的哈希值可以确认分配到散列表的下标时，如果此处没有元素，那么就直接插入
  • 当该元素就是和我一样的元素。即此处元素的hash值和key值都与要插入的元素相等时。通过变量e指向该元素。
  • 当该元素已经不是一个链表结构而是一个红黑树结构的时候(元素肯定过6)，将该元素插入到红黑树中，并用e指向该元素
  • 否则该处就是一个链表，链表头结点不是要插入的元素，但不能排除其他节点不是。所以然后遍历这个数组，当该链表中遍历到的节点的下一节点为空时将该元素插入到链表尾，循环跳出。如果不为空的话，对下一节点进行判断看是否是待插入节点。如果是跳出
• 程序进行到绿框时，此时程序只有两种情况。元素最后找到空出插入了，但是e无法指向。或者说元素找到和自己一样的元素了，并且由变量e指向。
  • 新旧值替换，根据函数一开始传入的参数onlyIfAbsent或者oldValue的特殊情况来决定是否替换。
    • key对应的旧值如果为NULL，那么无论onlyIfAbsent是否决定替换。都将被替换。
    • key对应的旧值如果不为NULL，那么如果onlyIfAbsent是false就替换。
  • 最后返回被替换掉的值。
• 修改了实例结构所以modCount+1。
• 加入元素后判断元素个数是否超过了阈值。如果是resize函数扩桶数

这样我们的putVal函数其实思路就理清了，看上去很复杂，其实宗旨没变，也就是判断，扩容，找位置，去除特殊情况，元素插入，只不过数据结构的差异性导致其特殊情况较多，判断的复杂了些。接下来该分析resize函数了。我们可以明显的看到putVal函数多出调用了resize函数。所以要想彻底理清HashMap实例是如何构建的，resize函数必然需要了解一下。

目前对resize的了解：table==null时，调用resize初始化table。元素数量>=threshold时，调用resize扩容。

Node<K,V>[] resize()

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table
 */
final Node<K,V>[] resize() {
}

从该函数的开头我们也可以确认我们刚才的观点。用来初始化和给table扩容的。

总结下来就是：

哈细表扩容：

• 当旧表容量大于0时，即旧表被初始化过了
  • 并且如果其容量大于或等于int的最大值。那么阈值设置为int的最大值。并返回旧旧表，此时表已经不能再扩容了，能做的只有置阈值为其能到大的最大值，尽可能的减少扩容次数。
  • 当旧表容量不及最大容量的一半时，并且旧表容量大于默认容量16时。由于函数resize被调用了。所以需要满足外界扩容需求，旧表阈值<<1。
• 当旧表没被初始化，但HashMap实例被初始化了。
  • 否则当旧表还未被初始化时，只是在初始化HashMap实例的时候赋予了阈值和负载因子(结合构造函数思考)，当旧阈值>0时，哈希表初始容量设置为阈值。
  • 否则，当构造HashMap实例时如果连阈值也没有赋值(默认为0)只是初始化了负载因子的话(默认无参构造函数)。初始化哈希表容量为DEFAULT_INITIAL_CAPACITY即16，阈值为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY即12。
• 当阈值=0时，新阈值=新容量*负载因子。当HashMap实例被被初始化时阈值也被初始化时会走这一分支
• 最后确定容量和阈值后初始化哈细表。

数据迁移：

• 当旧哈细表存在时，迭代哈细表每个元素。因为每个元素中存的都是链表或者红黑树。根据每个元素的哈希值重新散列到新哈希表的对应位置上。底层数据结构和节点的存储位置很大程度上会更改。

get(Object key)

从注释中可以看出，返回 null 值并不一定 表明该映射不包含该键的映射关系；也可能该映射将该键显示地映射为 null。可使用 containsKey 操作来区分这两种情况。

 /**
 * ·····
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 * ·····
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

函数具体查询逻辑封装到了getNode函数。

简单来说：

• key对应的哈希值计算出来落到哈希表对应的地方上，如果有元素存在。
• 有元素存在就需要比较了，因为元素上可能存的是链表或者红黑树。
  • 第一个元素就是搜寻的key本身
  • 第一个不是，但其是红黑树结构。参数传递并去红黑树中找
  • 不是红黑树结构，那么就是链表结构，进行迭代寻找，获取key对应的value。

remove(Object key)

/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @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 remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

从函数的注释中可以看出，该函数删除key对应的Entry并返回与 key 关联的旧值；如果 key 没有任何映射关系，则返回 null。但需要注意的是： 返回 null 还可能表示该映射之前将 null 与 key 关联。

函数再次把元素的通过hash函数包装传了进去，这很好理解，因为底层是哈希表嘛，不这样怎么能找到key到底在哈希表什么位置呢。我们可以看到删除逻辑的具体逻辑封装到了removeNode函数中。

removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)

先来对removeNod函数的多个参数进行一番分析。

 * @param hash hash for key 
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing

1. hash(key)
2. key
3. 对应matchValue参数，如果matchValue为true。那么删除key时其value必须与value相等，否则跳过这次删除
4. 如果true。只有当值相等时才删除。
5. 如果为false，那么在删除节点时不移动其他节点。

总的来说：

• 先判断key是否可以映射到哈希表上。

  • 如果可以，判断一下映射的位置头元素是否为该查找的元素。
  • 如果头元素不是要找元素，判断一下头元素后有无其他元素。如果有再判断一下这个元素的数据结构是否为红黑树，如果是，用node变量指向该key对应在红黑树中的节点。
  • 如果不是那说明哈希表该索引处是一个链表结构，然后对链表元素迭代寻找该元素，并用node节点指向寻找到的该元素。需要注意的是，p变量的逻辑定位，由于do while循环体中break语句相对于p=e语句置前，p变量在循环退出时指向的是node节点的前驱节点。

• 经历过橘黄色和红色两大块逻辑判断，成功找到了待删除节点的位置，并用node节点指向。如果该Node节点被成功找到了的话。

  • 红黑树：如果node节点所在哈希表的位置元素的存储结构式是红黑树的话。调用红黑树的删除方法
  • 链表：如果头节点就是待删除节点的话，那么待删除节点的next节点做头结点
  • 链表：如果待删除节点是链表中间部分的某个节点。借助p变量进行删除。

• modCount+1，size-1，并将删除的节点返回。

HashMap与HashTable对比

我们从一开始就曾说，两者从存储结构和实现来讲基本上都是相同的。两者最大的差别就是HashTable是线程安全的，而HashMap是线程不安全的。并且在数据存储时，HashMap允许key和value为null。而HashTable则键值均不允许为null。并且HashTable规定用作键的对象必须实现 hashCode 方法和 equals 方法。

HashTable在Map映射中的地位有点儿像Vector在List集合中的定位。也是比较过时的类，设计上有一些缺陷，不需要线程安全的情况下可以使用HashMap替代它，而需要线程安全的情况下也可以用ConcurrentHashMap来替代它。

总结

• HashMap的底层是：数组+链表+红黑树
• HashMap的实例有两个重要参数影响其性能。负载因子和初始容量，(装载因子*初始容量)< 散列表元素时，该散列表会扩容2倍，并重散列。
  • 负载因子：默认0.75，无论是初始大了还是初始小了对HashMap的性能都不好
    • 初始值大了，可以减少散列表再散列(扩容的次数)，但同时会导致散列冲突的可能性变大(散列冲突也是耗性能的一个操作，要得操作链表(红黑树)
    • 初始值小了，可以减小散列冲突的可能性，但同时扩容的次数可能就会变多！
  • 初始容量：默认值是16，无论初始大了还是小了对HashMap都是有影响的
    • 初始容量过大，那么遍历时速度就会受影响~
    • 初始容量过小，散列表再散列(扩容的次数)可能就变得多，扩容也是一件非常耗费性能的一件事
  • 参考公式：阈值 = 容量 * 负载因子
• HashMap在计算元素在哈希表中存储位置的时候，并不是直接拿key的哈希值来用的，会先对key的哈希值进行右移16位，然后再与其key的哈希值进行异或操作。根本上就是高位不变，低位变为高16位和低16位的异或结果，使得元素在存储时的随机性更大了。分布更加均匀了，减少了哈希冲突发生的概率
• 并不是箱子上元素大于等于8位元素的时候该哈希表的元素底层就能变成红黑树，它得同时满足哈希表总容量大于64才行，同时当红黑树元素数量低于8时，并不是会立马变回链表。而是在其元素小于6时才会。