集合框架Map的分析

集合框架Map的分析

Map有哪些实现？HashTable、HashMap和TreeMap有什么区别？

一、基础知识

• Map的主要实现类有HashTable、HashMap和TreeMap，它们都是以键值对的方式存储数据的。主要继承关系如下图：

Map的继承关系图

• HashTable最大的特点就是线程安全的，同时不支持存放null键和null值，因为计算hash值的时候需要依赖key的hash值，但是null并没有hash值；由于HashTable的同步性能开销，效率比较低下，现在使用场景比较少了。

• HashMap基本和HashTable类似，区别是它不是线程安全的，从而性能更高，而且随着null越来越重要，HashMap可以支持存放null键和null值，是绝大场景下存储键值对数据的首选数据结构。

• TreeMap以及它的马甲TreeSet底层都是红黑树，提供了一种有序存放数据的方式，顺序可以是自然顺序也可以是根据对象的排序规则的顺序。

• LinkedHashMap就是在HashMap的基础上，增加了一个双向链表，来记录元素存入的顺序；

二、进阶知识

• 数据结构描述

  数组+链表组成的复合结构，通过hash值决定在数组中的寻址，如果寻址一样则以链表的形式存放，当链表长度超过阈值8的时候，链表数据结构将被改造为红黑树，从而降低查找时间；当元素个数少于等于8的时候，则会重新变回链表，因为红黑树的维护是需要性能消耗的；

HashMap数据结构示意图

• 如何计算hash值和计算寻址地址的

  用来定位寻址的hash值并不是完全由key的hashcode决定的，而是依赖它再进行一些计算：

      static final int hash(Object key) {
          int h;
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }
  

  这里使用key的hashcode的异或和移位运算，是为了降低冲突的概率；

  得到hash值后，再根据如下的方式获取寻址值：

  i = (n - 1) & hash
  

• 如何避免hash冲突

  一般而言，一个好的hash算法能尽量减少冲突，但是不能避免，hash冲突所造成的问题解决办法一般有开放寻址法、链表法、控制装载因子这三种形式，HashMap就是典型的使用了链表法，更加详细的内容可以参考散列表和散列函数

• 如何初始化和扩容

  初始化并不是在new HashMap的时候进行的，而是一种懒加载，只有在首次使用的时候才会初始化。什么时候是首次使用呢？就是在第一次put元素的时候，可以通过源码看到，如果此时是空的，那么就初始化指定的或者默认的大小，如果此时放不下了，那么就会触发扩容；

  扩容和负载因此和容量有关，默认情况下负载因子是0.75，即当数组中已经占用的超过75%的时候，就会触发扩容；负载因子可以调整，但是不要设置过大，否则冲突会加剧，也不能设置太小，会造成频繁扩容，浪费资源和空间；