hashMap

发表于   |   更新于 | 分类于 ， ，

概要

关于HashMap的几个基本问题：

  1. hashMap的工作原理？
  2. hashMap可以接收key为null的键值对吗？hashTable可以接收key为null的键值对吗？
  3. hashMap的负载因子是做什么的？
  4. hashMap在JDK7和JDK8中的区别是什么？
  5. 简述HashMap的put方法的过程
  6. 简述HashMap的get方法的过程
  7. 什么时候会使用HashMap？他有什么特点？
  8. 你知道HashMap的工作原理吗？
  9. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
  10. 你知道hash的实现吗？为什么要这样实现？
  11. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

常见问题

  • 什么时候会使用HashMap？他有什么特点？
    需要保存key-value形式的键值对时，需要要使用HashMap，或者我们希望通过key快速查询到它所对应的value时，就会使用HashMap
    HashMap的特点：将key散列到表中，使用key的散列值查询元素，理想情况下，查询元素的时间复杂度是常数级别；通常情况下，保存key、value时，如果需要保存的key已经存在于散列表中，后面的值会覆盖前面的值；HashMap的键和值都允许是null，HashMap保存元素的最大值是Integer.MAX_VALUE；

在JDK7和JDK8中最大的区别就是

JDK8优化了当发生严重hash冲突时的查询优化，当满足一定的条件，使用红黑树代替链表来存储数据

HashMap的工作原理

HashMap的工作原理就是通过计算key的hash值，将key、value保存到对应的hash桶中，如果发生hash冲突，就用链表的方式将这些key、value连接起来；
访问某个key、value时，同样的方式，先计算key的hash值，从而定位key、value所在的hash桶

put方法的过程

  1. 判断数据是否为空，为空就resize，resize方法中包含了HashMap的初始化代码
  2. 通过hash方法计算key的hash值，确定桶的位置，如果索引位置的桶内元素为空，就将数据保存到该位置
  3. 如果桶内已经有元素了，判断该元素的key的hash是否与被插入的key的hash是否相等，以及key是否相等，如果相等，则替换值
  4. 如果不相等，再判断该节点是否是红黑树的节点，如果是，则调用添加树节点的方法插入数据
  5. 如果不是红黑树节点，则循环遍历链表，找到与key相等的节点就覆盖它的值，反之，则新增一个节点，链在链表的后面
  6. 在判断链表长度是否超过TREEFIY_THRESHOLD的值，如果超过了，就将链表树形化，
  7. 最后判断HashMap的容量是否超过了threshold, 如果超过了，就扩容

get方法的过程

  1. 如果HashMap中的table为空，或者key经过hash方法计算后的hash值所映射的桶为空，就返回空
  2. 反之，则判断桶里的元素的key的hash值、key值是否相等，如果相等，直接返回该元素
  3. 如果不相等，则判断该元素的下一个节点是否为空，如果为空，则返回空，如果不为空
  4. 则判断桶中的元素是否是TreeNode，如果是，则调用获取树节点的方法返回数据
  5. 反之，则遍历链表

hashMap的定义

hashMap是一种散列表，根据key的hash值被散列到表的不同位置，如果发生hash冲突，冲突的元素会以链表的形式存储

put(K k, V v)

查看put方法的源码，可以看出，hashMap是允许key为null的

1
2
3
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

查看hash方法的源码，我们知道如果key为null，那么hash值是0，否则会调用key的hashCode方法计算key的hash值（这也是为什么要重写key的hashCode方法的原因），并将hash值与它的高16位进行异或操作

1
2
3
4
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

当调用hashMap的put方法保存键值对时，通过hash方法重新计算key的hash值，如果hash值散列到散列表的索引处没有没有发生hash冲突，则将键值对保存即可,下面是putVal方法的代码片段

1
2
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

如果发生hash冲突，判断hash值所对应的散列表位置的元素是不是TreeNode（jdk版本1.8），如果是，直接调用添加一个TreeNode节点，源码片段如下

1
2
else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

如果fa’shegn不是TreeNode，

参考资料

Java中HashMap的UML类图

HashMap类图