1、map->hashmap HashMap 底层是基于数组和链表实现的。其中有两个重要的参数：容量；负载因子.容量的默认大小是 16，负载因子是 0.75，当 HashMap 的 size > 16*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。
key是采用传入参数的hashcode 在进行取模运算，在参数的hash是2^n时候跟位运算是一样的，所以采用位运算来做取模。

初始化 构造方法

首先，int n = cap -1是为了防止cap已经是2的幂时，执行完后面的几条无符号右移操作之后，返回的capacity是这个cap的2倍，因为cap已经是2的幂了，就已经满足条件了。 如果不懂可以往下看完几个无符号移位后再回来看。
比如容量是8 符合2^n次方，但是也满足了扩容。
所以不直接用2^n来，而是采用位运算

原始计算： n=n-1 -> 7=8-1
原始值 0000 1000

| n|>>>1 右移1位 0000 0111

| 或运算 0000 1000

值         0000 1111

| n|>>>2 右移2位 0000 0011

| 或运算 0000 1111

值为   0000 1111    

| n|>>>4 右移2位 0000 0011

| 或运算 0000 1111

值为   0000 1111                

| n|>>>8 右移8位 0000 0011

| 或运算 0000 1111

值为   0000 1111    

| n|>>>16右移16位 0000 0011

| 或运算 0000 1111

值为   0000 1111                            

最终值为 n=n+1 -> 16=15+1 满足2^n-1

首先会将传入的 Key 做 hash 运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标。

由于在计算中位运算比取模运算效率高的多，所以 HashMap 规定数组的长度为 2^n 。这样用 2^n - 1 做位运算与取模效果一致，并且效率还要高出许多。

由于数组的长度有限，所以难免会出现不同的 Key 通过运算得到的 index 相同，这种情况可以利用链表来解决，HashMap 会在 table[index]处形成链表，采用头插法将数据插入到链表中

hashset

hashset是将hashmap整个对象当成key存储，所以hashset的key就无法重复。