36°

HashMap底层分析

众所周知HashMap(无序,key不可以重复)的底层是数组+链表实现的。但是在jdk1.7和jdk1.8中稍有不同。

Base 1.7

其中有两个重要的参数:

  • 容量
  • 负载因子

容量的默认大小是 16,负载因子是 0.75,当 HashMap 的 size > 16*0.75 时就会发生扩容(容量和负载因子都可以自由调整)。而扩容这个过程涉及到 rehash、复制数据等操作,所以非常消耗性能。因此通常建议能提前预估 HashMap 的大小最好,尽量的减少扩容带来的性能损耗

put 方法

首先会将传入的 Key 做 hash 运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标。

由于在计算中位运算比取模运算效率高的多,所以 HashMap 规定数组的长度为 2^n 。这样用 2^n - 1 做位运算与取模效果一致,并且效率还要高出许多。

由于数组的长度有限,所以难免会出现不同的 Key 通过运算得到的 index 相同,这种情况可以利用链表来解决,HashMap 会在 table[index]处形成链表,采用头插法将数据插入到链表中。

get 方法

get 和 put 类似,也是将传入的 Key 计算出 index ,如果该位置上是一个链表就需要遍历整个链表,通过 key.equals(k) 来找到对应的元素。因为每次根据 key 的 hashcode 映射到 Entry 数组上,所以hashmap是无序的。

遍历方式

 Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator();
        while (entryIterator.hasNext()) {
            Map.Entry<String, Integer> next = entryIterator.next();
            System.out.println("key=" + next.getKey() + " value=" + next.getValue());
        }
Iterator<String> iterator = map.keySet().iterator();
        while (iterator.hasNext()){
            String key = iterator.next();
            System.out.println("key=" + key + " value=" + map.get(key));
    }</code></pre> 
map.forEach((key,value)->{
    System.out.println("key=" + key + " value=" + value);
});

强烈建议使用第一种 EntrySet 进行遍历。

第一种可以把 key value 同时取出,第二种还得需要通过 key 取一次 value,效率较低, 第三种需要 JDK1.8 以上,通过外层遍历 table,内层遍历链表或红黑树。

Base 1.8

在 JDK1.8 中对 HashMap 进行了优化: 当 hash 碰撞之后写入链表的长度超过了阈值(默认为8)并且 table 的长度不小于64(否则扩容一次)时,链表将会转换为红黑树

假设 hash 冲突非常严重,一个数组后面接了很长的链表,此时重新的时间复杂度就是 O(n) 。

如果是红黑树,时间复杂度就是 O(logn) 。

大大提高了查询效率。

简单总结下 HashMap:无论是 1.7 还是 1.8 其实都能看出 JDK 没有对它做任何的同步操作,所以并发会出问题(既线程不安全的),并发操作容易在一个桶上形成环形链表;这样当获取一个不存在的 key 时,计算出的 index 正好是环形链表的下标就会出现死循环

因此 JDK 推出了专项专用的 ConcurrentHashMap ,该类位于 java.util.concurrent 包下,专门用于解决并发问题。

想要深入了解的小伙伴可以自行参考:HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!

 

扩展

HashSet是一个不允许存储重复元素的集合,它的实现比较简单,只要理解了HashMapHashSet就水到渠成了。HashSet所有原理基本都是基于HashMap实现的

LinkedHashMap是有序的。它对HashMap进行了拓展,使用了双向链表来保证了顺序性。

 

本文由【如同相见恨晚】发布于开源中国,原文链接:https://my.oschina.net/u/3872440/blog/3072279

全部评论: 0

    我有话说: