HashMap数据结构

当链表节点较少时仍然是以链表存在，当链表节点较多时（大于8）会转为红黑树

img

类中属性

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
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    
    // 默认容量16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
 
    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;    
 
    final float loadFactor;//负载因子，用于扩容
 
    // 默认负载因子0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f; 
 
    // 链表节点转换红黑树节点的阈值, 9个节点转
    static final int TREEIFY_THRESHOLD = 8; 
 
    // 红黑树节点转换链表节点的阈值, 6个节点转
    static final int UNTREEIFY_THRESHOLD = 6;   
 
    // 转红黑树时, table的最小长度
    static final int MIN_TREEIFY_CAPACITY = 64; 
 
    transient Node<K,V>[] table;
 
    // 链表节点, 继承自Entry
    static class Node<K,V> implements Map.Entry<K,V> {  
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
 
        // ... ...
    }
 
    // 红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
   
        // ...
    }
}

img

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
1.看源码之前需要了解的一些内容

Node&lt;K,V&gt;[] table   哈希表结构中数组的名字

DEFAULT_INITIAL_CAPACITY：   数组默认长度16

DEFAULT_LOAD_FACTOR：        默认加载因子0.75



HashMap里面每一个对象包含以下内容：
1.1 链表中的键值对对象
    包含：  
	    int hash;         //键的哈希值
            final K key;      //键
            V value;          //值
            Node&lt;K,V&gt; next;   //下一个节点的地址值
			
			
1.2 红黑树中的键值对对象
	包含：
	    int hash;         		//键的哈希值
            final K key;      		//键
            V value;         	 	//值
            TreeNode&lt;K,V&gt; parent;  	//父节点的地址值
			TreeNode&lt;K,V&gt; left;	//左子节点的地址值
			TreeNode&lt;K,V&gt; right;	//右子节点的地址值
			boolean red;			//节点的颜色
					


2.添加元素
HashMap&lt;String,Integer&gt; hm = new HashMap&lt;&gt;();
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);

添加元素的时候至少考虑三种情况：
2.1数组位置为null
2.2数组位置不为null，键不重复，挂在下面形成链表或者红黑树
2.3数组位置不为null，键重复，元素覆盖



//参数一：键
//参数二：值

//返回值：被覆盖元素的值，如果没有覆盖，返回null
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
//简单理解：返回值就是返回键的哈希值
//整个过程本质上就是三步：
//(1)拿到 key 的 hashCode 值
//(2)将 hashCode 的高位进行 按位与 运算，重新计算 hash 值
//(3)将计算出来的 hash 值与 (table.length - 1) 进行 & 运算
static final int hash(Object key) {
    int h;
     // 1.先拿到key的hashCode值; 2.将hashCode的高16位参与运算
    //高16位与16位0值异或，低16位与高16位异或
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h &gt;&gt;&gt; 16);
    int n = tab.length;
   // 将(tab.length - 1) 与 hash值进行&运算
   int index = (n - 1) & hash;
}

//参数一：键的哈希值
//参数二：键
//参数三：值
//参数四：如果键重复了是否保留
//		   true，表示老元素的值保留，不会覆盖
//		   false，表示老元素的值不保留，会进行覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
	    //定义一个局部变量，用来记录哈希表中数组的地址值。
        Node&lt;K,V&gt;[] tab;
		
		//临时的第三方变量，用来记录键值对对象的地址值
        Node&lt;K,V&gt; p;
        
		//表示当前数组的长度
		int n;
		
		//表示索引
        int i;
		
		//把哈希表中数组的地址值，赋值给局部变量tab
		tab = table;

        if (tab == null || (n = tab.length) == 0){
		//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
		//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
		//如果没有达到扩容条件，底层不会做任何操作
		//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
			tab = resize();
		//表示把当前数组的长度赋值给n
            n = tab.length;
        }

		//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置
		i = (n - 1) & hash;//index
		//获取数组中对应元素的数据
		p = tab[i];
		
		
        if (p == null){
		//底层会创建一个键值对对象，直接放到数组当中
            tab[i] = newNode(hash, key, value, null);
        }else {
            Node&lt;K,V&gt; e;
            K k;
			
		//等号的左边：数组中键值对的哈希值
		//等号的右边：当前要添加键值对的哈希值
		//如果键不一样，此时返回false
		//如果键一样，返回true
			boolean b1 = p.hash == hash;
			
            if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;
            } else if (p instanceof TreeNode){
	//判断数组中获取出来的键值对是不是红黑树中的节点
	//如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
                e = ((TreeNode&lt;K,V&gt;)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);
		//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
		//treeifyBin方法的底层还会继续判断
		//判断数组的长度是否大于等于64
		//如果同时满足这两个条件，就会把这个链表转成红黑树
                        if (binCount &gt;= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
		//e：			  0x0044  ddd  444
		//要添加的元素： 0x0055   ddd   555
		//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
						 break;
					}

                    p = e;
                }
            }
			
		//如果e为null，表示当前不需要覆盖任何元素
	       //如果e不为null，表示当前的键是一样的，值会被覆盖
	      //e:0x0044  ddd  555
	     //要添加的元素： 0x0055   ddd   555
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null){
					
	   //等号的右边：当前要添加的值
	  //等号的左边：0x0044的值
		e.value = value;
				}
                afterNodeAccess(e);
                return oldValue;
            }
        }
		
        //threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12
        if (++size &gt; threshold){
			 resize();
		}
        
	//表示当前没有覆盖任何元素，返回null
        return null;
    }

