金题库

yPhantom 2019年10月16日 32次浏览

HashMap

说一说HashMap的数据结构

从结构实现来说,HashMap在1.7中是数组+链表,在1.8中是数组+链表+红黑树。

HashMap借助键值Key的hashcode值来组织存储,对于键值对<Key, Value>,内部将其封装成实现了Map.Entry<Key, Value>的Node类,这个Node可以理解为整个结构中一个个单元。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    
    Node(int hash, K key, V value, Node<K,V> next) {
        ...
    }
    ...
}

Node中定义了hash值,key,value以及next,链表就是通过这个next域来实现的。当插入键值对出现哈希冲突的时候,1.7中采用头插法,1.8中采用尾插法,形成链表。

当链表的长度大于8时,链表会转换为以TreeNode为单元(结点)的红黑树。TreeNode的实现如下:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    ...
}

当红黑树的总大小小于等于6的时候,又会转换为链表。

为什么不一直用树呢?为什么要选择6和8?为什么不用AVL树?

参考为什么Java8中HashMap链表使用红黑树而不是AVL树

这个应该是内存占用和存储的桶内查找复杂性之间的权衡,因为大部分的哈希函数很少产生冲突,为长度为3或者4维护树的代价比较昂贵。

AVL和红黑树的比较相似,但是AVL树在查询的场景下速度更快,红黑树在插入删除的场景下更快,AVL树通常应用在数据库方面。原因在于AVL在平衡数据结构的时候需要更多次操作。

HashMap如何利用hashcode建立索引的?

三步:取key的hashcode值、高位运算、取模运算

方法一:
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二:
static int indexFor(int h, int length) {  //jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

因为Java约定可以用hashcode值来唯一标识一个对象,因此计算索引的时候,我们首先想可以用hashcode对数组的长度取模,这样来说,数据分布是比较均匀的,但是模运算还是比较慢的。Java的实现是,首先让hashmap数组的长度是2的N次方,然后可以通过hashcode & (length - 1)达到和取模相同的效果。

最后当table的总长度比较小的时候,length - 1表示的二进制中的1也比较短,为了减小冲突,将hashcode的更多信息融入到有限的几位比特1中,JDK又将hashcode的高16位与低16位进行异或。

HashMap的扩容机制

hashmap中扩容机制比较值得注意的就是重新计算索引值。对于h & (length-1)来说,因为length翻倍了,也就相当于length - 1前面多了一个1,那么如果原来的hash值对应的那一位是1,则往后+oldCap的索引,否则保持不变。如果我们认为hashcode每一位都是均匀随机的话,那么重新分配的时候也是均匀随机的,因此扩容就均匀的分散了原来的节点。

另外一点就是JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是JDK1.8不会倒置。这是因为1.7是头插法,1.8是尾插法,尾插法的好处在于有一个原理叫局部性原理。简单来说最近被插入节点或者删除节点的位置很有可能再次被访问。这样可以改善性能。

HashMap的线程不安全性

参考掘金,一共有三种:

  • JDK1.8在给数组中链表的头赋值next节点时,可能会丢失另一线程中的结点。

  • JDK1.8中一个线程在resize中有一步,会将table赋值成一个扩容后的空数组,如果此时有一个线程调用get方法会得到null值

  • JDK1.7会出现死循环,JDK1.8修复了。

参考资料: