HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap 可以存储 null 的 key 和 value

  • null 作为键只能有一个
  • null 作为值可以有多个

JDK1.8之前的HashMap

JDK1.8之前的HashMap的底层是数组＋链表，数组是 HashMap 的主体，链表是用来解决冲突。（也就是所谓的“拉链法”）

  1. 【获取hash值】HashMap通过key的hashCode经过扰动函数处理后得到hash值
  2. 【找到存放位置】通过(n-1)&hash获取当前元素当前存放位置（这里的 n 指的是数组的长度）。
  3. 【判断冲突】如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同【其实就是比较hash值以及使用key的equals方法。】
    • 如果相同的话，直接覆盖
    • 不相同就通过拉链法解决冲突。

拉链法是一种解决冲突的方法，当发生冲突的时候，就创建一个节点，将该节点放在链表最后面

image-20220902144906058

扰动函数hash

1
2
3
4
5
6
7
8
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);
}

JDK1.8的HashMap

JDK1.8 以后在解决哈希冲突时有了较大的变化。

Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。【Java7是 数组＋链表】

为什么要添加红黑树结构?

Java7的不足：

当我们进行查找时，根据 hash 值我们能够快速定位到数组的具体下标。

但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的。

时间复杂度取决于链表的长度，为 **O(n)**。

Java8的改进：

在 Java8 中，为了降低这部分的开销，当链表中的元素达到了 8 个时，会将链表转换为红黑树。

在这些位置进行查找的时候可以降低时间复杂度为 **O(logN)**。

HashMap结构示意图【主要是描述结构，不会达到这个状态的，因为这么多数据的时候早就扩容了】

image-20220902152819331 
1
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

类属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量  16

static final int MAXIMUM_CAPACITY = 1 << 30;  //最大容量 2^30

static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认装填因子 0.75

static final int TREEIFY_THRESHOLD = 8;// 链表转换为红黑树的阈值

static final int UNTREEIFY_THRESHOLD = 6;// 当桶(bucket)上的结点数大于这个值时会转成红黑树

static final int MIN_TREEIFY_CAPACITY = 64;//桶中结构转化为红黑树对应的table的最小容量
// 加载因子
final float loadFactor;
// 临界值(容量*填充因子) 当实际大小超过临界值时，会进行扩容
int threshold;
// 存放元素的个数，注意这个不等于数组的长度。
transient int size

装填因子LOAD_FACTOR

什么是装填因子？$ a = \frac{n}{m}$

n为哈希表的关键字个数，也就是哈希表中已经有多少个位置有元素了。

m表示哈希表的长度，也就是容量。

  • loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密
    • loadFactor 太大导致查找元素效率低，而且很容易导致冲突
  • loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。
    • 太小导致数组的利用率低，存放的数据会很分散

**loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值**。

默认情况下，默认容量为 16，负载因子为 0.75。

Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 个时。

就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

threshold

threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。

也就是这个size，你向map中添加元素的个数，并不是数组的长度【容量】。

底层数据结构

1
2
3
4
//存储元素的数组，总是2的幂次倍
transient Node<K,V>[] table;
//存放具体元素的集  键值对集合
transient Set<Map.Entry<K,V>> entrySet;

Node<K,V>链表节点内部类，源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; //哈希值，存放元素到hashmap中时用来与其他元素hash值比较
    final K key;	//键
    V value;		//值
    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()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
	
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

抽象结构如下：

image-20220902155602516

TreeNode<K,V>红黑树节点内部类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;    // needed to unlink next upon deletion
    boolean red;			//判断颜色
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

     // 返回根节点
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    //省略了大量代码
}

构造方法

  • 无参构造，装填因子为默认的装填因子【0.75】,所有属性均为默认

    1
    2
    3
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他字段均为默认值
    }

  • 包含另一个“Map”的构造函数

    1
    2
    3
    4
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默认装填因子 0.75
        putMapEntries(m, false);
    }

    内部调用了putMapEntries方法【这个方法在后面讲】

  • 指定“容量大小”的构造函数

    1
    2
    3
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

  • 指定“容量大小”和“加载因子”的构造函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);//返回给定目标容量的2次方大小。
    }

putMapEntries方法

从一个Map对象中批量添加的函数。

这个方法服务于 Map的构造方法HashMap(Map<? extends K, ? extends V> m)和Map的putAll(Map<? extends K, ? extends V> m)方法。

  • 当构造方法调用这个方法，**evict为False**

  • 当putAll调用这个方法，**evict为True**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size(); //获取传入map集合的大小
    if (s > 0) {
        if (table == null) { // 判断table是否已经初始化  “自身的map"
            //======================================================================
            float ft = ((float)s / loadFactor) + 1.0F;//[ft = 元素个数/装填因子 +1 ]
            //计算 容量， [装填因子=元素个数/容量]。这个ft应该是预计需要多少容量
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?//如果ft<最大容量，则t = ft,否则 t = 最大容量。
                     (int)ft : MAXIMUM_CAPACITY);
            //======================================================================
            //总之通过以上计算，最后得到的这个t 表示，如果批量加入 这个Map，【最终预计需要多少容量】。
            if (t > threshold)//计算得到的t大于阈值，则初始化阈值,
                threshold = tableSizeFor(t);//tableSizeFor(t)  返回给定目标容量的2次方大小。
        }
        else if (s > threshold)//判断 即将要加入的元素个数是否会大于阈值
            resize();//扩容
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