put方法

  • 1、首先看table数组，不存在(null或len=0)则初始化(扩容)。存在继续
  • 2、看索引处，不存在则新增。存在继续
  • 3、判断索引处的值，相等则记录。不等继续
  • 4、判断是红黑树的话，走红黑树
  • 5、判断是链表的话，走链表
  • 6、判断超阈值，则扩容

1. 数组位置为 null

  • 当我们往 HashMap 中插入一个新的键值对时，首先会计算出键的哈希值，通过 hash() 方法来进行计算。
  • 然后，putVal() 方法会根据计算得到的哈希值计算出该键值对应该插入数组的位置（用 tab[i] 表示）。如果该位置是 null，说明该位置没有任何元素，那么新的键值对就直接插入到该位置。
  • 举例：
    当调用 put("aaa", 111) 时，"aaa" 的哈希值（假设为 0x0011）会计算出来，然后通过 tab[0x0011] 来判断当前位置。如果该位置是 null，就会创建一个新的节点，将 key="aaa"，value=111 插入到这个位置。

2. 数组位置不为 null，键不重复，挂在下面形成链表或红黑树

  • 如果数组中某个位置已经有值，即 tab[i] 不为 null，这时会检查该位置的键是否与当前要插入的键相同。如果键不相同，则会将新的键值对挂在该位置的后面，形成一个链表或红黑树。
  • 链表会在该位置后面依次插入新的节点，而红黑树会在链表长度超过阈值时转换为红黑树结构来提高查找效率。
  • 举例：
    当调用 put("bbb", 222) 时，假设 tab[0x0022] 位置已经被 0x0011 aaa 111 占用，"bbb" 的哈希值不同，因此会继续寻找下一个位置，或者在该位置后面形成一个链表，依次挂载 bbb 的键值对。

3. 数组位置不为 null，键重复，元素覆盖

  • 如果数组中该位置的键值对已经存在，而且该位置的键和当前插入的键相同，HashMap 会直接覆盖原来的值，替换成新的值。
  • 这时会判断当前数组中该位置的键是否和要插入的键相同。如果相同，则会直接用新的值覆盖原来的值，而不再插入新的节点。
  • 举例：
    当调用 put("ccc", 333) 时，假设 tab[0x0033] 位置已经被 0x0033 ccc 333 占用，"ccc" 的哈希值相同，且键相同，因此直接用新的值 333 覆盖旧的值。此时 tab[0x0033] 仍然是 ccc，但是值会变为新的 333。

总结

在 HashMap 的 put 方法中，插入数据时会经历以下几个步骤：

  1. 计算哈希值：使用 hash() 方法计算键的哈希值。

  2. 检查数组位置：根据哈希值计算数组的索引 i，检查 tab[i] 位置。

  3. 插入操作

    ：

    • 如果该位置为空（null），直接插入新的节点。
    • 如果该位置已有节点，并且键不同，则在链表或红黑树中继续查找插入。
    • 如果键相同，则替换旧的值。

这种方式保证了 HashMap 的查找效率，同时通过链表和红黑树的机制有效地解决了哈希冲突的问题。

更多详解参考

Java集合(五): HashMap源码剖析-CSDN博客