HashMap与HashTable的对比分析

前言

    前一段时间分析java collection中间一些数据结构代码的时候，单独把HashMap的实现做了一个分析（见链接）。以前看到很多人讨论问题的时候，会把HashMap和HashTable放在一起对比和分析。最开始的时候觉得他们两者的差别很小，网上也有很多浅显的解答。后来结合一些细节分析的时候，发现他们也存在许多细节上的差异，有的也许是针对不同应用的考量，有的也许是由于历史原因。这里想结合源代码的实现进行讨论。

元素结构

    如果说比较HashMap和HashTable的内部元素结构的话，我们会发现他们内部的实现基本上是一样的。它是由一个Entry<K, V>组成的数组。而Entry的声明如下：

 

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
//...

    这里是Entry声明的部分典型代码。可见他们还是采用类似链表数组结构，如下图：

 

    在看了前面的基本结构之后，我们再来看看他们的长度调整方式和映射的比较。

表的增长和映射

HashMap部分

    在HashMap里，我们所有元素的映射都是通过先计算元素的hashcode然后映射到数组中。不过它的具体情况如下：

HashMap默认长度为16：

 

static final int DEFAULT_INITIAL_CAPACITY = 16;

    它每次增长调整的时候都会变成原来的两倍, 在默认构造函数的时候，它的调整方式如下：

 

 

public HashMap(int initialCapacity, float loadFactor) {
// Ignored...
   // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];

// ignored...

}

    在我们添加Entry的时候，它的长度调整细节如下：

 

 

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

    这里调用了resize方法，而很明显传入的参数正好是原有table长度的两倍。resize方法主要做的事情就是新建一个原有长度两倍的数组，然后将原来table里所有的元素按照hash的映射方式重新映射到新的table中。前面两部分代码的标红部分正好保证了HashMap里所有元素的长度必然为2的指数。在前面分析HashMap的文章里我们已经讨论过，HashMap里元素的映射方式是先计算元素的hash值。

 

 

final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        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);
    }

    在计算出来hash值之后，再通过IndexFor方法将hash值映射到数组的索引上：

 

 

static int indexFor(int h, int length) {
        return h & (length-1);
    }

    这种与操作的好处在于实现了一个求模运算的效果，保证索引是在0-2的k次方之间。   

 

HashTable部分

    HashTable部分的实现有一点不同，首先它默认构造函数设置的table长度是11,见如下代码：

public Hashtable() {
        this(11, 0.75f);
    }

    在我们添加元素的时候，如果HashTable要调整长度，它是通过调用rehash方法，这方法的思路也和前面差不多，只不过它是通过将新数组长度设置为原有数组长度 ×2 + 1。

protected void rehash() {
        int oldCapacity = table.length;
        Entry<K,V>[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<K,V>[] newMap = new Entry[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        boolean currentAltHashing = useAltHashing;
        useAltHashing = sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = currentAltHashing ^ useAltHashing;

        table = newMap;

//...
    }

   这里的代码看似复杂，其实也就是先将数组长度增加，然后再和HashMap差不多，将所有元素重新映射到新数组里头。为什么不是直接将元素从原来数组按照原来的索引直接拷到新数组呢？因为这里数组的长度变化之后计算hash的方式和映射到数组中间索引的过程和数组长度有关系。

这里计算索引的过程则如一下语句：

int index = (e.hash & 0x7FFFFFFF) % newCapacity;

   我们再看看HashTable里计算hash值的方法，它的过程基本上是一样的。

访问方法

    我们再来看看他们之间访问方法的差别。

对null值参数的差别

    HashMap里是接受null类型的值作为key或者value的，我们可以看看典型的put方法：

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        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;
    }

     这里对访问的key值是null的情况做了一个单独的判断，如果key为null，put方法则直接遍历数组发现第一个key为null的元素并更新value，或者在数组的索引0下标创建一个新元素。

而对于HashTable的实现，如果我们要往里面添加null元素则会抛出异常：

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        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)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = hash(key);
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        return null;
    }

 

方法的线程安全

    看到前面贴出来的一部分实例代码，我们会看到HashTable里的方法带了synchronized的修饰。而HashMap里却没有。没错，对于HashTable来说，它是线程安全的。而对于HashMap来说却不是。不过如果在多线程的情况下，我们需要考虑性能或者数据访问一致性的话，HashMap就不是一个合理的选择，我们更应该考虑一下ConcurrentHashMap。

元素的迭代访问

    这一部分算是一个比较细小的差别，我们在需要采用迭代器访问HashTable的时候，它有几个原有的访问方法，分别是：

// return all keys
public synchronized Enumeration<K> keys();

// return all values
public synchronized Enumeration<V> elements()

    而如果我们在HashMap里要访问key或者KeyValue集合的话，则会采用如下的几个方法：keySet(), entrySet()。他们内部的实现做了几层封装，主要的迭代器实现是HashIterator，针对具体key，value有对应继承的ValueIterator, KeyIterator：

Iterator<K> newKeyIterator()   {
        return new KeyIterator();
    }
    Iterator<V> newValueIterator()   {
        return new ValueIterator();
    }
    Iterator<Map.Entry<K,V>> newEntryIterator()   {
        return new EntryIterator();
    }

private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }

    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }

    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }

    这里HashMap里面的迭代器是标准的Iterator接口实现，而HashTable里的则不一样，它采用的是Enumerator，这个类实现了Enumeration和Iterator两个接口，这部分的关键定义如下：

private class Enumerator<T> implements Enumeration<T>, Iterator<T> 

    看起来有点奇怪，为什么这部分要分别定义呢？因为原有的Enumeration接口是比较老的版本里的定义，它和Iterator接口的定义不一样。为了保证后面版本的jdk里也可以采用标准迭代器的方式来访问HashTable里的元素同时也为了和原来使用它的老代码兼容，这里就同时实现了两个接口。而他们两个接口里定义的东西基本上是一样的，除了Iterator接口里还定义了一个remove()方法。

 

总结

    前面诸多的讨论，主要是针对HashTable和HashMap两者在结构和实现细节方面做一些分析。总的来说，他们两者的差别主要集中在元素的映射方式不一样，而且结构调整的过程也有差别。另外，迭代访问其中集合元素以及线程安全都是他们的差异。从很多人为了面试背题目的角度来说，说出他们对null参数支持的差别似乎就够了。但是如果深挖的话，差别还是很多的。

 

参考材料

http://openjdk.java.net/

http://oznyang.iteye.com/blog/30690