JDK1.7 数组+链表
JDK1.8 及以后，数组+链表/红黑树
链表长度>=8后转红黑树
key是唯一的，value可以重复
允许存储null键，null值
底层结构
数组，数组中每一项是一个链表
put
put方法，key存在的话会覆盖原值，返回旧值，key不存在的话，存放进数组中，返回null
put的时候，先对key的hashCode做了hash运算，通过hash后的值获取该key应该存放在数组中哪个下标位置处（indexFor方法，将得到的hash值h，通过h & (length-1)计算得出这个key应该在数组中的哪个位置），然后遍历该位置处的链表，替换原值，如果在链表中没有存在该key，则新增到链表的头部。
get
get的时候也是要先对key进行hash运算，得出hash值，获取该值在数组中的下标位置，然后遍历数组该位置的链表，hash值相同并且key值相同，返回链表该处的值。
hash
对key的值再做一次hash，是为了让其分布更加散列，计算得出的数组下标分布更加均匀。
hashMap的容量，为什么是2的n次幂
1、位运算比模运算快的多，
2、length如果是2的幂，length - 1就是一个奇数，并且这个数字转换为二进制低位都是1，在做&运算的时候，分布的更加散列，
3、只有当length是2的幂的时候，h & (length - 1) 与 h % length 结果是一致的，
做了个实验说明第二点--分布的更加散列
public class Main {
public static void main(String[] args) {
// hashMap容量
// int initialCapacity = 63;
int initialCapacity = 64;
// int initialCapacity = 66;
for (int i = 1; i < 100; i++) {
// hashMap中的hash算法
int hash = hash(i);
System.out.println( i + "--在数组中的下标--" + ((initialCapacity - 1) & hash));
}
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
}
举了3个数字，63-单数，64-2的幂，66-偶数，来说明只有2的幂的时候，分布的才会更加散列，
展开查看
```
1--在数组中的下标--1
2--在数组中的下标--2
3--在数组中的下标--3
4--在数组中的下标--4
5--在数组中的下标--5
6--在数组中的下标--6
7--在数组中的下标--7
8--在数组中的下标--8
9--在数组中的下标--9
10--在数组中的下标--10
11--在数组中的下标--11
12--在数组中的下标--12
13--在数组中的下标--13
14--在数组中的下标--14
15--在数组中的下标--15
16--在数组中的下标--16
17--在数组中的下标--17
18--在数组中的下标--18
19--在数组中的下标--19
20--在数组中的下标--20
21--在数组中的下标--21
22--在数组中的下标--22
23--在数组中的下标--23
24--在数组中的下标--24
25--在数组中的下标--25
26--在数组中的下标--26
27--在数组中的下标--27
28--在数组中的下标--28
29--在数组中的下标--29
30--在数组中的下标--30
31--在数组中的下标--31
32--在数组中的下标--32
33--在数组中的下标--33
34--在数组中的下标--34
35--在数组中的下标--35
36--在数组中的下标--36
37--在数组中的下标--37
38--在数组中的下标--38
39--在数组中的下标--39
40--在数组中的下标--40
41--在数组中的下标--41
42--在数组中的下标--42
43--在数组中的下标--43
44--在数组中的下标--44
45--在数组中的下标--45
46--在数组中的下标--46
47--在数组中的下标--47
48--在数组中的下标--48
49--在数组中的下标--49
50--在数组中的下标--50
51--在数组中的下标--51
52--在数组中的下标--52
53--在数组中的下标--53
54--在数组中的下标--54
55--在数组中的下标--55
56--在数组中的下标--56
57--在数组中的下标--57
58--在数组中的下标--58
59--在数组中的下标--59
60--在数组中的下标--60
61--在数组中的下标--61
62--在数组中的下标--62
63--在数组中的下标--63
64--在数组中的下标--0
65--在数组中的下标--1
66--在数组中的下标--2
67--在数组中的下标--3
68--在数组中的下标--4
69--在数组中的下标--5
70--在数组中的下标--6
71--在数组中的下标--7
72--在数组中的下标--8
73--在数组中的下标--9
74--在数组中的下标--10
75--在数组中的下标--11
76--在数组中的下标--12
77--在数组中的下标--13
78--在数组中的下标--14
79--在数组中的下标--15
80--在数组中的下标--16
81--在数组中的下标--17
82--在数组中的下标--18
83--在数组中的下标--19
84--在数组中的下标--20
85--在数组中的下标--21
86--在数组中的下标--22
87--在数组中的下标--23
88--在数组中的下标--24
89--在数组中的下标--25
90--在数组中的下标--26
91--在数组中的下标--27
92--在数组中的下标--28
93--在数组中的下标--29
94--在数组中的下标--30
95--在数组中的下标--31
96--在数组中的下标--32
97--在数组中的下标--33
98--在数组中的下标--34
99--在数组中的下标--35
```
展开查看
```
1--在数组中的下标--0
2--在数组中的下标--2
3--在数组中的下标--2
4--在数组中的下标--4
5--在数组中的下标--4
6--在数组中的下标--6
7--在数组中的下标--6
8--在数组中的下标--8
9--在数组中的下标--8
10--在数组中的下标--10
11--在数组中的下标--10
12--在数组中的下标--12
13--在数组中的下标--12
14--在数组中的下标--14
15--在数组中的下标--14
16--在数组中的下标--16
17--在数组中的下标--16
18--在数组中的下标--18
19--在数组中的下标--18
20--在数组中的下标--20
21--在数组中的下标--20
22--在数组中的下标--22
23--在数组中的下标--22
24--在数组中的下标--24
25--在数组中的下标--24
26--在数组中的下标--26
27--在数组中的下标--26
28--在数组中的下标--28
29--在数组中的下标--28
30--在数组中的下标--30
31--在数组中的下标--30
32--在数组中的下标--32
33--在数组中的下标--32
34--在数组中的下标--34
35--在数组中的下标--34
36--在数组中的下标--36
37--在数组中的下标--36
38--在数组中的下标--38
39--在数组中的下标--38
40--在数组中的下标--40
41--在数组中的下标--40
42--在数组中的下标--42
43--在数组中的下标--42
44--在数组中的下标--44
45--在数组中的下标--44
46--在数组中的下标--46
47--在数组中的下标--46
48--在数组中的下标--48
49--在数组中的下标--48
50--在数组中的下标--50
51--在数组中的下标--50
52--在数组中的下标--52
53--在数组中的下标--52
54--在数组中的下标--54
55--在数组中的下标--54
56--在数组中的下标--56
57--在数组中的下标--56
58--在数组中的下标--58
59--在数组中的下标--58
60--在数组中的下标--60
61--在数组中的下标--60
62--在数组中的下标--62
63--在数组中的下标--62
64--在数组中的下标--0
65--在数组中的下标--0
66--在数组中的下标--2
67--在数组中的下标--2
68--在数组中的下标--4
69--在数组中的下标--4
70--在数组中的下标--6
71--在数组中的下标--6
72--在数组中的下标--8
73--在数组中的下标--8
74--在数组中的下标--10
75--在数组中的下标--10
76--在数组中的下标--12
77--在数组中的下标--12
78--在数组中的下标--14
79--在数组中的下标--14
80--在数组中的下标--16
81--在数组中的下标--16
82--在数组中的下标--18
83--在数组中的下标--18
84--在数组中的下标--20
85--在数组中的下标--20
86--在数组中的下标--22
87--在数组中的下标--22
88--在数组中的下标--24
89--在数组中的下标--24
90--在数组中的下标--26
91--在数组中的下标--26
92--在数组中的下标--28
93--在数组中的下标--28
94--在数组中的下标--30
95--在数组中的下标--30
96--在数组中的下标--32
97--在数组中的下标--32
98--在数组中的下标--34
99--在数组中的下标--34
```
展开查看
```
1--在数组中的下标--1
2--在数组中的下标--0
3--在数组中的下标--1
4--在数组中的下标--0
5--在数组中的下标--1
6--在数组中的下标--0
7--在数组中的下标--1
8--在数组中的下标--0
9--在数组中的下标--1
10--在数组中的下标--0
11--在数组中的下标--1
12--在数组中的下标--0
13--在数组中的下标--1
14--在数组中的下标--0
15--在数组中的下标--1
16--在数组中的下标--0
17--在数组中的下标--1
18--在数组中的下标--0
19--在数组中的下标--1
20--在数组中的下标--0
21--在数组中的下标--1
22--在数组中的下标--0
23--在数组中的下标--1
24--在数组中的下标--0
25--在数组中的下标--1
26--在数组中的下标--0
27--在数组中的下标--1
28--在数组中的下标--0
29--在数组中的下标--1
30--在数组中的下标--0
31--在数组中的下标--1
32--在数组中的下标--0
33--在数组中的下标--1
34--在数组中的下标--0
35--在数组中的下标--1
36--在数组中的下标--0
37--在数组中的下标--1
38--在数组中的下标--0
39--在数组中的下标--1
40--在数组中的下标--0
41--在数组中的下标--1
42--在数组中的下标--0
43--在数组中的下标--1
44--在数组中的下标--0
45--在数组中的下标--1
46--在数组中的下标--0
47--在数组中的下标--1
48--在数组中的下标--0
49--在数组中的下标--1
50--在数组中的下标--0
51--在数组中的下标--1
52--在数组中的下标--0
53--在数组中的下标--1
54--在数组中的下标--0
55--在数组中的下标--1
56--在数组中的下标--0
57--在数组中的下标--1
58--在数组中的下标--0
59--在数组中的下标--1
60--在数组中的下标--0
61--在数组中的下标--1
62--在数组中的下标--0
63--在数组中的下标--1
64--在数组中的下标--64
65--在数组中的下标--65
66--在数组中的下标--64
67--在数组中的下标--65
68--在数组中的下标--64
69--在数组中的下标--65
70--在数组中的下标--64
71--在数组中的下标--65
72--在数组中的下标--64
73--在数组中的下标--65
74--在数组中的下标--64
75--在数组中的下标--65
76--在数组中的下标--64
77--在数组中的下标--65
78--在数组中的下标--64
79--在数组中的下标--65
80--在数组中的下标--64
81--在数组中的下标--65
82--在数组中的下标--64
83--在数组中的下标--65
84--在数组中的下标--64
85--在数组中的下标--65
86--在数组中的下标--64
87--在数组中的下标--65
88--在数组中的下标--64
89--在数组中的下标--65
90--在数组中的下标--64
91--在数组中的下标--65
92--在数组中的下标--64
93--在数组中的下标--65
94--在数组中的下标--64
95--在数组中的下标--65
96--在数组中的下标--64
97--在数组中的下标--65
98--在数组中的下标--64
99--在数组中的下标--65
```
tableSizeFor 这个方法保证了hashMap中的容量始终是2的幂。
这个方法是计算得到一个比传过来的参数值大的，最近的2的幂。
resize -- 扩容
初始容量是16，负载因子是0.75，阈值时16*0.75 = 12
当hashMap的容量大于12的时候，就会触发扩容。
不是线程安全的
--
jdk1.8 为什么长度>=8后转红黑树
两个对象的hashCode相同会发生什么？
两个对象的hashCode相同时，应该要放在数组同一个下标位置，接着HashMap会遍历链表中的key值，若有key值相同的元素，则覆盖并返回原值，如果没有相同的key，则将该值添加在链表的表头。
如果两个对象的hashCode相同，如何获取值的？
如果两个对象hashCode相同，则遍历链表中的key，获取链表中存储的值。
为什么负载因子是0.75?
空间与时间的折中。
泊松分布
TODO
进制转换、位运算复习
