HashMap、HashTable和ConcurrentHashMap的区别

HashMap、HashTable

简单点来说，HashTable是线程安全的HashMap，都实现了Map接口，Map接口对键值对进行映射。但还是有些不同，这里从三点来说：线程安全性，同步(synchronization)，以及速度。

• 我们先来看看HashMap的底层:

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

不难看出， HashMap实现了 Cloneable, Serializable两大接口；

底层描述：HashMap底层是数组加链表的形式，基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

 

以下为hashmap的方法，有两个很明显的特点：

1. 没有加synchronized；因此线程不安全
2. 它的键值可以为空；
3. Map中不允许重复的键；

public int size()   //键值对的数量
public boolean isEmpty()  //判断是否为空
public V get(Object key)  //常用的get方法，通过键获取值
private V getForNullKey(Object key)  //通过键查看哪个值为空 
private V putForNullKey(V value) //通过值查看哪个键为空 
public boolean containsKey(Object key) //包含某个键
final Entry<K,V> getEntry(Object key) //hashmap中通过key拿到键值对
public V put(K key, V value)  //常用的put方法，将键值对放入map中
public V remove(Object key)  //移除掉当前的键值对
public void clear()  //清空map
public boolean equals(Object obj)

•  HashTable的底层

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

 HashTable也实现了 Cloneable, Serializable两大接口，再次证明HashTable和HashMap都实现的Map接口；

底层描述：

1. 和HashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对。
2. 从底层代码看出，Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
3. Hashtable 它是线程安全的。它的key、value都不可以为null。

 

下面我们来看看HashTable中的方法：

1. 加synchronized；因此线程安全
2. 它的键值不可以为空；

3. HashTable和HashMap用法相似

public synchronized int size()；

public synchronized boolean isEmpty()

public synchronized Enumeration<K> keys()

public synchronized boolean contains(Object value)

public boolean containsValue(Object value) //是否包含值

public synchronized boolean containsKey(Object key) //是否包含key

public synchronized V get(Object key)   //通过key拿到value

public synchronized V remove(Object key)  //通过key移除掉当前键值对

public synchronized void clear()  //清空map

很明显都加了synchronized来保证线程安全

在这里对synchronized做一些拓展，sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁，其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。
 

总结：

• 你需要完全的线程安全的时候使用HashTable，否则HashMap

问：我们能否让HashMap同步？

• Map m = Collections.synchronizeMap(hashMap);

 

ConcurrentHashMap

当我们需要线程安全时又想要很高的性能，此时就需要使用ConcurrentHashMap了，那么为什么不适用稳定安全的hashtable呢？

我们先对ConcurrentHashMap做一些介绍：

• 底层采用分段的数组+链表实现，线程安全。
• 通过把整个map分为N个Segment，可以提供相同的线程安全效率提升N倍，默认16倍。
• 读操作不加锁，修改操作加分段锁，允许多个修改操作并行发生。
• 扩容：段内扩容（段内元素超过该段对应的Entry数组的0.75，触发扩容，而不是整段扩容），插入前检测是否需要扩容，避免无效扩容。

现在明白了，它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，而ConcurrentHashMap引入了分段锁，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

这里我们对分段锁进行介绍：

        首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

面试中这些是常用的问题，在这里我例举几个：

问：为什么String作为键？

因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。

问：hashmap如何处理碰撞的？

• 由于hashmap在存值的时候并不是直接使用的key的hashcode，而是通过哈希算法计算出了一个新的hash值，这个计算出的hash值可以明显的减少碰撞。
• 扩容，扩容其实很好理解，就是将原来桶的容量扩为原来的两倍。这样争取散列的均匀，比如：原来桶的长度为16,hash值为1和17的entry将会都在桶的0号位上，这样就出现了碰撞，而当桶扩容为原来的2倍时，hash值为1和17的entry分别在1和17号位上，岔开了碰撞。