Java-基于Hash实现的数据结构

       HashTable、HashMap、HashSet、ConcurrentHashMap等都是Java中基于Hash实现的几种常见的数据结构。

• HashTable

  关于HashTable的关联关系如下：
  

  

         可以看到HashTable继承自Dictionary类，同时实现了Map、Cloneable（可复制）、Serializable（可序列化）这三个接口。Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。

        Hashtable的存储形式为键值对，底层的存储结构为数组加链表的形式，直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后除以数组长度根据余数定位数组索引（除法的效率比较低，但是当数组的长度为素数时，会有效减少Hash冲突）来获得最终的位置。Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。


        HashTable是线程安全的，源码当中每个方法均有Synchronized修饰，但是另一方面也使得效率更低。HashTable中键和值均不能为null。

• HashMap

  关于HashMap的关联关系如下：
  

  

         可以看到HashMap继承自AbstractMap类，同时实现了Map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

        HashMap的存储形式为键值对，，底层的存储结构为数组加链表的形式，HashMap为了提高计算效率，将容量小固定为了2的次幂，根据与（位运算符号“&”）上数组长度减1的值来获取数组索引，位运算比除法的效率要高很多，但是hash冲突却也增加了。HashMap默认的初始化大小为16，负载因子默认为0.75，之后每次数据量大于容量乘以负载因子时扩充，容量变为原来的2倍。

        Hashap是非线程安全的，键可以为null，但是最多只有一个，值可以为null。

        JDK1.7中，HashMap存在两个比较明显的问题：当Hash冲突严重时，在对应数组索引上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；因为扩容时采用头插法，在多线程高并发下扩容时，因为要对链表的节点进行读写操作，会产生死锁的问题，严重影响程序安全。

        所以在JDK1.8的时候，进行相关优化。针对第一点，加入了红黑树进行优化，当链表节点数大于8时，链表转化为红黑树结构，当红黑树节点数小于6时，转变为链表结构。针对第二点，不采用头插法转而采用双链表的形式去拆分原有的链表放到扩容后的HashMap中。同时在JDK1.7中的先检查扩容修改为先插入再检测扩容。

备注：至于为什么是负载因子是0.75、8个节点由链表转为红黑树、6个节点由红黑树转为链表，其实基本上是出于对每个链表的元素个数服从泊松分布，基于时间和空间的平衡，相当于一个经验值。

• HashSet

  关于HashSet的关联关系如下：
  

  

         可以看到HashSet继承自AbstractSet、AbstractCollection类，同时实现了Map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

        HashSet是基于HashMap实现的，内部有一个为HashMap类型的属性，相当于对HashMap做了一层封装，HashSet中的元素都以键的形式存储在HashMap中，值都为空对象。

        源码解析：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    ...
    private transient HashMap<E,Object> map;
    // 假值，每次加入新的数据，用于构造map中存储的键值对的值
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
}

• LinkedHashMap

  关于LinkedHashMap的关联关系如下：
  

  

         可以看到LinkedHashMap继承自Hashmap、AbstractMap类，同时实现了Map这个接口。

          LinkedHashMap在HashMap的基础上加入了双向链表的实现，每个节点均多增加了指向前一个加入的节点的指针（before）和指向后一个节点的指针（after）。

• ConcurrentHashMap

  关于ConcurrentHashMap的关联关系如下：

  

          可以看到HashMap继承自AbstractMap类，同时实现了ConcurrentMap、Serializable（可序列化）这两个接口。

          ConcurrentHashMap的存储形式为键值对，可视为线程安全的一种HashMap，在JDK1.7中是一种基于分段锁的实现，在JDK1.8中修改为基于volatile+CAS的实现，相当于对每个数组元素加锁。

• TreeMap

        关于ConcurrentHashMap的关联关系如下:

        简单提一下，TreeMap的存储形式为键值对，是基于红黑树实现的一种有序的数据结构，默认按字典序排序。