In diesem Artikel erfahren Sie, was der Unterschied zwischen HashMap und HashTable in Java ist. Ein einfacher Vergleich von HashMap und HashTable. Es hat einen gewissen Referenzwert. Freunde in Not können sich darauf beziehen. Ich hoffe, es wird Ihnen hilfreich sein.
1. Schauen wir uns zunächst die Vererbungsstruktur an:
HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
Nach dem Login kopieren
Hashtable
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable
Nach dem Login kopieren
1 Aus dem Namen geht hervor, dass HashMap den Kamel-Kasten-Benennungsregeln entspricht. Aufgrund der Vererbungsstruktur erbt HashMap von AbstractMap und Hashtable erbt von Dictionnary. Dictionary ist eine aufgegebene Klasse und alle Hashtables werden im Allgemeinen nicht empfohlen. Der Synchronisationscontainer ConcurrentHashMap kann in einer Multithread-Umgebung verwendet werden.
2. Es kann über die Attribute der Klasse in jdk1.8 ermittelt werden, wenn die Anzahl der in einer Kette in der HashMap gespeicherten Knoten größer oder gleich 8 ist und die Länge der verknüpften Liste Ist das Array größer als 64, wird es in einen rot-schwarzen Baum konvertiert, während Hashtable nicht in einen rot-schwarzen Baum konvertiert wird.
3. Put() von Hashtable und put() von HashMap
Put-Operation von Hashtable:
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 = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}Nach dem Login kopieren
Die Methode in Hashtable fügt das synchronisierte Schlüsselwort hinzu, es handelt sich also um eine synchronisierte Methode.
Durch if (value == null) throw new NullPointerException();} können wir sehen, dass es nicht zulässt, dass der Wert von value leer ist, und wenn der Schlüssel null ist, wird key.hashCode() aufgerufen. ; wird ausgelöst Der Nullzeiger ist abnormal, daher dürfen der Schlüssel und der Wert im in der Hashtable gespeicherten Eintrag nicht leer sein. Darüber hinaus erhält Hashtable den Index der verknüpften Liste durch die %-Operation.
Wenn Sie sich HashMap
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}Nach dem Login kopieren
unten ansehen, können Sie sehen, dass der Schlüssel in HashMap eine Null haben kann, sein Hash-Wert 0 ist und die Methode von HashMap erhalten werden kann Der Index des verknüpften Listenarrays ist derselbe wie bei Hashtable. Anders als bei der Berechnung wird (n-1)&hash verwendet, da die Länge der verknüpften Array-Liste von HashMap 2 hoch n beträgt.
Zusammenfassung: Der Schlüssel in HashMap kann eine Null haben, der Wert kann mehrere Nullen haben und der Schlüssel und der Wert in Hashtable dürfen nicht leer sein. Die Methoden zum Positionieren der Kette sind unterschiedlich. HashMap erhält den Index durch die &-Operation, während Hashtable den Index durch % erhält und die &-Operation schneller ist.
4. HashMap und Hashtable haben unterschiedliche Erweiterungsmethoden.
Hashtable-Erweiterung:
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
//MAX_ARRAY_SIZE = int的最大值-8
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
//从链表数组尾到头遍历
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
//从新定位链位置
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}Nach dem Login kopieren
Durch den Quellcode haben wir festgestellt, dass die maximale Länge des Hashtable-verknüpften Listenarrays dem Maximalwert des int-Typs -8 entspricht. Die Erweiterung der Hashtable wird Verdoppeln Sie die ursprüngliche Länge plus 1 und nach der Erweiterung muss die verknüpfte Liste neu positioniert werden. Darüber hinaus wird die Reihenfolge der Array-verknüpften Liste nach der Erweiterung zur umgekehrten Reihenfolge der ursprünglichen Reihenfolge.
HashMap-Erweiterung:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//如果远链表数组长度大于零
if (oldCap > 0) {
//如果原长度大于或等于MAXIMUM_CAPACITY(2^30)，则将threshold(闸值)设为Integer.MAX_VALUE大约为MAXIMUM_CAPACITY(2^30)的二倍
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//让新的容量变为旧的二倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的闸值也变为原来的二倍
newThr = oldThr << 1; // double threshold
}
//老的链表数组长度小于等于0，老的闸值大于零，这种情况是初始化时传入一个map导致的构造器为public HashMap(Map<? extends K, ? extends V> m)
else if (oldThr > 0) // initial capacity was placed in threshold
//让新的容量等于旧的闸值
newCap = oldThr;
//下面的else是默认的构造器，即public HashMap()
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//新的闸值为零时（也就是(newCap = oldCap << 1) >= MAXIMUM_CAPACITY的情况），这时需要赋予newThr正确的值。
if (newThr == 0) {
float ft = (float)newCap * loadFactor; //闸值=链表数组长度*加载因子。
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//扩容，如果原来的链表数组中有数据，就复杂到table中
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历老的链表数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//当oldTab[j]这条链不为空时
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果这条链只有首节点有数据，把它添加进新链表数组中
if (e.next == null)
//因为数组的容量时2的n次方，所以使用hash&(newCap-1)来计算出在那条链中。
newTab[e.hash & (newCap - 1)] = e;
//如果老的链在红黑树中，使用split()方法来复制
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//当前链中不只只有一个链表头数据时，遍历链表来复制
else { // preserve order
//数据的复制有两种情况，第一种是原位置不变，第二种是位置改变
loHead代表和原链相同位置的链，hiHead代表是原链加上原容量的链，因为扩容后长度为原长度的二倍，一个链中的节点要不在原位置的链中，要么在原位置加原容量的链中
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//通过e.hash和oldCap进行&运算来得出位置是否需要改变。
比如原数组容量为16（10000）和hash值进行&运算，如果高位1未参加运算，则为0即位置不变，如果高位参加了运算值不等于0,需要改变位置。
//loHead和hiHead分别代表原位置的链和新位置的链
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
//原位置为j
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//新位置为j+oldCap
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}Nach dem Login kopieren
Sie können sehen, dass sich die Erweiterungskapazität von HashMap verdoppelt hat und die verknüpfte Liste nicht neu positioniert werden muss, da sich die erweiterte Position entweder an der ursprünglichen Position oder befindet an der ursprünglichen Position + ursprüngliche Kapazität können durch UND-Verknüpfung des Hashs und der Länge des verknüpften Listenarrays ermittelt werden. Wenn die hohen Bits der Array-Länge an der ursprünglichen Position + der ursprünglichen Kapazität beteiligt sind. Wenn die High-Bits der Array-Länge nicht in die Berechnung einbezogen werden, befinden sie sich an der ursprünglichen Position. Darüber hinaus bleibt die Reihenfolge der verknüpften Listendaten nach der Erweiterung von HashMap unverändert.
5. Die anfänglichen Kapazitäten von HashMap und Hashtable sind unterschiedlich.
Die Anfangskapazität von Hashtable beträgt 11 und die Anfangskapazität von HashMap beträgt 16.
Das obige ist der detaillierte Inhalt vonWas ist der Unterschied zwischen HashMap und HashTable in Java? Einfacher Vergleich von HashMap und HashTable. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
