HashMap学习

HashMap

基本认识

HashMap 的底层数据结构

我们现在用的都是 JDK 1.8，底层是由“数组+链表+红黑树”组成，而在 JDK 1.8 之前是由“数组+链表”组成。
为什么要改成“数组+链表+红黑树”

主要是为了提升在 hash 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)，而使用红黑树是 O(logn)。
在什么时候用链表？什么时候用红黑树？

对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。
为什么链表转红黑树的阈值是8？

对于 HashMap 也是同样的道理，简单来说，阈值为8是在时间和空间上权衡的结果

红黑树节点大小约为链表节点的2倍，在节点太少时，红黑树的查找性能优势并不明显，付出2倍空间的代价作者觉得不值得。

到8个节点时，红黑树的性能优势也会开始展现出来，因此8是一个较合理的数字。
那为什么转回成链表节点是用的6而不是复用8？

如果我们设置节点多于8个转红黑树，少于8个就马上转链表，当节点个数在8徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗。
那 HashMap 有哪些重要属性？分别用于做什么的？

除了用来存储我们的节点 table 数组外，HashMap 还有以下几个重要属性：1）size：HashMap 已经存储的节点个数；2）threshold：扩容阈值，当 HashMap 的个数达到该值，触发扩容。3）loadFactor：负载因子，扩容阈值 = 容量 * 负载因子，默认值是0.75。
threshold 除了用于存放扩容阈值还有其他作用吗？

默认初始容量是16。HashMap 的容量必须是2的N次方，HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。
HashMap 的插入流程是怎么样的？
计算 key 的 hash 值，是怎么设计的？

拿到 key 的 hashCode，并将 hashCode 的高16位和 hashCode 进行异或（XOR）运算，得到最终的 hash 值。
1
2
3
4
5

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashMap 是线程安全的吗？

不是。HashMap 在并发下存在数据覆盖、遍历的同时进行修改会抛出 ConcurrentModificationException 异常等问题，JDK 1.8 之前还存在死循环问题。

而 JDK 1.8 之后采用的是“尾插法”，扩容后节点顺序不会反掉，不存在死循环问题。

遍历

在foreach循环中使用entries来遍历

Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 

for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}

遍历map中的键

1
2
3

for (Integer key : map.keySet()) {
	System.out.println("Key = " + key);
}

遍历map中的值

1
2
3

for (Integer value : map.values()) {
    System.out.println("Value = " + value); 
}

使用Iterator遍历使用泛型(推荐)

Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator(); 

while (entries.hasNext()) { 
    Map.Entry<Integer, Integer> entry = entries.next();
    System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
 
}

不使用泛型：
Map map = new HashMap();
 
Iterator entries = map.entrySet().iterator();
while (entries.hasNext()) {
    Map.Entry entry = (Map.Entry) entries.next();
    Integer key = (Integer)entry.getKey(); 
    Integer value = (Integer)entry.getValue(); 
    System.out.println("Key = " + key + ", Value = " + value); 
}

通过键找值遍历（效率低）

Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 

for (Integer key : map.keySet()) { 
    Integer value = map.get(key); 
    System.out.println("Key = " + key + ", Value = " + value);
}

参考文档

HashMap