HashSet的add()方法解析
示例代码如下：【可用于后续的源码追踪】
1 public class HomeWork04 {
2 public static void main(String[] args) {
3 HashSet hashSet = new HashSet();
4 // 重复元素的不重复添加
5 hashSet.add("hello");
6 hashSet.add("world");
7 hashSet.add(new String("hello"));
8 hashSet.add(new Person("tom",20));
9 hashSet.add(new Person("jack",18));
10 hashSet.add(new Person("tom",20)); // 重复元素【重写了hashCode和equals之后】
11
12 // 超过阈值，hashSet如何扩容
13 for(int i = 0;i<8;i++){
14 hashSet.add(i);
15 }
16 hashSet.add(8);
17
18 // 单链表个数超过8个，单链表树化
19 for(int i = 0;i<9;i++){
20 hashSet.add(new A(i));
21 }
22
23
24 // 遍历hashSet集合
25 Iterator iterator = hashSet.iterator();
26 while (iterator.hasNext()) {
27 Object obj = iterator.next();
28 System.out.println(obj);
29 }
30
31 /**
32 * HashSet的无参构造器:
33 * public HashSet() {
34 * map = new HashMap<>(); // HashSet的底层还是HashMap【k-v】
35 * }
36 * $: 此时HashSet的table是[].
37 *
38 * 解析add()方法:
39 * 1) public boolean add(E e) { ==> 【HashSet】
40 * // 这里的PRESENT是固定的
41 * return map.put(e, PRESENT)==null;
42 * }
43 * $:这里的add()方法，本质就是调用HashMap的put方法，存储key值
44 *
45 * 2) public V put(K key, V value) { ==> 【HashMap】
46 * return putVal(hash(key), key, value, false, true);
47 * }
48 * $:首先计算key的hash值，通过key的hash值，在table中存放key
49 *
50 * 3) static final int hash(Object key) { ==> 【HashMap】
51 * int h;
52 * return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
53 * }
54 * $:返回key的hash值
55 *
56 * 4) final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
57 * boolean evict) { ==> 【HashMap】
58 * Node<K,V>[] tab; Node<K,V> p; int n, i;
59 * if ((tab = table) == null || (n = tab.length) == 0)
60 * // 首次进入putVal(),table是null,为table扩容
61 * n = (tab = resize()).length;
62 * if ((p = tab[i = (n - 1) & hash]) == null)
63 * // 正式添加元素:
64 * // key求出的hash值经过某种算法，得到table处的索引i
65 * // 以key创建新Node节点,将该节点存放到table[i]处。
66 * tab[i] = newNode(hash, key, value, null);
67 * else {
68 * // table不为空，并且添加的key映射到table数组中的table[i]不为空【冲突】
69 * Node<K,V> e; K k;
70 * // p = table[i],这里p即为相同索引在table的内容
71 * // 比较p.key的hash值和key的hash值，同时比较p.key是否与key相同。
72 * if (p.hash == hash &&
73 * ((k = p.key) == key || (key != null && key.equals(k))))
74 * e = p;
75 * // 判断p是否是树节点
76 * else if (p instanceof TreeNode)
77 * // p是树节点，则用putTreeVal()方式添加key
78 * e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
79 * else {
80 * // p仍然是Node类的节点,遍历table[i]处的链表【单链表】
81 * for (int binCount = 0; ; ++binCount) {
82 * // 是否到达最后一个节点
83 * if ((e = p.next) == null) {
84 * // 最后一个节点，插入key
85 * p.next = newNode(hash, key, value, null);
86 * // 链表的个数大于8就要树化
87 * if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
88 * treeifyBin(tab, hash);
89 * ① break;
90 * }
91 * // 遍历过程中，判断当前节点e.hash值是否与key的hash值相同，并且e.key是否与key相同
92 * if (e.hash == hash &&
93 * ((k = e.key) == key || (key != null && key.equals(k))))
94 * ② break;
95 * // 移动p,通过e = p.next，再次移动e
96 * // 通过对p.e的交替移动完成遍历。
97 * p = e;
98 * }
99 * }
100 *
101 * // 将新Node节点的value替换掉旧节点的value【PRESENT不影响】
102 * if (e != null) {
103 * V oldValue = e.value;
104 * if (!onlyIfAbsent || oldValue == null)
105 * e.value = value;
106 * afterNodeAccess(e);
107 * return oldValue;
108 * }
109 * }
110 * // 记录不重复添加的个数
111 * ++modCount;
112 * if (++size > threshold)
113 * // 如果当前的个数超过阈值，则需要扩容
114 * resize();
115 * afterNodeInsertion(evict);
116 * return null;
117 * }
118 *
119 * $ oldTab:旧table数组,oldCap:旧table的容量,oldThr:旧table的阈值
120 * newCap:新table的容量,newThr:新table的阈值,threshold:最终阈值
121 * 5) final Node<K,V>[] resize() { ==> 【HashMap】
122 * Node<K,V>[] oldTab = table;
123 * int oldCap = (oldTab == null) ? 0 : oldTab.length;
124 * int oldThr = threshold;
125 * int newCap, newThr = 0;
126 * if (oldCap > 0) {
127 * if (oldCap >= MAXIMUM_CAPACITY) {
128 * threshold = Integer.MAX_VALUE;
129 * return oldTab;
130 * }
131 * // 扩容机制：newCap:原数组长度的2倍，newThr:原阈值的2倍。
132 * else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
133 * oldCap >= DEFAULT_INITIAL_CAPACITY)
134 * newThr = oldThr << 1;
135 * }
136 * else if (oldThr > 0)
137 * newCap = oldThr;
138 * else {
139 * // 首次oldCap为0,oldThr为0
140 * // 为newCap赋初始值16,为newThr赋初始值0.75 * 16 = 12
141 * newCap = DEFAULT_INITIAL_CAPACITY;
142 * newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
143 * }
144 * if (newThr == 0) {
145 * float ft = (float)newCap * loadFactor;
146 * newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
147 * (int)ft : Integer.MAX_VALUE);
148 * }
149 * // threshold赋最终阈值
150 * threshold = newThr;
151 * // 按照newCap,为table分配存储空间
152 * Node<K, V>[] newTab = (Node<K,V>[])new Node[newCap];
153 * table = newTab;
154 * // oldTab不为空的情况:【复制数据】
155 * if (oldTab != null) {
156 * // 复制旧数组的数据到新数组中
157 * for (int j = 0; j < oldCap; ++j) {
158 * Node<K,V> e;
159 * if ((e = oldTab[j]) != null) {
160 * oldTab[j] = null;
161 * // 判断j索引的oldTab[j]是否是单个元素
162 * if (e.next == null)
163 * // 单个元素的话，计算索引值，存放到newTab中。
164 * newTab[e.hash & (newCap - 1)] = e;
165 * else if (e instanceof TreeNode)
166 * ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
167 * else {
168 * // j对应的oldTab[j]是单链表
169 * // 以下处理方式，尚未理解，仍需多看源码 ???
170 * Node<K,V> loHead = null, loTail = null;
171 * Node<K,V> hiHead = null, hiTail = null;
172 * Node<K,V> next;
173 * do {
174 * next = e.next;
175 * if ((e.hash & oldCap) == 0) {
176 * if (loTail == null)
177 * loHead = e;
178 * else
179 * loTail.next = e;
180 * loTail = e;
181 * }
182 * else {
183 * if (hiTail == null)
184 * hiHead = e;
185 * else
186 * hiTail.next = e;
187 * hiTail = e;
188 * }
189 * } while ((e = next) != null);
190 * if (loTail != null) {
191 * loTail.next = null;
192 * newTab[j] = loHead;
193 * }
194 * if (hiTail != null) {
195 * hiTail.next = null;
196 * newTab[j + oldCap] = hiHead;
197 * }
198 * }
199 * }
200 * }
201 * }
202 * return newTab;
203 * }
204 */
205 }
206 }
207 // 使得出现单链表
208 class A {
209 private int num;
210
211 public A(int num) {
212 this.num = num;
213 }
214
215 @Override
216 public int hashCode() {
217 return 100;
218 }
219
220 @Override
221 public String toString() {
222 return "A{" +
223 "num=" + num +
224 '}';
225 }
226 }
227
228 /**
229 * 自定义对象，重写hashCode()和equals()方法.
230 */
231 class Person {
232 private String name;
233 private int age;
234
235 public Person(String name, int age) {
236 this.name = name;
237 this.age = age;
238 }
239
240 @Override
241 public boolean equals(Object o) {
242 if (this == o) return true;
243 if (o == null || getClass() != o.getClass()) return false;
244 Person person = (Person) o;
245 return age == person.age && Objects.equals(name, person.name);
246 }
247
248 /**
249 * 1) public static int hash(Object... values) {
250 * return Arrays.hashCode(values);
251 * }
252 * 2) public static int hashCode(Object a[]) {
253 * if (a == null)
254 * return 0;
255 *
256 * int result = 1;
257 *
258 * for (Object element : a)
259 * result = 31 * result + (element == null ? 0 : element.hashCode());
260 *
261 * return result;
262 * }
263 * @return
264 */
265 @Override
266 public int hashCode() {
267 return Objects.hash(name, age);
268 }
269
270 @Override
271 public String toString() {
272 return "Person{" +
273 "name='" + name + '\'' +
274 ", age=" + age +
275 '}';
276 }
277 }
标签：hash,HashSet,int,return,add,key,table,java,null From： https://www.cnblogs.com/zwgitOne123/p/17020553.html