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的幂的时候，分布的才会更加散列，
- 当初始容量为64时，i在数组中的分布情况：
展开查看
``` 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 ```- 当初始容量为63的时候，i在数组中的分布情况
展开查看
``` 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 ```- 当初始容量为66的时候，分布情况：
展开查看
``` 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
进制转换、位运算复习
