正文

HashMap、HashTable、ConcurrentHashMap、TreeMap、LinkedHashMap、WeakHashMap区别

IP云
IP云V管理员/4 阅读
11/29
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1. HashMap

标准链地址法实现(下图)。数组方式存储 key/value ，线程非安全，允许 null 作为 key 和 value ， key 不可以重复， value 允许重复，不保证元素迭代顺序是按照插入时的顺序， key 的 hash 值是先计算 key 的 hashcode 值，然后再进行计算，每次容量扩容会重新计算所以 key 的 hash 值，会消耗资源，要求 key 必须重写 equals 和 hashcode 方法。默认初始容量 16 ，加载因子 0.75 ，扩容为旧容量乘 2 ，查找元素快，如果 key 一样则比较 value ，如果 value 不一样，则按照链表结构存储 value 。如果需要同步，可以用 Collections 的 synchronizedMap 方法( Map m = Collections.synchronizedMap(new HashMap(…)); )。使 HashMap 具有同步的能力，或者使用 ConcurrentHashMap 。

JDK 1.8之后，加入了static final int TREEIFY_THRESHOLD = 8 ; ,当同一桶内元素个数超过8个，就会将链表结构进行树化。 

    /**

     * The bin count threshold for using a tree rather than list for a

     * bin.  Bins are converted to trees when adding an element to a

     * bin with at least this many nodes. The value must be greater

     * than 2 and should be at least 8 to mesh with assumptions in

     * tree removal about conversion back to plain bins upon

     * shrinkage.

     */

    static final int TREEIFY_THRESHOLD = 8;

2. HashTable

线程安全，不允许有 null 的键和值，线程安全的，它在所有涉及到多线程操作的都加上了 synchronized 关键字来锁住整个 table ，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是安全的，但是无疑是效率低下的。

3. ConcurrentHashMap

HashTable 有很多的优化空间，锁住整个 table 这么粗暴的方法可以变相的柔和点，比如在多线程的环境下，对不同的数据集进行操作时其实根本就不需要去竞争一个锁，因为他们不同 hash 值，不会因为 rehash 造成线程不安全，所以互不影响，这就是锁分离技术，将锁的粒度降低，利用多个锁来控制多个小的 table ，这就是 ConcurrentHashMap JDK1.7版本的核心思想。

JDK1.7的实现

在JDK1.7版本中， ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成，如下图所示：

Segment 数组的意义就是将一个大的 table 分割成多个小的 table 来进行加锁，也就是上面的提到的锁分离技术，而每一个 Segment 元素存储的是 HashEntry 数组+链表 ，这个和 HashMap 的数据存储结构一样

JDK1.8的实现

JDK1.8的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树 的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap ，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。

4. TreeMap

TreeMap 实现 SortMap 接口，基于红黑二叉树的 NavigableMap 的实现，线程非安全，不允许 null ， key 不可以重复， value 允许重复，存入 TreeMap 的元素应当实现 Comparable 接口或者实现 Comparator 接口，会按照排序后的顺序迭代元素，两个相比较的 key 不得抛出 classCastException 。主要用于存入元素的时候对元素进行自动排序，迭代输出的时候就按排序顺序输出

5. LinkedHashMap

LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的。也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比 HashMap 慢，不过有种情况例外，当 HashMap 容量很大，实际数据较少时，遍历起来可能会比 LinkedHashMap 慢，因为 LinkedHashMap 的遍历速度只和实际数据有关，和容量无关，而 HashMap 的遍历速度和他的容量有关。

6. WeakHashMap

WeakHashMap ，从名字可以看出它是某种 Map ，允许 null 作为 key 和 value (Both null values and the null key are supported.)，非线程安全(this class is not synchronized)。它的特殊之处在于 WeakHashMap 里的 entry 可能会被 GC 自动删除，即使程序员没有调用 remove() 或者 clear() 方法。

更直观的说，当使用 WeakHashMap 时，即使没有显示的添加或删除任何元素，也可能发生如下情况：

  • 调用两次 size() 方法返回不同的值；
  • 两次调用 isEmpty() 方法，第一次返回 false ，第二次返回 true ；
  • 两次调用 containsKey() 方法，第一次返回 true ，第二次返回 false ，尽管两次使用的是同一个 key ；
  • 两次调用 get() 方法，第一次返回一个 value ，第二次返回 null ，尽管两次使用的是同一个对象。

WeekHashMap 的这个特点特别适用于需要缓存的场景 。在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。

要明白 WeekHashMap 的工作原理，还需要引入一个概念： 弱引用（WeakReference） 。Java中内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。GC判断某个对象是否可被回收的依据是， 是否有有效的引用指向该对象 。如果没有有效引用指向该对象（基本意味着不存在访问该对象的方式），那么该对象就是可回收的。这里的 “有效引用” 并不包括 弱引用 。也就是说， 虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，仅有弱引用指向的对象仍然会被GC回收 。

WeakHashMap 内部是通过弱引用来管理 entry 的，弱引用的特性对应到 WeakHashMap 上意味: 将一对 key, value 放入到 WeakHashMap 里并不能避免该 key 值被 GC 回收，除非在 WeakHashMap 之外还有对该 key 的强引用 。

相关阅读

目录[+]