HashMap和Hashtable的详细区别

hashmap和hashtable的详细区别

一、简述：

1.安全性

hashtable是线程安全，hashmap是非线程安全。
hashmap的性能会高于hashtable，我们平时使用时若无特殊需求建议使用hashmap，在多线程环境下若使用hashmap需要使用collections.synchronizedmap()方法来获取一个线程安全的集合（collections.synchronizedmap()实现原理是collections定义了一个synchronizedmap的内部类，这个类实现了map接口，在调用方法时使用synchronized来保证线程同步

2.是否可以使用null作为key

hashmap可以使用null作为key，不过建议还是尽量避免这样使用。hashmap以null作为key时，总是存储在table数组的第一个节点上。而hashtable则不允许null作为key

3.继承了什么，实现了什么

hashmap继承了abstractmap，hashtable继承dictionary抽象类，两者均实现map接口

4.默认容量及如何扩容

hashmap的初始容量为16，hashtable初始容量为11，两者的填充因子默认都是0.75。
hashmap扩容时是当前容量翻倍即:capacity * 2，hashtable扩容时是容量翻倍+1即:capacity * (2+1)

6.底层实现

hashmap和hashtable的底层实现都是数组+链表结构实现

7.计算hash的方法不同

hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模
hashmap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取模

二、详述：

参考文章：

hashmap和hashtable有什么不同？在面试和被面试的过程中，我问过也被问过这个问题，也见过了不少回答，今天决定写一写自己心目中的理想答案。

代码版本

jdk每一版本都在改进。本文讨论的hashmap和hashtable基于jdk 1.7.0_67。源码见这里

1. 时间

hashtable产生于jdk 1.1，而hashmap产生于jdk 1.2。从时间的维度上来看，hashmap要比hashtable出现得晚一些。

2. 作者

以下是hashtable的作者：

以下代码及注释来自java.util.hashtable

* @author  arthur van hoff
* @author  josh bloch
* @author  neal gafter

以下是hashmap的作者：

以下代码及注释来自java.util.hashmap

 * @author  doug lea
 * @author  josh bloch
 * @author  arthur van hoff
 * @author  neal gafter

可以看到hashmap的作者多了大神doug lea。不了解doug lea的，可以看这里。

3. 对外的接口（api）

hashmap和hashtable都是基于哈希表来实现键值映射的工具类。讨论他们的不同，我们首先来看一下他们暴露在外的api有什么不同。

3.1 public method

下面两张图，我画出了hashmap和hashtable的类继承体系，并列出了这两个类的可供外部调用的公开方法。

---

从图中可以看出，两个类的继承体系有些不同。虽然都实现了map、cloneable、serializable三个接口。但是hashmap继承自抽象类abstractmap，而hashtable继承自抽象类dictionary。其中dictionary类是一个已经被废弃的类，这一点我们可以从它代码的注释中看到：

以下代码及注释来自java.util.dictionary

 * <strong>note: this class is obsolete.  new implementations should
 * implement the map interface, rather than extending this class.</strong>

同时我们看到hashtable比hashmap多了两个公开方法。一个是elements，这来自于抽象类dictionary，鉴于该类已经废弃，所以这个方法也就没什么用处了。另一个多出来的方法是contains，这个多出来的方法也没什么用，因为它跟containsvalue方法功能是一样的。代码为证：

以下代码及注释来自java.util.hashtable

 public synchronized boolean contains(object value) {
     if (value == null) {
         throw new nullpointerexception();
     }

     entry tab[] = table;
     for (int i = tab.length ; i-- > 0 ;) {
         for (entry<k,v> e = tab[i] ; e != null ; e = e.next) {
             if (e.value.equals(value)) {
                 return true;
             }
         }
     }
     return false;
 }

 public boolean containsvalue(object value) {
     return contains(value);
 }

所以从公开的方法上来看，这两个类提供的，是一样的功能。都提供键值映射的服务，可以增、删、查、改键值对，可以对建、值、键值对提供遍历视图。支持浅拷贝，支持序列化。

3.2 null key & null value

hashmap是支持null键和null值的，而hashtable在遇到null时，会抛出nullpointerexception异常。这并不是因为hashtable有什么特殊的实现层面的原因导致不能支持null键和null值，这仅仅是因为hashmap在实现时对null做了特殊处理，将null的hashcode值定为了0，从而将其存放在哈希表的第0个bucket中。我们一put方法为例，看一看代码的细节：

以下代码及注释来自java.util.hashtable

public synchronized v put(k key, v value) {

    // 如果value为null，抛出nullpointerexception
    if (value == null) {
        throw new nullpointerexception();
    }

    // 如果key为null，在调用key.hashcode()时抛出nullpointerexception

    // ...
}


以下代码及注释来自java.util.hasmap

public v put(k key, v value) {
    if (table == empty_table) {
        inflatetable(threshold);
    }
    // 当key为null时，调用putfornullkey特殊处理
    if (key == null)
        return putfornullkey(value);
    // ...
}

private v putfornullkey(v value) {
    // key为null时，放到table[0]也就是第0个bucket中
    for (entry<k,v> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            v oldvalue = e.value;
            e.value = value;
            e.recordaccess(this);
            return oldvalue;
        }
    }
    modcount++;
    addentry(0, null, value, 0);
    return null;
}

4. 实现原理

本节讨论hashmap和hashtable在数据结构和算法层面，有什么不同。

4.1 数据结构

hashmap和hashtable都使用哈希表来存储键值对。在数据结构上是基本相同的，都创建了一个继承自map.entry的私有的内部类entry，每一个entry对象表示存储在哈希表中的一个键值对。

entry对象唯一表示一个键值对，有四个属性：

-k key 键对象
-v value 值对象
-int hash 键对象的hash值
-entry<k, v> entry 指向链表中下一个entry对象，可为null，表示当前entry对象在链表尾部

可以说，有多少个键值对，就有多少个entry对象，那么在hashmap和hashtable中是怎么存储这些entry对象，以方便我们快速查找和修改的呢？请看下图。

上图画出的是一个桶数量为8，存有5个键值对的hashmap/hashtable的内存布局情况。可以看到hashmap/hashtable内部创建有一个entry类型的引用数组，用来表示哈希表，数组的长度，即是哈希桶的数量。而数组的每一个元素都是一个entry引用，从entry对象的属性里，也可以看出其是链表的节点，每一个entry对象内部又含有另一个entry对象的引用。

这样就可以得出结论，hashmap/hashtable内部用entry数组实现哈希表，而对于映射到同一个哈希桶（数组的同一个位置）的键值对，使用entry链表来存储(解决hash冲突)。

以下代码及注释来自java.util.hashtable

/**
 * the hash table data.
 */
private transient entry<k,v>[] table;


以下代码及注释来自java.util.hashmap

/**
 * the table, resized as necessary. length must always be a power of two.
 */
transient entry<k,v>[] table = (entry<k,v>[]) empty_table;

从代码可以看到，对于哈希桶的内部表示，两个类的实现是一致的。

4.2 算法

上一小节已经说了用来表示哈希表的内部数据结构。hashmap/hashtable还需要有算法来将给定的键key，映射到确定的hash桶（数组位置）。需要有算法在哈希桶内的键值对多到一定程度时，扩充哈希表的大小（数组的大小）。本小节比较这两个类在算法层面有哪些不同。

初始容量大小和每次扩充容量大小的不同。先看代码：

以下代码及注释来自java.util.hashtable

// 哈希表默认初始大小为11
public hashtable() {
    this(11, 0.75f);
}

protected void rehash() {
    int oldcapacity = table.length;
    entry<k,v>[] oldmap = table;

    // 每次扩容为原来的2n+1
    int newcapacity = (oldcapacity << 1) + 1;
    // ...
}


以下代码及注释来自java.util.hashmap

// 哈希表默认初始大小为2^4=16
static final int default_initial_capacity = 1 << 4; // aka 16

void addentry(int hash, k key, v value, int bucketindex) {
    // 每次扩充为原来的2n 
    if ((size >= threshold) && (null != table[bucketindex])) {
       resize(2 * table.length);
}

可以看到hashtable默认的初始大小为11，之后每次扩充为原来的2n+1。hashmap默认的初始化大小为16，之后每次扩充为原来的2倍。还有我没列出代码的一点，就是如果在创建时给定了初始化大小，那么hashtable会直接使用你给定的大小，而hashmap会将其扩充为2的幂次方大小。

也就是说hashtable会尽量使用素数、奇数。而hashmap则总是使用2的幂作为哈希表的大小。我们知道当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀（具体证明，见这篇），所以单从这一点上看，hashtable的哈希表大小选择，似乎更高明些。但另一方面我们又知道，在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。所以从hash计算的效率上，又是hashmap更胜一筹。

所以，事实就是hashmap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以hashmap为解决这问题，又对hash算法做了一些改动。具体我们来看看，在获取了key对象的hashcode之后，hashtable和hashmap分别是怎样将他们hash到确定的哈希桶（entry数组位置）中的。

以下代码及注释来自java.util.hashtable

// hash 不能超过integer.max_value 所以要取其最小的31个bit
int hash = hash(key);
int index = (hash & 0x7fffffff) % tab.length;

// 直接计算key.hashcode()
private int hash(object k) {
    // hashseed will be zero if alternative hashing is disabled.
    return hashseed ^ k.hashcode();
}


以下代码及注释来自java.util.hashmap
int hash = hash(key);
int i = indexfor(hash, table.length);

// 在计算了key.hashcode()之后，做了一些位运算来减少哈希冲突
final int hash(object k) {
    int h = hashseed;
    if (0 != h && k instanceof string) {
        return sun.misc.hashing.stringhash32((string) k);
    }

    h ^= k.hashcode();

    // this function ensures that hashcodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// 取模不再需要做除法
static int indexfor(int h, int length) {
    // assert integer.bitcount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

正如我们所言，hashmap由于使用了2的幂次方，所以在取模运算时不需要做除法，只需要位的与运算就可以了。但是由于引入的hash冲突加剧问题，hashmap在调用了对象的hashcode方法之后，又做了一些位运算在打散数据。关于这些位计算为什么可以打散数据的问题，本文不再展开了。感兴趣的可以看。

如果你有细心读代码，还可以发现一点，就是hashmap和hashtable在计算hash时都用到了一个叫hashseed的变量。这是因为映射到同一个hash桶内的entry对象，是以链表的形式存在的，而链表的查询效率比较低，所以hashmap/hashtable的效率对哈希冲突非常敏感，所以可以额外开启一个可选hash（hashseed），从而减少哈希冲突。因为这是两个类相同的一点，所以本文不再展开了，感兴趣的看。事实上，这个优化在jdk 1.8中已经去掉了，因为jdk 1.8中，映射到同一个哈希桶（数组位置）的entry对象，使用了红黑树来存储，从而大大加速了其查找效率。

5. 线程安全

我们说hashtable是同步的，hashmap不是，也就是说hashtable在多线程使用的情况下，不需要做额外的同步，而hashmap则不行。那么hashtable是怎么做到的呢？

以下代码及注释来自java.util.hashtable

public synchronized v get(object key) {
    entry tab[] = table;
    int hash = hash(key);
    int index = (hash & 0x7fffffff) % tab.length;
    for (entry<k,v> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
        }
    }
    return null;
}

public set<k> keyset() {
    if (keyset == null)
        keyset = collections.synchronizedset(new keyset(), this);
    return keyset;
}

可以看到，也比较简单，就是公开的方法比如get都使用了synchronized描述符。而遍历视图比如keyset都使用了collections.synchronizedxxx进行了同步包装。

6. 代码风格

从我的品位来看，hashmap的代码要比hashtable整洁很多。下面这段hashtable的代码，我就觉着有点混乱，不太能接受这种代码复用的方式。

以下代码及注释来自java.util.hashtable

/**
 * a hashtable enumerator class.  this class implements both the
 * enumeration and iterator interfaces, but individual instances
 * can be created with the iterator methods disabled.  this is necessary
 * to avoid unintentionally increasing the capabilities granted a user
 * by passing an enumeration.
 */
private class enumerator<t> implements enumeration<t>, iterator<t> {
    entry[] table = hashtable.this.table;
    int index = table.length;
    entry<k,v> entry = null;
    entry<k,v> lastreturned = null;
    int type;

    /**
     * indicates whether this enumerator is serving as an iterator
     * or an enumeration.  (true -> iterator).
     */
    boolean iterator;

    /**
     * the modcount value that the iterator believes that the backing
     * hashtable should have.  if this expectation is violated, the iterator
     * has detected concurrent modification.
     */
    protected int expectedmodcount = modcount;

    enumerator(int type, boolean iterator) {
        this.type = type;
        this.iterator = iterator;
    }
    
    //...

}

7. hashtable已经被淘汰了，不要在代码中再使用它。

以下描述来自于hashtable的类注释：

if a thread-safe implementation is not needed, it is recommended to use hashmap in place of hashtable. if a thread-safe highly-concurrent implementation is desired, then it is recommended to use java.util.concurrent.concurrenthashmap in place of hashtable.

简单来说就是，如果你不需要线程安全，那么使用hashmap，如果需要线程安全，那么使用concurrenthashmap。hashtable已经被淘汰了，不要在新的代码中再使用它。

8. 持续优化

虽然hashmap和hashtable的公开接口应该不会改变，或者说改变不频繁。但每一版本的jdk，都会对hashmap和hashtable的内部实现做优化，比如上文曾提到的jdk 1.8的红黑树优化。所以，尽可能的使用新版本的jdk吧，除了那些炫酷的新功能，普通的api也会有性能上有提升。

为什么hashtable已经淘汰了，还要优化它？因为有老的代码还在使用它，所以优化了它之后，这些老的代码也能获得性能提升。

reference

• https://github.com/zhaox/jdk-1.7-annotated/blob/master/src/java/util/hashmap.java
• https://github.com/zhaox/jdk-1.7-annotated/blob/master/src/java/util/hashtable.java