Javaソースの角度からHashMapとHashTableの違いを分析します。
16686 ワード
HashMapとHashTableはKey-Valueのキーを保存するために使われているので、常に両者の違いを比較してきました。以下はソースの角度からHashMapとHashTableの違いを分析します。
まず二つの違いを紹介して、ソースから分析します。
HahMapとHahTableの違いは主に以下の通りです。
1、継承の親が異なる
まず二つの違いを紹介して、ソースから分析します。
HahMapとHahTableの違いは主に以下の通りです。
1、継承の親が異なる
public class HashMap extends AbstractMap implements Cloneable, Serializable public class Hashtable extends Dictionary implements Map, Cloneable, Serializable
HashTableは いMapの で、JDK 1.0から れ めて、Dictionaryから して、その JDKはまだMapのこのインターフェースが れていますか？HashMapはAbstractMapという を していますが、AbstractMapという はMapインターフェースを しました。
2、HashTable ， ； HashMap ， ， Collections synchronizedXxx() 。
3、HashTable Key Value NULL ， HashMap Key
NULL, HashMap Map ，Map Key ， HashMap
Key NULL ， HashMap Value NULL
。
4、
Hashtable、HashMap Iterator。 ，Hashtable
Enumeration 。
HashMap 。
HashMap Field ：
/**
* Min capacity (other than zero) for a HashMap. Must be a power of two
* greater than 1 (and less than 1 << 30).
* HashMap
*/
private static final int MINIMUM_CAPACITY = 4;
/**
* Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
* HashMap
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* An empty table shared by all zero-capacity maps (typically from default
* constructor). It is never written to, and replaced on first put. Its size
* is set to half the minimum, so that the first resize will create a
* minimum-sized table.
*
* HashMapEntry ，HashMapEntry ,HashMapEntry MINIMUM_CAPACITY/2
*/
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
/**
* The default load factor. Note that this implementation ignores the
* load factor, but cannot do away with it entirely because it's
* mentioned in the API.
*
* Note that this constant has no impact on the behavior of the program,
* but it is emitted as part of the serialized form. The load factor of
* .75 is hardwired into the program, which uses cheap shifts in place of
* expensive division.
*
*/
static final float DEFAULT_LOAD_FACTOR = .75F;
/**
* The hash table. If this hash map contains a mapping for null, it is
* not represented this hash table.
* HashMap ， HashMapEntry
*/
transient HashMapEntry[] table;
/**
* The entry representing the null key, or null if there's no such mapping.
* HashMapEntry
*/
transient HashMapEntry entryForNullKey;
/**
* The number of mappings in this hash map.
* HashMap ( )
*/
transient int size;
/**
* Incremented by "structural modifications" to allow (best effort)
* detection of concurrent modification.
* ，HashMap
*/
transient int modCount;
/**
* The table is rehashed when its size exceeds this threshold.
* The value of this field is generally .75 * capacity, except when
* the capacity is zero, as described in the EMPTY_TABLE declaration
* above.
* ( )
*/
private transient int threshold;
// Views - lazily initialized
/** K Set */
private transient Set keySet;
/** K-Value Set ,Set Entry */
private transient Set> entrySet;
private transient Collection values;
HashMapはHashMap Entry でKey-Valueキーの を しています。HashMap EntryはHashMapの の な クラスで、java.util.Map.Entryインターフェースを しました。HashMapのプロパティFieldでは、Key-Valueキーペアを するためのHashMapEntry のデフォルトの と を します。 のHashMapEntry EMPTY_TABLEおよびHashMap tabは、HashMapEntryオブジェクトを するための である。デフォルトの DEFAULT_LOAD_FACTORは、それを0.75（3/4）と します。
HashMapの は に のいくつかあります。HashMap() Costructs a new empty HashMap instance.HashMap(int capacity) Costructs a new HashMap instance with the specified capacity.HashMap(int capacity, float loadFactor) Costructs a new HashMap instance with the specified capacity and load factor.HashMap(Map extendsK,? extends V> map) Costructs a new HashMap instance containing the mappings from the specified map.
たちはHashMap(int capacity)というコンストラクションのソースコードを に ました。 /**
* Constructs a new {@code HashMap} instance with the specified capacity.
*
* @param capacity
* the initial capacity of this hash map.
* @throws IllegalArgumentException
* when the capacity is less than zero.
* HashMap
*@param capacity：HashMap
*
*/
public HashMap(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity: " + capacity);
}
if (capacity == 0) {
@SuppressWarnings("unchecked")
HashMapEntry[] tab = (HashMapEntry[]) EMPTY_TABLE;
table = tab;
threshold = -1; // Forces first put() to replace EMPTY_TABLE
return;
}
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = Collections.roundUpToPowerOfTwo(capacity);
}
makeTable(capacity);
}
この は、 された capacityによって、HashMapEntry オブジェクトを します。capacityが0に しい は、 のHashMapEntry オブジェクトEMPTY_を します。TABLEはtabオブジェクトに を えます。capacityが0でない 、capacityが より さい はcapacityを に し、capacityが より きい はcapacityを に する。 に、makeTableを び して、tab の を する。 はmakeTableの な です。 /**
* Allocate a table of the given capacity and set the threshold accordingly.
* table ， ( )
* @param newCapacity must be a power of two
*
*/
private HashMapEntry[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry[] newTable
= (HashMapEntry[]) new HashMapEntry[newCapacity];
table = newTable;
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
return newTable;
}
makeTableでは、 された の きさで しいHashMapEnty newTableを し、そのnewTable をHashMapの File tableに することによって、HashMapでtable が のHash MapEntryを する であることが かります。 では、 threshholdを の3/4として し、テーブル に されたHashMapEntry の が threshholdより きい 、テーブル は されます。java.util.hashMap.put（K key、V value）のソースコードを ると、この が かります。 /**
* Maps the specified key to the specified value.
*
* @param key
* the key.
* @param value
* the value.
* @return the value of any previous mapping with the specified key or
* {@code null} if there was no such mapping.
*/
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = secondaryHash(key);
HashMapEntry[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
HashMap.put はHashMapにHashMap Entry を するために され、keyが の はput ValueForNullKeyメソッドを び して、nULLであるHashMapEntryオブジェクトにvalueを する。そして、 ってきたkeyがテーブル に に しているかどうかを し、 すれば しいvalue をkeyに き えて いvalue oldValueに し、oldValueを します。keyがtable に しない は、addNewEntry（K key，V value，int hash，int index）を び します。 は、Valueオブジェクトをテーブル に します。しかし、テーブル に する に、テーブル の sizeが threshldより きい は、double Capacityを び して、テーブル の を う。doubleCapacity のソースコードは の りです。 /**
* Doubles the capacity of the hash table. Existing entries are placed in
* the correct bucket on the enlarged table. If the current capacity is,
* MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
* will be new unless we were already at MAXIMUM_CAPACITY.
*
*/
private HashMapEntry[] doubleCapacity() {
/** table */
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
int newCapacity = oldCapacity * 2;
HashMapEntry[] newTable = makeTable(newCapacity);
if (size == 0) {
return newTable;
}
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry e = oldTable[j];
if (e == null) {
continue;
}
int highBit = e.hash & oldCapacity;
HashMapEntry broken = null;
newTable[j | highBit] = e;
for (HashMapEntry n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
return newTable;
}
にjava.util.hashMap.get（Object key）の のソースコードを てみます。 /**
* Returns the value of the mapping with the specified key.
*
* @param key
* the key.
* @return the value of the mapping with the specified key, or {@code null}
* if no mapping for the specified key is found.
*/
public V get(Object key) {
if (key == null) {
HashMapEntry e = entryForNullKey;
return e == null ? null : e.value;
}
// Doug Lea's supplemental secondaryHash function (inlined).
// Replace with Collections.secondaryHash when the VM is fast enough (http://b/8290590).
int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
hash ^= (hash >>> 7) ^ (hash >>> 4);
HashMapEntry[] tab = table;
for (HashMapEntry e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
HashMap.get では、hashMapがKeyを する で、カスタムクラスがKeyの となると、equals とhashCode を き えることが に され、equals とhashCode の は しなければならない。つまり、カスタムクラスを ってHashMapの のKeyオブジェクトとして、HashMapは2つのKeyが しいと する は、2つのKeyがequals（）の で してtrueに り、2つのKeyのhashCodeの も しくなければならない。
それと に、HashTableのソースコードを てみます。HashTableとHashMapは の の の の と じです。ここでは しく しないで、 に の の の のいくつかの いを ます。
java.util.hashtable.put（K key、V value）ソース： /**
* Associate the specified value with the specified key in this
* {@code Hashtable}. If the key already exists, the old value is replaced.
* The key and value cannot be null.
*
* @param key
* the key to add.
* @param value
* the value to add.
* @return the old value associated with the specified key, or {@code null}
* if the key did not exist.
* @see #elements
* @see #get
* @see #keys
* @see java.lang.Object#equals
*/
public synchronized V put(K key, V value) {
if (key == null) {
throw new NullPointerException("key == null");
} else if (value == null) {
throw new NullPointerException("value == null");
}
int hash = Collections.secondaryHash(key);
HashtableEntry[] tab = table;
int index = hash & (tab.length - 1);
HashtableEntry first = tab[index];
for (HashtableEntry e = first; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for key is present; create one
modCount++;
if (size++ > threshold) {
rehash(); // Does nothing!!
tab = doubleCapacity();
index = hash & (tab.length - 1);
first = tab[index];
}
tab[index] = new HashtableEntry(key, value, hash, first);
return null;
}
HashTable.put はHashMap.put と に じ を しています。 にHashTable.put はsynchronizedキーワードによって されています。したがって、HashTableはスレッド です。また、KeyがNULLであれば、HashTable.put では を しますので、HashTableではKeyはNULLではなく、 の からHashMap.put ではKeyはNULLであることが かります。
はjava.util.hashtable.getのソースコードを します。 たような も つけられます。だから、 に しません。 /**
* Returns the value associated with the specified key in this
* {@code Hashtable}.
*
* @param key
* the key of the value returned.
* @return the value associated with the specified key, or {@code null} if
* the specified key does not exist.
* @see #put
*/
public synchronized V get(Object key) {
int hash = Collections.secondaryHash(key);
HashtableEntry[] tab = table;
for (HashtableEntry e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
HashMapソース（JDK 1.7、コメントを む） HashTableソース（JDK 1.7、コメントを む）