【Java集合】记录阅读 HashMap 集合类源码的辛酸历程

HashMap官方介绍

HashMap是基于哈希表的Map接口实现。此实现提供了所有可选的映射操作，并允许空值和空键。（HashMap类大致相当于Hashtable，只是它不同步并且允许null。）这个类不保证映射的顺序；特别是，它不能保证排序在一段时间内保持不变。 这个实现为基本操作（get和put）提供了恒定的时间性能，假设哈希函数在bucket中正确地分散元素。迭代集合视图需要的时间与HashMap实例的“容量”（存储桶数）及其大小（键值映射数）成正比。因此，如果迭代性能很重要，那么不要将初始容量设置得太高（或负载系数设置得太低），这一点非常重要。 HashMap实例有两个影响其性能的参数：初始容量和加载因子。

HashMap的实例有两个影响其性能的参数：初始容量和负载系数。容量是哈希表中的存储桶数，初始容量只是创建哈希表时的容量。加载因子是衡量哈希表在自动增加容量之前允许获得的满度。当哈希表中的条目数超过加载因子和当前容量的乘积时，哈希表将被重新哈希（即重建内部数据结构），以便哈希表的存储桶数大约是的两倍。

一般来说，默认负载系数（0.75）在时间和空间成本之间提供了一个很好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括 get and put）。在设置其初始容量时，应考虑映射中的预期条目数及其负载系数，以最小化重新散列操作的数量。如果初始容量大于最大条目数除以负载系数，则不会发生再散列操作。

如果许多映射要存储在一个HashMap实例中，那么使用足够大的容量创建它将使映射的存储效率高于让它根据需要执行自动重新存储以增长表。请注意，使用具有相同{@code hashCode（）}的many键肯定会降低任何哈希表的性能。为了改善影响，当键为{@link Comparable}时，此类可以使用键之间的比较顺序来帮助打破关系。

请注意，此实现不同步，如果多个线程同时访问哈希映射，并且线程中至少有一个线程在结构上修改了该映射，那么它必须在外部进行同步。（结构修改是添加或删除一个或多个映射的任何操作；仅更改与实例已包含的键关联的值不是结构修改。）这通常通过同步自然封装映射的某个对象来完成。

如果不存在这样的对象，则应使用{@link Collections#synchronizedMap Collections.synchronisedMap}方法“包装”映射。这最好在创建时完成，以防止意外未同步访问映射：map m=Collections。synchronizedMap（new HashMap（…））；

这个类的所有“collection-view-methods”返回的迭代器都是fail-fast：如果在创建迭代器之后的任何时候对映射进行了结构修改，那么除了通过迭代器自己的remove方法之外，迭代器将抛出一个{@link ConcurrentModificationException}。因此，在面对并发修改时，迭代器会快速而清晰地失败，而不是冒着在未来某个不确定的时间发生任意、不确定行为的风险。

请注意，不能保证迭代器的快速失败行为，因为一般来说，在存在非同步并发修改的情况下，不可能做出任何硬保证。快速迭代失败尽最大努力抛出ConcurrentModificationException。因此，编写一个依赖于这个异常的正确性的程序是错误的：迭代器的快速失败行为应该只用于检测bug。

HashMap的特点

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

HashMap 是无序的，即不会记录插入的顺序。

HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value，也可以是整型（Integer）的 key 和字符串（String）类型的 value。

HashMap 中的元素实际上是对象，一些常见的基本类型可以使用它的包装类。

HashMap 类位于 java.util 包中，使用前需要引入它，语法格式如下：import java.util.HashMap;

HashMap的成员变量

HashMap 一共有 13 个成员变量：

// table 的默认初始容量-必须是2的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// table 最大容量，如果任何一个带参数的构造函数隐式指定了更高的值，则使用必须是2的幂并且 <= （1<<30）。
static final int MAXIMUM_CAPACITY = 1 << 30
    
// 构造函数中未指定时使用的默认负载系数。(默认加载因子0.75)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 对bin使用树而不是列表的bin计数阈值。当将元素添加到至少有这么多节点的bin时，bin将转换为树。该值必须大于2，并且应至少为8，以符合树删除中关于收缩后转换回普通箱的假设。(链表转换为红黑树的长度阈值)
static final int TREEIFY_THRESHOLD = 8;

// 在“调整大小”操作期间取消筛选（拆分）存储箱的存储箱计数阈值。应小于TREEIFY_THRESHOLD，并且在移除过程中，最多6个网格以检测收缩。
static final int UNTREEIFY_THRESHOLD = 6;

// 可对其进行树化的最小表容量。（否则，如果bin中的节点过多，则会调整表的大小。）应至少为4*TREEIFY_THRESHOLD，以避免调整大小和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY = 64;

// 该表在首次使用时初始化，并根据需要调整大小。分配时，长度总是2的幂。（在某些操作中，我们还允许长度为零，以允许当前不需要引导机制。）
transient Node<K,V>[] table;


// 保存缓存的entrySet()，注意：AbstractMap字段用于表示keySet()和values()。
transient Set<Map.Entry<K,V>> entrySet;

// 此映射中包含的键值映射数。
transient int size;

// 此HashMap在结构上被修改的次数,结构修改是指那些更改哈希映射中映射数或以其他方式修改其内部结构（例如，rehash）的修改。此字段用于使HashMap的Collection视图上的迭代器快速失败。（请参阅ConcurrentModificationException）。
transient int modCount;

// 下一个要调整大小的大小值（容量*负载系数）。
int threshold;

// 哈希表的加载因子。
final float loadFactor;

//序列化版本号
private static final long serialVersionUID = 362498820763181265L;

HashMap的构造方法

HashMap 一共有 4 个构造方法：

// 使用默认初始容量（16）和默认加载因子（0.75）构造一个空的HashMap。
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}


