hashmap

hashmap的存储模式

hashmap

1.工作原理

通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

2.hash实现

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

3.put函数实现

1.对key值的hashcode再进行一次hash计算，然后根据当前的entry数组长度求出index。
2.如果没有发生碰撞则直接放到bucket中
3.如果碰撞了则以链表的形式放到bucket中
4.如果链表的长度>=8,则将转换为红黑树（转化时会判断是否<=阈值6，如果是则转为链表）
5.如果key已经存在则将oldvalue替换掉
6.如果bucket超过阈值（load factor*current capacity）就要resize

4.resize的实现

当put时如果发现目前的bucket占用已经超过阈值，就会resize。resize的过程中就是把bucket扩充为原来的二倍，阈值也扩大到原来的二倍。之后重新计算原来已经存在的entry的index，并放到新的bucket中。因为扩充的特性，元素的新位置要么在原索引处要么在oldIndex+newcap处。
扩容之后计算下标

hash计算 重新计算的下标与原来的相比在于高位多1bit，新的下标可以如图所示 前后索引对比
因此只要新增的bit为0则依旧放在原索引位置，为1则变成“原索引+oldcap”，下图为16扩充为32的resize示意图 16扩充至32

5.key值不可变

自定义key值的时候其值不可以变化，否则将会出现数据无法读取，丢失。

参考
http://coding-geek.com/how-does-a-hashmap-work-in-java/

https://www.cnblogs.com/mzc-blogs/p/5800084.html