HashMap学习



HashMap

基本认识

  1. HashMap 的底层数据结构

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

  2. 为什么要改成“数组+链表+红黑树”

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

  3. 在什么时候用链表?什么时候用红黑树?

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

  4. 为什么链表转红黑树的阈值是8?

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


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


    到8个节点时,红黑树的性能优势也会开始展现出来,因此8是一个较合理的数字。

  5. 那为什么转回成链表节点是用的6而不是复用8?

    如果我们设置节点多于8个转红黑树,少于8个就马上转链表,当节点个数在8徘徊时,就会频繁进行红黑树和链表的转换,造成性能的损耗。

  6. 那 HashMap 有哪些重要属性?分别用于做什么的?

    除了用来存储我们的节点 table 数组外,HashMap 还有以下几个重要属性:1)size:HashMap 已经存储的节点个数;2)threshold:扩容阈值,当 HashMap 的个数达到该值,触发扩容。3)loadFactor:负载因子,扩容阈值 = 容量 * 负载因子,默认值是0.75。

  7. threshold 除了用于存放扩容阈值还有其他作用吗?

    默认初始容量是16。HashMap 的容量必须是2的N次方,HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方,例如传 9,容量为16。

  8. HashMap 的插入流程是怎么样的?

  9. 计算 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);
    }
  10. HashMap 是线程安全的吗?

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

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

遍历

  1. 在foreach循环中使用entries来遍历
1
2
3
4
5
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());
}
  1. 遍历map中的键
1
2
3
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
  1. 遍历map中的值
1
2
3
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
  1. 使用Iterator遍历使用泛型(推荐)
1
2
3
4
5
6
7
8
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());

}
1
2
3
4
5
6
7
8
9
10
不使用泛型:
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);
}
  1. 通过键找值遍历(效率低)
1
2
3
4
5
6
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

打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  1. © 2020-2021 Lauy    湘ICP备20003709号

请我喝杯咖啡吧~

支付宝
微信