hashMap 底层原理

1.源码  

java1.7    hashMap 底层实现是数组+链表

java1.8 对上面进行优化  数组+链表+红黑树

1.hashmap 初始化时就生了一个长度为16 的数组。

　　1.1 为什么初始化时16   而不是8  或者4  ，其实8 也行4 也行，但是 我的java 是c语言写的，而c语言是由汇编语言，而汇编的语言来源是机器语言，而汇编的语言使用的就是16进制，对于经验而言，当然就选16喽。

2.hashmap  是怎么保存数据的。

　　　　在hashmap 中有这样一个结构

　　　　　　　　Node implenets Map.entity{

　　　　　　　　　　hash

　　　　　　　　　　key

　　　　　　　　　　value

　　　　　　　　　　next

　　　　　　　　} 

当我们像hashMap 中放入数据时，其实就是一个

Enity{

　　key

　　vaue

}

在存之前会把这个Entity  转成Node 

　　　　怎么转的如下：

  根据Entity 的key   通过hash  算出一个值  当成Node 的 hash  ,key vlaue  ,复制到Node 中，对于没有参数hash 冲突前，Node 的next 是null.

复制完成后，还需要通过Entity 对象的hash  算出  该 Entiry对象 具体应该放在 hashMap 的那个位置。计算如下  Hash&(lenth-1) 得到的值就是hashMap 对应具体的位置。（lentth是当前hashMap 的长度）。‘

 解决hash 冲突

　　　　就是不同的元素通过   Hash&(lenth-1) 公式算出的位置相同，现在就启动了链表（单项链表），挂在了当前位置的下面，而链表的元素怎么关联呢，就用到了Node  的next  ，next的值就是该链表下一个元素在内层中的地址。

　　　　jdk1.7  就是这样处理的，而到了 1.8  以后，就引用了红黑树，1.8以后这个链表只让挂7个元素，超过七个就会转成一个红黑树进行处理（最多是64，超多64 就会重新拆分）。

　　　　当红黑树下挂的节点小于等于6的时候，系统会把红黑树转成链表。 

 hashMap 扩容：

　　　　hashMap  会根据  当前的hashMap 的存储量达到 16*0.75=12 的时候，就是扩容  16*2=32  依次类推下去。2倍扩容。

　　　　扩容后元素是如何做到均匀分的。

 对上面的总结：

hashMap 底层原理

原文：https://www.cnblogs.com/xiaowangbangzhu/p/10445574.html