HashMap

• 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。