Java中的哈希表
一、什么是哈希表？
在前面的文章中，我们已经讲解过了数组和链表的比较，参考《ArrayList和LinkedList——数组VS链表》，可以得出以下的结论：
- 数组更利于元素的查找；
- 链表更利于元素的插入和删除；
那么有没有一种数据结构可以同时具有数组和链表的优点呢？即能快速地查找又能高效地插入删除元素？很明显，本文的主角“哈希表”就能很好的满足这个要求。
那么哈希表是怎么做到两者的优点兼具的呢？这主要归功于它独特的数据结构。哈希表是由一块地址连续的数组空间构成的，其中每个数组都是一个链表，数组的作用在于快速寻址查找，链表的作用在于快速插入和删除元素，因此，哈希表可以被认为就是链表的数组，下图是一个哈希表的简单示意图：
哈希表结构示意图
按照上图的示例，我们就有一个问题，这些元素是怎么确定需要放置到哪个数组空间和其对应的链表上的呢？
一般而言，我们在存储元素的时候，会用到“散列方法”，它的作用就是尽量均衡地将元素分配到数组空间中，避免出现某个数组空间中的链表元素大大超过其它数组空间中链表元素个数的情况。
散列方法对比示意图
比较经典的散列函数有“除法散列法”、“平方散列法”、“斐波那契散列法”，这些散列方法在《数据结构》的教材中可以找到，但现在基本都不使用这些了，本文也不再重点讲述这些内容。但为了动态描述散列表是如何工作的，下面给出一个使用“除法散列法”的例子：
散列存储实例
除法散列法：index = value % arraySize
待插入数据：1,9,18,22,29
现在我们在内存中创建一个大小为5的数组空间，那么arraySize就为5。
- 插入元素1时，index=1%5=1，插入第一个数组空间；
- 插入元素9时，index=9%5=4，插入第四个数组空间；
- 插入元素18时，index=18%5=3,插入第三个数组空间；
- 插入元素22时，index=22%5=2，插入第二个数组空间；
- 插入元素29时，index=29%5=4，插入第四个数组空间，发现已经存在一个元素了，那么就在该元素后面增加一个链表节点进行存储；
当需要查找某个元素的时候，比如查找18，那么首先对其值进行散列，18%5=3，得到了数组空间地址为3，那么就去该地址对应的链表上逐个去寻找元素。
由此可以看出，当某个链表长度过长的话，查找效率就会急剧下降。因此，一个好的散列方法能确保各个元素均匀地分布到各个数组空间的地址上，避免某个链表过长，这对于哈希表的查找效率是非常重要的。
然而，即使我们拥有了一个好的哈希方法，倘若散列后还是会有很多元素对应同一个数组地址（哈希冲突），则还是会出现单个数组空间中链表元素过多过长的问题，这种情况下怎么解决查询效率慢的问题呢？
一种通用的做法是，将过长的链表转化为二叉查找树、平衡二叉树、红黑树，关于树的数据结构本文不再展开，只需要了解，它们是为了解决单条链表元素过多时查找效率慢的问题，详情可以参考《数据结构》。
二、关于HashMap
2.1 线程安全
首先最重要的一点是HashMap不是线程安全的，这是它区别于HashTable和ConcurrentHashMap的重要特性，但也因此，它的效率是最高的。
// TODO 待补充一个证明HashMap线程不安全的例子
2.2 空值存放
其次，在HashMap中，允许存放key和value为null的情况，只不过key为null的情况只允许存放一个，但是value为null的情况，则没有做限制。
public static void main(String[] args) {
Map<Object,Object> aMap = new HashMap<>(16);
aMap.put(null,"apple");
aMap.put(null,"banana");
aMap.put("apple",null);
aMap.put("banana",null);
aMap.put("orange",null);
// print banana
System.out.println(aMap.get(null));
// print null
System.out.println(aMap.get("apple"));
// print null
System.out.println(aMap.get("banana"));
// print null
System.out.println(aMap.get("orange"));
}
2.3 初始化及扩容机制
如果我们在声明一个HashMap的时候，没有指定它的大小，那么其默认的大小就是16，当数组空间占用数量达到capacity*loadFactor -1的时候，就会扩容为原来的2倍。
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
如果我们一开始指定了HashMap的大小，那么其就会初始化2的幂次方容量的大小。同样的，当数组空间占用数量达到capacity*loadFactor -1的时候，也会扩容为原来的2倍。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2.4 数据结构
在JDK1.8之前，HashMap就是简单的数组+链表的数据结构，但是JDK1.8中，已经优化成了数组+链表/红黑树的数据结构。即当链表中的元素大于阈值8的时候，链表会转换为一颗红黑树，如此可以加快在链表上寻找元素的效率。
三、关于HashTable
HashTable是线程安全的，这个在看它的源码就能发现，除了构造函数外，其它的方法都是加上了synchronized关键字的。
public synchronized int size() {
return count;
}
public synchronized boolean isEmpty() {
return count == 0;
}
HashTable因为是线程安全的，因此效率当然会比HashMap要低，同时，它不支持存放键为null的情况，会抛出异常。
HashTable的默认不指定初始大小的情况下初始容量为11，之后每次扩容会变为2n+1。
HashTable在底层的数据结构上还是维持原来的数组+链表形式。
在实际的多线程使用场景下，通常不推荐使用HashTable，而是使用ConcurrentHashMap，因为后者的效率更高，详细的原理分析可以在下面ConcurrentHashMap处看到。
四、关于HashSet
HashSet的内部就是调用的HashMap，它和HashMap的区别是，HashSet存放的是单个值，而且不能重复。
有必要说一说HashSet是怎么判断元素重复的：
- 获取将要添加元素的hashcode值；
- 如果hashcode和已经存储元素的任何一个都不同，则证明不重复，可以添加；
- 如果hashcode和某个已经存在的元素的hashcode相同，则比较它们的值是否相等；
- 如果值相等，则证明重复，否则就是不重复，可以添加。
所以，如果你需要把元素添加到Hash类型的数据结构中时，一定要记得重写equals方法和hashcode方法。参考文章《Java中equals和hashcode的使用》
五、关于ConcurrentHashMap
我们已经知道了ConcurrentHashMap是线程安全的，提倡在多线程的场景下使用它，那么它是如何实现线程安全的呢？相比较于同样是线程安全的HashTable，它们之间的不同体现在哪里呢？
在JDK1.7的时候，ConcurrentHashMap采用的是分段锁和数组+链表形式的数据结构，和HashMap的数据结构比较起来，多了分段锁的机制，也正是这个机制保证了它的线程安全。
ConcurrentHashMap分段锁示意图
如上图所示，每个Segment包含了若干个数组空间，只有获取到这个Segment的锁，才能对其中数组空间及其链表进行操作。
而HashTable的线程安全是借助synchronized关键字实现的，在一个线程没有调用完方法之前，其它线程是不能使用的，只能等待，导致整个数组空间都不可用。而ConcurrentHashMap的分段锁机制，只要多个线程想要操作的元素位于不同的Segment内，那么就互不影响，不存在锁竞争的情况，因此效率自然要高。
在JDK1.8中，ConcurrentHashMap更进一步，把分段锁细化到了每个数组空间的链表头节点上，因此，只要多个线程操作的元素位于不同的数组空间链表上，就不会存在竞争锁的情况，效率进一步得到了提升。
ConcurrentHashMap链表头节点所示意图
因此，我们在多线程场景下，总是应该使用ConcurrentHashMap，而不是HashTable。
