hashmap详解

hashmap

1.存储key和value,  以节点对象思路存储
 class Node{
  private k  key;
  private v value;
   private next;
  final int hash;  //这个是用来处理hash算法
  }
 Node节点组建数组和链表以及红黑树

hash.PNG

初始化和插入数据

1.node对象创建时，会初始化数组，在put的时候进行判定，才会执行创建链表或者转化成链表红黑树，以及扩容操作

2.put的时候进行判定是否创建链表，然后才会创建链表或者红黑树。

3.put的时候放能节省空间，用的时候再创建

//时间换空间的思想，
具体过程：

1.首先初始化数组，初始化数组长度16

2.那么每次put操作，通过key和hash算法需要产生一个0-15的索引值

哈希算法

产生0-15的整数，数值尽可能不会重复，得到一个取值范尽可能大的整数，

产生0-15的整数三种思路：

 1.取模控制，控制这个整数在0-15内 通过取模控制  key.hashcode  % 16
 2.二进制位运算  0000-1111，数据和1111进行与操作，保留后四
 3.逻辑运算： （n-1）& hash 取后四位  n是数组长度

实际采用了充分散列的思想： 先异或，再与

hashcode高低16位，两者异或
key.hashcode ^ key.hashcode>>16  ，然后和1111与操作，保留后四

数组扩容：

1.当数组需要扩容时，需要是2的n次方，只有10000这样的减了才是全1，20就不行，hashMap会自适应调节成2的n次方。

2.数组扩容：当put了16*load_factor;就是放了12次数据,就会扩容，数组数据扩到2的n次方，也是上一次数据的二倍，load_factor默认=0.75;

扩容：

1.数组部分就直接复制到新的数组上

2.链表按照4位保留位的扩容后前一位的0，或者1；分成两部分贴进新的数组；

3.树就打乱重排

链表和红黑树

头插 ：产生的index相，就会插入链表，
当链表长度高，插入和查找效率太低了，因此采用了树，以空间换时间，
当链表长度大于8的时候，会转成红黑树，实际上8的情况极少
红黑树三次旋转必将平衡
平衡树构建麻烦，二叉树可能出现斜树，反而会退化成链表
源码：

public  int hash(Object value){
int h;
return (value==null)? 0 : Math.abs(seed*(cap-1)&(h=value.hashCode())^(h>>>16));
}