// 使用指定的初始容量和默认加载因子（0.75）构造一个空的HashMap。
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


// 使用指定的初始容量和加载因子构造一个空的HashMap。
public HashMap(int initialCapacity, float loadFactor) {
    // 如果指定初始容量小于0 直接抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // 如果指定初始容量等于最大值 直接使用最大值
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    // 判断指定加载因子，如果小于0 或者不能转为浮点数，也就是非法数值 直接抛出异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 检查完毕，合法数据进行赋值
    this.loadFactor = loadFactor;
    // 按照指定初始化容量和加载因子计算出阈值
    this.threshold = tableSizeFor(initialCapacity);
}


// 使用与指定的映射相同的映射构造新的HashMap。HashMap是使用默认加载因子（0.75）创建的，初始容量足以保存指定Map中的映射。
public HashMap(Map<? extends K, ? extends V> m) {
    // 使用默认加载因子（0.75）
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    // 将容器m中的元素添加到HashMap
    putMapEntries(m, false);
}

HashMap的PUT操作

主程序如下：

 public static void main(String[] args){
     // 使用默认空参构造创建HashMap容器
     HashMap<Integer, String> map = new HashMap<>();
     // 以下执行PUT操作
     map.put(1, "JAVA");
     map.put(2, "MySQL");
     map.put(1, "Redis");
 ​
 }

1. 调用空参构造

// 使用默认初始容量（16）和默认加载因子（0.75）构造一个空的HashMap。
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

2.自动装箱（非必须）

如果我们添加元素的key是基本数据类型的，那么在put到HashMap容器中时，会首先进行自动装箱，然后进行添加操作。如果是引用类型变量，则直接PUT。这里的1为基本数据类型，需要进行自动装箱。

public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

3. 调用put方法

// 将指定值与此映射中的指定键相关联。如果映射先前包含键的映射，则替换旧的值。
public V put(K key, V value) {
    // 可以发现，在这里并没有具体任何实现，而是直接调用了putVal方法
    return putVal(hash(key), key, value, false, true);
}

4.调用hash(key)方法

计算键的hashCode并将哈希的高位扩展到低位（XOR）。因为该表使用两个掩码的幂，所以仅在当前掩码以上的位上变化的哈希集将始终发生碰撞。（在已知的例子中，有一组浮点键在小表格中保持连续的整数。）因此，我们应用了一种向下传播高位影响的转换。比特扩展的速度、效用和质量之间存在权衡。由于许多常见的散列集已经合理分布（因此不会从传播中受益），并且因为我们使用树来处理容器中的大量冲突，所以我们只需以最便宜的方式对一些移位的位进行异或，以减少系统损失，以及合并最高位的影响，否则，由于表的界限，将永远不会在索引计算中使用。

// 计算指定Key的哈希值
static final int hash(Object key) {
    // 临时存储key的哈希值 h = key.hashCode()
    int h;
    // 如果key为空，则哈希值为0，否则使用如下哈希算法进行计算哈希值并返回
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

5. 调用putVal方法（重要）

// 实现HashMap的put和相关方法。
// 参数1：hash 被添加元素Key的哈希值
// 参数2：key  被添加元素的key
// 参数3：value 被添加元素的value
// 参数4：onlyIfAbsent  如果为true，则不更改现有值
// 参数五：evict  如果为false，则表处于创建模式。HashMap并没有使用，留给LinkedHashMap使用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 定义一系列变量，暂存数据
    // tab（当前容器数组table）临时存储当前容器的table数组 tab = table
    // p（旧节点元素）临时存储在当前容器中 新加元素下标位置的老的节点 p = tab[i = (n - 1) & hash]
    // n(table的长度)临时存储当前容器的table数组的长度 n = tab.length
    // i（新加元素在table中的下标位置）临时存储当前元素在数组中的下标位置 i = (n - 1) & hash
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 如果当前容器数组为空或者当前容器长度为0，则进行第一次扩容 tab = resize()，并将扩容后的长度赋值为 n
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 判断在当前容器中，被添加元素（新元素）所需要的下标位置处是否为空，
    // 如果为空，则进行新建节点直接插入tab[i] = newNode(hash, key, value, null);
    // 通过当前数组长度减一在和hash值进行按位与运算，计算出新元素所在下标i,并将当前数组的此下标节点赋值给P节点，也就是p节点存储旧的元素。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        
        // 如果当前所需下标位置不为空，已经有了元素，则进行一系列复杂操作
        // 首先创建临时变量
        // e临时存储旧节点元素
        // k临时存储当前位置旧元素的key  k = p.key
        Node<K,V> e; K k;
        
        // 判断如果当前位置存放的元素（旧元素）与被加入元素（新元素）的哈希值相同，并且【旧元素的key与新元素的key相同，或者 二者的key不为空时，新旧元素的key值内容相同】时，将旧节点元素赋值为e --> e = p; 表明容器中已存在与新元素相同的key,在下面直接进行覆盖操作。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        // 否则则表明不存在新元素的key，则进行判断当前是否为红黑树结构，如果是，则直接插入树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  // 返回null
        
        // 如果不是红黑树结构，则是链表，遍历添加到链表末尾
        else {
            for (int binCount = 0; ; ++binCount) {
               // 如果旧节点下一个元素为空，表明是链表尾部，则添加至此p.next = newNode(hash, key, value, null);
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    
                    // 注意在把元素添加到链表后，立即判断该链表是否已经达到8个结点，
                    // 达到8个节点数就调用treeifyBin()对当前这个链表进行树化(转成红黑树)
                    // 注意:if(tab==null ||(n=tab.length)<MIN_TREEIFY_CAPACITY(64)) resize();
					// 
					// 如果上面条件成立，先table扩容，只有上面条件不成立时，才进行转成红黑树
                    // 判断是否需要转换为红黑树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 添加完成 跳出循环
                    break;
                }
                
                // 如果下个节点不为空，则判断旧节点下一个元素的hash值和KEY值是否与新元素相同，
                // 如果相同直接跳出循环，不进行操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                
                // 将下一个节点赋值给p -->p = e;进行下轮循环
                p = e;
            }
        }
        // 如果是红黑树结构,直接加入后，返回e为null
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                // 进行value覆盖操作
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // 记录容器修改次数 +1
    ++modCount;
    // 添加元素后进行判断是否需要扩容resize();
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

面试题：说一下HashMap中put操作过程？

首先判断容器数组table是否为空，若数组为空则进行第一次扩容（resize），不为空则通过hash算法，计算Key在数组中的索引；

然后进行插入元素的操作，

• 如果被添加元素所需要的下标位置元素为空，则直接插入数据；