tableSizeFor(t)返回给定目标容量的2次方大小，比如 t = 10，就返回16；t=100，返回128。

流程总结：

  1. 首先判断自身的Node<K,V>[] table有没有初始化

    • 如果没有初始化

      ​ 1.根据传入Map所含元素数量，装填因子，最大容量，来计算预计最终所需容量，t。

      ​ 2.如果t>阈值，则阈值就是大于t的二次方大小。

    • 如果初始化过，且 传入Map所含元素数量 s 大于 阈值，则对Map进行扩容。

  2. 最后再循环遍历传入的Map，调用putVal()方法添加。

注：

  • if (t > threshold)这里的threshold成员实际存放的值是capacity的值。因为在table还没有初始化时（table还是null），用户给定的capacity会暂存到threshold成员上去（毕竟HashMap没有一个成员叫做capacity，capacity是作为table数组的大小而隐式存在的）
  • else if (s > threshold)说明传入map的size都已经大于当前map的threshold了，即当前map肯定是装不下两个map的并集的，所以这里必须要执行**resize()[扩容]**操作
  • putval也是使用的默认修饰符，因此只能被本类或者该包下的类访问到，最后循环里的putVal可能也会触发resize操作

put()方法&putVal()方法

HashMap 只提供了 put 用于添加元素，putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用。

put()方法：

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

内部调用了putVal()方法

参数：

  • hash：key的hash值
  • key: 键
  • value：值
  • onlyIfAbsent：如果为真，不更改现有值
  • Evict ：如果为false，表示表处于创建模式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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;
    if ((p = tab[i = (n - 1) & hash]) == null)//如果插入所要插入的位置 为 null，则直接插入。
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //判断hash和equal看是否等价。
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//等价就直接覆盖
        //不等价就判断是否是树节点
        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);
                    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;
            }
        }
        if (e != null) { // 值覆盖
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//如果元素个数大于阈值，就进行扩容。
        resize();
    afterNodeInsertion(evict);
    return null;
}

总结：

  1. 如果定位到的数组位置没有元素 就直接插入
  2. 如果定位到的数组位置有元素就和要插入的 key 比较【比较hash和调用equals()】
    1. 如果 key 相同就直接覆盖
    2. 如果 key 不相同
      1. 如果是一个树节点就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入
      2. 如果是链表节点就遍历链表插入(插入的是链表尾部)。

当链表长度大于阈值（默认为 8）并且 HashMap 数组长度超过 64 的时候才会执行链表转红黑树的操作，否则就只是对数组扩容。

参考 HashMap 的 treeifyBin() 方法

扩容方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;					//旧的数组 Table
    int oldCap = (oldTab == null) ? 0 : oldTab.length;	//旧的容量，即oldTab.length,如果非null,否则是0
    int oldThr = threshold;						//旧的阈值
    int newCap, newThr = 0;						//初始  新的阈值和新的容量  为0
//===================================确定新的容量和新的阈值============================
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {			//原本的容量达到 最大容量
            threshold = Integer.MAX_VALUE;			//那阈值就是int 最大值
            return oldTab;							//超过最大值就不再扩充了，就只好随你碰撞去吧
        }
        // 新的容量扩充为旧的两倍   ，而且没有超过规定的容量上限，且，旧的容量大于默认容量。   
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 新的阈值也扩充为两倍
    }
    //数组table没有初始，但有初始的阈值，那么新的容量就是阈值。
    else if (oldThr > 0) // 初始容量置于阈值
        newCap = oldThr;
    //数组table没有初始化，且阈值也没有初始化
    else {               // 零初始阈值表示使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;//新的容量就是默认容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的阈值就是 默认容量*默认装填因子。
    }

    
    //如果新的容量超过了MAXIMUM_CAPACITY，或者旧的容量小于 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;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//初始一个新的数组
    table = newTab;
    if (oldTab != null) {
        // 开始遍历原数组，进行数据迁移。  下面的有些无关紧要了
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // 如果该数组位置上只有单个元素，那就简单了，简单迁移这个元素就可以了
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                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;
                        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;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

总结一下是如何扩容的

当你进行初始化时：

  • 如果你是无参构造一个HashMap

    初始容量就是16（默认容量），初始阈值就是12（默认容量*默认装填因子）。

  • 如果你使用初始容量的那个构造函数 new 一个HashMap

    初始阈值就是 你指定的初始容量的2次方大小，初始容量就是初始阈值。

    例如，new HashMap<>(24);，则初始容量为36，初始阈值也是36。

当你添加的元素需要扩容时：

  • 如果旧的容量小于最大容量【2^30】

    • 新的容量 为 旧的容量两倍，新的阈值因情况而定

      • 旧的容量 > 默认容量【16】，且新的容量<最大容量【2^30】：新的阈值 就是 旧的阈值两倍

      • 旧的容量大于默认容量，且新的容量大于最大容量：

        1
        2
         float ft = (float)newCap * loadFactor;//装填因子*新的容量
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY?(int)ft:Integer.MAX_VALUE);

  • 如果旧的容量大于最大容量【2^30】

    那阈值就是int 最大值，然后就不会再去扩充。

我们会发现，hashmap的容量总是2的次方，比如8、16、32、64…..

还有就是，在扩容的过程中它还需要进行数据迁移，这是非常耗时的，所以我们应该尽量避免扩容！

HashSet

HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法，因此HashSet的实现非常简单，只有不到300行代码。这里不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;


    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();//对HashMap的包装。
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    //......
}

__END__