-
HashMap存储元素的关系结构图
image.png
image.png
package collection.map;
import java.util.HashMap;
import java.util.Map;
/**
* @author haishen
* @date 2019/2/26
*/
public class HashMapTest {
public static void main(String[] args) {
Map<String, String> hashMap = new HashMap();
hashMap.put(null, "1");
hashMap.put("1", "12");
hashMap.put("3",null);
hashMap.get("3");
System.out.println(hashMap.size());
}
}
image.png
- 设置默认的扩容因子，DEFAULT_LOAD_FACTOR = 0.75f;四分之三
put操作
image.png
- 计算元素key 的hash值；
- 调用putVal方法。
- key和value是可以为null的。
计算key的hash值
image.png
- key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值(4个字节，32位);
- 用这个散列值与这个散列值无符号右移16位的的值进行异或运算（相同为0，相反为1）。
- 可以看出key是可以为null的。
image.png
- “扰动函数”，右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。参考
putVal执行逻辑
image.png
- 如果表为空，或者表的长度为零，则先进行扩容逻辑；
- 根据key 的hash 值和数组容量大小-1的与操作的结果索引结果，如果该索引位置没有元素，则将新元素添加进去；
- 如果有元素，则说明出现了hash冲突，需要解决冲突，解决冲突的方式，
- 如果存在的节点和新添加的节点的hash值和key相同，确定值老节点，后续更新value即可
- 如果节点是树节点，走树节点解决冲突的逻辑；
- 以链表的形式添加节点，如果链表的节点长度超过8，链表转换从红黑树的数据结构。
- 如果链式节点索引到的节点和新添加的节点的hash值和key相同，确定是老的节点，后续更新value即可；
- 最后是已存在的节点则更新对应的value值。
- 判断当前map中记录的元素是否大于设置的阀值，如果大于，还需要进行扩容逻辑。
扩容逻辑
image.png
- 根据老数组的容量大小判断需要扩容的大小，如果没有设置初始值，则扩容大小为16，如果有初始值，在扩容大小为原容量的2倍；
- 创建一个新容量大小的数据；
- 循环遍历老数组，将老素组中的元素放到新的数组中去；
- 如果指定位置获取的元素没有后继节点，则将该老元素的赋值到该老元素的hash值与新数组大小减一进行与操作后的位置；
- 如果是树节点，则走树节点重新分配逻辑；
- 以上几种情况都不符合的话，说明该元素是有后继节点的，需要对后继节点进行重新hash；这个工程中定义了4个关键的Node对象，loHead（低位头节点）、loTail（低位尾节点）、hiHead（高位头节点）、hiTail（高位尾节点）；
- 整个doWhile循环体中做的事情就是判断拿到的节点的hsah值与老的数组容量的与操作结果是否为0，如果为零，则判断该元素还是在扩容前的位置，如果与操作结果不为0，则判断该元素的位置应该在扩容后的新增空间中，具体位置为该元素在（老数组容器中位置+老数组容量）的所指定的值；低位和高位的链式关系通过上面提到的4个关键的Node对象来指定；
- 最后节点的后继节点遍历完成之后，跳出循环体，将最终的低位头节点设置到扩容前的位置，将最终的高位头节点设置到扩容后的位置。
解决疑问
- 为什么判断拿到的节点的hsah值与老的数组容量的与操作结果是否为0，就可以区分元素是在扩容前还是在扩容后的位置？
- 为什么扩容后的位置为老数组容器中位置+老数组容量的值？
解答
- 首先明确，HashMap的容器大小为2的n次方；元素在数组中的位置是根据元素的hash值和和数组容量减一（对应的二进制值为全1）进行与操作后得到的值来确定的；元素的hash值的计算方式上文有提到，结论是这个值比较到大，大到会远远超出数组的大小，为了能够映射到数组内，所以进行了元素的hash值和数组容量减一的与操作，这个与操作的结果是映射到了数组容量范围内的值；
- 所以如果元素的hash值小于老数组容量，即hash值不需要截取就对应数组的某一个位置，那么这个元素的hash值与老数组容量（高位为1，低位全为0）进行与操作肯定为零；当数组容量是原来的2倍时，按位与操作更是零，低位还是原来的值，高位是零，所以还在老数组的位置；
- 所以如果元素的hash值不小于老数组容量，那么这个元素的hash值与老数组容量（高位为1，低位全为0）进行与操作时，按位与操作时低位还是原来的值，元素按位对应老数组容量最高位与操作结果为零时，高位为零，所以还在老数组的位置；元素对应老数组容量最高位不为零时，说明这个元素在数组容量最高位位置值的二进制值就是为1，在元素与新数组容量-1进行按位与操作获取索引位置时最高位为1，所以新所以的位置为（老数组容器中位置+老数组容量）。
- 总结就是新容量是老容量的2倍，其容量减一（全1）相比时新容量高位多了个1，当元素的hash与容量减一进行按位与操作时，如果对应新容量减一的高位为1，那么与操作之后的位置就比老容量的位置多了个老容量的大小。
get 操作
image.png
- 执行getNode方法，判断是否有返回值，最后返回查询结果。
image.png
- 根据key的hash值和容器长度-1 进行与操作索引数组元素；
- 如果索引的结果的hash值和key满足判断，这查找到节点，返回；
- 否则，判断如果索引的节点有后继节点，
- 判断如果过是树节点，走树节点查找逻辑；
- 如果不是树节点，走链式遍历逻辑，遇到hash值以及key和参数相同的节点则返回。
replace操作
image.png
- 通过getNode方法查找对应的节点，然后对value重新赋值。
remove操作
image.png
image.png
遍历操作
Set keys = hashMap.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
String key = (String) ite.next();
System.out.println("key:{" + key + "}--->value:{" + hashMap.get(key) + "}");
}
image.png
- iterator()对应的方法是KeyIterator；
image.png
- KeyIterator继承父类HashIterator
image.png
- HashIterato初始化时会通过doWhile操作，寻找第一个不为null的元素节点；
- 执行nextNode方法时，判断当前节点是否有后继节点，如果没有从当前节点的索引+1的位置开始返回第一个不为null的节点；
- 否则就是有后继节点，直接返回后继节点，有先循环遍历链表节点，遍历完成之后；
-
所以hashmap的元素遍历顺序如下图，元素的输出顺序和添加顺序是不一致的。
image.png
注意：JDK1.8后，除了对hashmap增加红黑树节点外，对原有造成死锁的关键原因点（新table复制在头端添加元素）改进为依次在末端添加新的元素。虽然JDK1.8后添加红黑树改进了链表过长查询遍历慢问题和resize时出现导致put死循环的bug，但还是非线性安全的，比如数据丢失等等。因此多线程情况下还是建议使用concurrenthashmap。