• 如果被添加元素所需要的下标位置元素非空，判断key是否存在，

  • 若key已存在，则直接覆盖其value；

  • 若key不存在，则判断是否有链表，

    • 若不是链表则是红黑树直接插入

    • 若是链表则遍历到链表末尾进行插入，插入后判断链表长度是否大于8

      • 若链表长度大于8，则进行树化操作

      • 若链表长度不大于8，则跳出循环

添加元素后进行判断是否需要扩容resize()，如果数组中元素个数（size）超过threshold，则再次进行扩容操作。

HashMap的GET操作

1.调用get方法

// 根据key获取元素对应的value
public V get(Object key) {
    // 临时存储查询到的元素 用于返回value
    Node<K,V> e;
    // 调用getNode(hash(key), key)方法判断是否为空，是则返回null否则返回元素值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

2.调用getNode方法

// 实现map.get的相关方法。
// 参数hash：目标元素key的哈希值--> hash(key)--> hash=(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// 参数key：目标元素key
final Node<K,V> getNode(int hash, Object key) {
    	// 定义一系列的临时变量
    	// tab 临时存储当前容器的table数组-->tab = table
    	// first 临时存储根据当前元素key的hash值计算出该hash值在table中的下标位置的第一个节点
    	// e 临时存储当前table槽中的下一个元素节点
    	// n 临时存储当前容器中table数组的长度-->n = tab.length
    	// k 临时存储对应table槽中首个元素的key-->k = first.key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    	// 判断当前容器的table数组不为空且长度大于零，并且查询元素key的hash值所在的table下标位置元素非空
    	// 也就是保证了在容器中可能会有被查询的元素
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            
            // 判断如果对应位置的第一个节点的hash值与所查询元素的hash值一致并且【key相同或者key不为null且key的内容值相				同】时，则表明就是目标元素，直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            
            
            // 否则，如果下一个节点不为空就去遍历查找
            if ((e = first.next) != null) {
                // 如果当前是红黑树结构，则去使用getTreeNode(hash, key)查询，并直接返回查询结果
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
                // 否则就是链表结构，开始遍历链表
                do {
                    // 同样的逻辑判断，当前元素是否为目标元素。如果hash值相同并且key相同且key的内容值一致，是直接返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
      // 否则直接返回null
        return null;
    }

面试题：说一下HashMap的获取元素的操作过程。

当我们调用get方法进行根据key获取指定的元素时，他会去调用getNode方法去完成，并且传入目标元素的key以及key的哈希值。

• 在getNode方法中，首先会去判断当前容器的table数组是否为空且长度是否大于零，并且查询元素key的hash值所在的table下标位置元素是否非空，如果table为空或者长度小于零或者指定槽位为空，则直接返回null；

• 当table数组是不为空且长度大于零且指定槽位有元素，则进行查询操作

  • 首先判断对应槽位的第一个节点的hash值与所查询元素的hash值一致并且【key相同或者key不为null且key的内容值相同】时，则表明就是目标元素，直接返回

  • 否则，当下一个节点不为空就去遍历查找

    • 如果当前是红黑树结构，则去使用getTreeNode(hash, key)查询，并直接返回查询结果

    • 否则就是链表结构，开始遍历链表，判断当前元素是否为目标元素，查询后直接返回

• 如果未查询到指定元素进行返回，则最后返回null，查询结束。

HashMap的Remove操作

1.调用remove方法

// 根据指定元素的key，如果存在，则从此映射中移除指定键的映射。
public V remove(Object key) {
    // 用于存储删除的元素节点 用于返回旧元素的value
    Node<K,V> e;
    // 调用removeNode方法进行删除操作
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

2.调用removeNode方法

// 实现map.remove的相关方法。
// 参数hash：目标元素key的哈希值--> hash(key)--> hash=(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
// 参数key：目标元素key
// 参数value：如果matchValue，则匹配值，否则忽略  -->null
// 参数matchValue：如果为true，则仅在值相等时移除  -->false
// 参数movable：如果为false，则在删除时不要移动其他节点  -->true
final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {
    
    // 定义一系列临时变量
    // tab：存储当前容器的table数组-->tab = table
    // p：临时存储被删元素应该在table中的下标位置的当前元素节点-->p = tab[index = (n - 1) & hash]
    // n：存储当前容器中table数组的长度-->n = tab.length
    // index:存储被删元素应该在table中的下标位置-->index = (n - 1) & hash
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    
	// 判断如果当前容器table数组不为空并且table数组长度大于零并且被删元素应该在table中的下标位置元素不为空，说明路由的槽			位是有数据的，需要进行查找操作，并且删除，否则直接返回null，
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        
        // 定义临时变量，暂存数据
        // node：用于存储被删除元素节点-->node = p;
        // e：用于临时存储当前槽位下一个元素节点-->e = p.next
        // k：用于临时存储该槽位上遍历当前元素节点的key
        // v：用于临时存储被删除元素的value-->v = node.value
        Node<K,V> node： = null, e; K k; V v;
        
        // 判断如果被删元素所在table位置上的第一个元素与被删元素的hash值相等并且key相等，内容相同，则表明是需要删除的元素
        // 则将该节点元素赋值给node节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        
        // 否则当下一个元素不为空，开始遍历下一个元素节点
        else if ((e = p.next) != null) {
            
            // 判断当前是否为红黑树结构，是则去调用getTreeNode方法获取被删除元素并赋值给node节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            
            // 否则就是链表结构，开始遍历
            else {
                do {
                    // 如果当前元素节点key的hash值与被删元素的一致，并且key相等，则表明是被删除的元素，直接赋值给node						节点，跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    // 指向下一个节点
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        
        // 如果经过上面的查询，node节点也就是被删除的元素节点不为空并且[matchValue为false或者value相同，也就是查找到了			需要被删除的元素，则进行删除操作
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            
            // 判断当前结构是否为红黑树，如果是则调用removeTreeNode方法去删除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            
            // 否则就是链表结构，如果要删除的元素节点就是当前p指向节点，则将删除元素的下一个元素放至槽位中
            else if (node == p)
                tab[index] = node.next;
            else
                // 将当前元素p的下一个元素设置成要删除元素的下一个元素
                p.next = node.next;
            // 记录修改次数++
            ++modCount;
            // 容器元素数量--
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

面试题：说一下HashMap的删除元素的操作过程。

当我们调用remove方法进行删除指定的元素时，他会去调用removeNode方法去完成，并且传入目标元素的key以及key的哈希值，和一些其他的参数。

• 在removeNode方法中会首先判断table数组是否为空、数组长度是否小于零，当前槽位是否有元素，如果为空或者当前槽位为空则直接返回null；

• 若当前数组不为空且该槽位有元素则取出该槽位的第一个元素，进行判断

  • 若当前槽位第一个元素是目标元素，则直接赋值给node节点

  • 否则，进行遍历查询后续元素节点

    • 如果当前是红黑树结构，则调用removeTreeNode方法查询目标节点，并返回赋值给node节点

    • 如果是链表结构，则开始遍历链表，查询目标节点找到则赋值给node节点，否则方法返回null

• 查询到被删除元素赋值给node节点不为空后，进行删除操作

  • 判断当前结构是否为红黑树，如果是则调用removeTreeNode方法去删除

  • 链表结构则判断目标节点是否为槽位节点，是的话则将删除元素的下一个元素放至槽位中

  • 否则，将当前元素p的下一个元素设置成要删除元素的下一个元素

HashMap的扩容机制

首先扩容是一个特别消耗性能的操作，所以在使用HashMap的时候，如果提前预知会有大量元素存储，估算map的大小，通过有参构造指定容量去创建 HashMap ，避免map进行频繁的扩容。这点在上面HashMap的官方介绍中也有提到。其次是负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。再有就是HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。JDK1.8引入红黑树大程度优化了HashMap的性能。

JDK 1.7

在 Java1.7 中 Hashmap 的扩容需要满足两个条件：一是当前数据存储的数量（即size()）大小必须大于等于阈值且table长度大于64；二是当前加入的数据是否发生了hash冲突。

因为上面这两个条件，所以存在下面这些情况

• 一就是Hashmap 在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

• 二是也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。原理：前11个值全部hash碰撞，存到数组的同一个位置（虽然hash冲突，但是这时元素个数小于阈值12，并没有同时满足扩容的两个条件。所以不会扩容），在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，因为存入之前此时比较当前元素个数 11<12(16*0.75)，所以在存入第12个元素的时候不会发生扩容，那么还有15个数据下标的位置是空的，后面所有存入的15个值全部分散到数组剩下的15个位置（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，也没有同时满足扩容的两个条件，所以叶不会扩容），前面12+15=27，所以在存入第28个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

JDK 1.8

Java8中扩容只需要满足一个条件：当前存放新值（注意不是替换已有元素位置时）的时候已有元素的个数大于等于阈值（已有元素等于阈值，下一个存放后必然触发扩容机制）

• 扩容一定是放入新值的时候，该新值不是替换以前位置的情况下

• 扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。

当我们使用空参构造创建Hashmap 时，第一次进行put操作会触发第一次扩容，并且使用默认大小16、默认加载因子0.75，阈值为12进行扩容；

当我们指定初始化容量大小进行创建Hashmap 时，会按照大于指定容量的最近2的次幂进行初始化，比如指定容量30，那么第一次初始化后容量为32，threshold阈值为24 =（32*0.75）。

HashMap的常见面试题

HashMap 1.7 和 HashMap 1.8 的区别？

底层使用的数据结构结构不同，插入数据的方式、hash 值计算方式不同以及扩容策略不同。

HashMap 和 Hashtable 的区别

1. 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果要保证线程安全的话就使用 ConcurrentHashMap ！）；

2. 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；

3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

4. 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet 区别

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

综上，相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

HashMap 的底层实现

JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。其中数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

JDK1.8 之后

JDK1.8 之后在解决哈希冲突时有了较大的变化，相比于之前的版本，链表容易过长，最坏情况下会成为单向链表，会严重影响 HashMap 的性能， 而红黑树搜索的时间复杂度是 O(logn)，而链表是糟糕的 O(n)，于是就引入了红黑树，链表和红黑树在达到一定条件会进行转换：

• 当链表超过 8 且数据总量超过 64 时会转红黑树。

• 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。

HashMap是如何解决Hash冲突的？

哈希冲突: hashMap在存储元素时会先计算key的hash值来确定存储位置，因为key 的hash值计算最后有个对数组长度取余的操作，所以即使不同的key也可能计算出相同的hash值，这样就引起了hash冲突。

HashMap中的哈希冲突解决方式可以主要从三方面考虑(以JDK1.8为背景)

• 拉链法 HasMap中的数据结构为数组+链表/红黑树，当不同的key计算出的hash值相同时，就用链表的形式将Node结点（冲突的key及key对应的value)挂在数组后面。

• hash函数 key的hash值经过两次扰动，key的哈希值与key的哈希值右移16位的值进行异或hash ^（hash >> 16），然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样)，这样做可以让哈希取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。

• 红黑树 在拉链法中，如果hash冲突特别严重，则会导致数组上挂的链表长度过长，性能变差，因此在链表长度大于8时，将链表转化为红黑树，可以提高遍历链表的速度。

为什么在解决 hash 冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树?

因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。

当元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能。当元素大于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。

因此，如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。

HashMap 为什么线程不安全，体现在哪里？

• HashMap在JDK 7 时多线程下扩容并发执行put操作时，可能会导致形成循环链表，从而引起死循环。

• 多线程的put可能导致元素的丢失。

• put和get并发时，可能导致get为null。

在 hashMap1.7 中扩容的时候，因为采用的是头插法，所以会可能会有循环链表产生，导致数据有问题，在 1.8 版本已修复，改为了尾插法。

在任意版本的 hashMap 中，如果在插入数据时多个线程命中了同一个槽，可能会有数据覆盖的情况发生，导致线程不安全。

那么 HashMap 线程不安全怎么解决？或者说如何得到一个线程安全的Map？

• 用Collections工具类，将线程不安全的Map包装成线程安全的Map，也就是给 hashMap 直接加锁,来保证线程安全

• 使用java.util.concurrent包下的concurrentHashMap , 不管是其 1.7 还是 1.8 版本,本质都是减小了锁的粒度,减少线程竞争来保证高效

• 使用 hashTable,其实就是在其方法上加了 synchronized 锁，但是不建议使用Hashtable，虽然Hashtable是线程安全的，但是性能较差。

微信关注

编程那点事儿