关于jdk8的hashmap

迷南。 2022-10-10 12:52 168阅读 0赞

## 标题链表大于8且数组长度大于64才会将链表转为红黑树 ##

如果仅仅是链表长度大于8,而数组长度小于64,则会进行数组扩容2倍,来重新排列数组所有值

## 标题hashmap的默认长度必须为2的n次方,即使传参长度设置为非2的n次方时,仍然会寻找大于其传参最近的2的n次方作为数组的长度, ##

> 之所以会使用2的n次方,是因为在计算最后的存放位置的下标时,思路是使用>>> 然后^运算 最后&运算 ,  
> 前面的>>>然后^运算这两步主要是为了取到比较随机的数,而之后用&运算主要思路是用刚刚得到的随机数和数组长度取余来得到下标,但是取余运算对于计算机来说效率是不佳的,而sun大神发现取余时可以用随机数和数组长度做&运算代替,但是仅限于数组长度是2的n次方的时候,所以也就是说,只要数组的长度是2的n次方,则可以用&运算来取得余数,而&运算时二进制运算肯定要比取余运算快的多,  
> 所以,这也是为什么数组长度要是2的n方的原因,只有这样的时候,才可以利用&运算来高效率的取余.
> 
> 一般我们利用hash码, 计算出在一个数组的索引, 常用方式是”h % length”, 也就是求余的方式 . 可能是这种方式效率不高,  
> SUN大师们发现, “当容量一定是2^n时，h & (length - 1) == h % length” . 按位运算特别快 .

#### 他是怎么做到:如果传进去的不是2的n次方,而转为成大于本身的最接近的2的n次方呢? ####

static final int tableSizeFor(int cap) { 
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
        
    这里逻辑参考:https://blog.csdn.net/qq_27731689/article/details/95865083?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-4.control&spm=1001.2101.3001.4242

**这是hashmap将指定长度可以转换为2的幂的流程**  
![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oCdfuW_tQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

> 问题?:通过看如上代码 为什么要先cap-1,然后在做接下来的处理呢? 如上代码:根据重复的  
> 无符号右移,就会转为大于自己的最接近的2的n次方,所以,如果传进来的正好是2的n次方,就会变成大于本身2的n次方,而实际上,如果已经是2的n次方了,我们就可以直接使用了,而如果不减一,将变成比自己大的2的n次方,减去1的目的是为了处理传进来的正好是2的幂的情况

## put 的时候如果计算出下标的呢? ##

### 这个问题分为两步 ###

**1.先取到hash值**

static final int hash( Object key) { 
            int h;
            /*
          * h = key.hashCode();
          * h = h ^ (h >>> 16)
            */
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

从代码可以看出他是通过key的hash值与key的hash值右移16位进行异或取到的  
**2.根据第一步获取到的hash计算下标**

> 使用取到的hash值和数组长度-1做与&运算(这里等同于取模,之所以使用&,是因为二进制运算运算效率更高)

## 为什么扩展因子是0.75?而不是存储满了不够再进行扩容 ##

> **如果负载因子过小**,很轻易的导致达到负载因子而频繁扩容,导致大量空间被浪费

> **如果负载因子太大**:因为在每次扩容时,都需要将所有的数据重新计算,重新去排列,这些都是需要时间成本的,而负载因子过大甚至如果等到数组满了才去扩容的话,因为很难达到到负载因子,而导致难于扩容而产生大量hash碰撞,可能有一些链表中的数据量已经很长了,已经产生大量红黑树了,

## 为什么链表在达到"8"时转为了红黑树呢(前提是数组已经大于64)? ##

##### 1.首先为什么是8呢?而不是7或者9呢? #####

> 首先目的是什么?  
> 是为了防止同一链表过长,导致查询效率下降

> 红黑树本身存储的时候是需要成本的基本上红黑树的占用空间时链表的2倍,从维护和存储空间上都要更复杂一些,所以数量少的话,我们不建议去转为红黑树的,是时间和空间的上的权衡,  
> 之所以是8,是因为数据在存储的时候概率是符合泊松分布的,也就是说实际上,一个链表在达到8而转化为红黑树的概率是极低的.  
> 从此处也可以看到,其实作者本身并不太愿意转为红黑树,而是链表过长时,采用这种方案来减少了大量的查询时间,

## 为什么链表增加元素时超过8转为红黑树,而减少元素却是小于6才转回为链表 ##

> 因为如果都设置为8的话,有可能频繁的导致某个位置的在红黑树和链表两种结构频繁互转,毕竟转换也是成本

# hashmap在扩容时,肯定是需要重新排列所有的元素的位置把,那么他是怎么做的呢? #

> hashmap在扩容时,并不是遍历一遍,然后像增加元素时那样,从新计算hash然后使用&取余运算来计算元素在新数组上的位置,而是使用了一种效率更高但是仍然能达到目的的一样方式  
> 他是这么做的,设计的非常巧妙,因为hashmap每次扩容时都是上次容量的2倍,与原来的hash&(n-1)只相差一个bit位.,所以正好利用这个特性计算出恰好的特性,新的元素要不在**新**数组的 **原位置**,要不在**新**数组的 **原位置+旧容量 的位置**

> **那什么时候是原位置,什么时候是原位置+旧容量呢?**  
> 由此可见,在rehash时,并不需要重新计算hash然后计算下标,  
> 而是用hash & oldCap(元素hash&原数组长度) 得到的最高位如果是0,那就是原下标位置,如果得到的最高位是1,那么这个元素在新的数组的新位置就是 旧下标位置+旧数组长度=新的数组下标,  
> 所以在新的数组上计算下标 不需要通过像之前那样 >>> ^ & 运算来计算下标位置,

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oCdfuW_tQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20221005/7cac9bb29ded4c8fb1bd5179ae61b958.png