HashMap和HashTable到底哪不同？

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

* @author  Arthur van Hoff
* @author  Josh Bloch
* @author  Neal Gafter

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

* @author  Doug Lea
* @author  Josh Bloch
* @author  Arthur van Hoff
* @author  Neal Gafter

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

* <strong>NOTE: This class is obsolete.  New implementations should
* implement the Map interface, rather than extending this class.</strong>

以下代码及注释来自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);
}

以下代码及注释来自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;
}

以下代码及注释来自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;

以下代码及注释来自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);
}

以下代码及注释来自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);
}

以下代码及注释来自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;
}

以下代码及注释来自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;
   }
   
   //...

}