Quelle est la différence entre HashMap et HashTable en Java ? Comparaison simple de HashMap et HashTable
- 青灯夜游avant
- 2018-10-22 17:54:422553parcourir
Ce que cet article vous apporte, c'est quelle est la différence entre HashMap et HashTable en Java ? Une comparaison simple de HashMap et HashTable. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. J'espère qu'il vous sera utile.
1. Tout d'abord, jetons un coup d'œil à la structure d'héritage :
HashMap
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
Hashtable
public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable
1. , nous pouvons voir à travers le nom HashMap est conforme aux règles de dénomination des cas camel, mais Hashtable n'est pas conforme aux règles de dénomination des cas chameaux. Grâce à la structure d'héritage, nous constatons que HashMap hérite de AbstractMap
2. On peut retrouver grâce aux attributs de la classe que dans jdk1.8, lorsque le nombre de nœuds stockés dans une chaîne dans le HashMap est supérieur ou égal à 8 et la longueur de la liste chaînée Le tableau est supérieur à 64, il est converti en arbre rouge-noir et Hashtable ne se convertit pas en arbre rouge-noir.
3. Put() de Hashtable et put() de HashMap
Opération put de 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;
}
La méthode dans Hashtable ajoute le mot-clé synchronisé, c'est donc un synchrone méthode.
Grâce à if (value == null) throw new NullPointerException();} nous pouvons voir qu'il ne permet pas à la valeur de value d'être vide, et lorsque la clé est nulle, appeler key.hashCode() ; va lancer Le pointeur nul est anormal, donc la clé et la valeur dans l'entrée stockée dans la table de hachage ne peuvent pas être vides. De plus, Hashtable obtient l'indice de la liste chaînée via l'opération %.
En regardant HashMap ci-dessous
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);
}
vous pouvez voir que la clé dans HashMap peut avoir une valeur nulle. Lorsque la clé est nulle, sa valeur de hachage est 0 et la méthode de HashMap doit être nulle. obtenir l'indice du tableau de liste chaînée Différent de Hashtable, il est calculé en utilisant (n-1)&hash, car la longueur de la liste de tableaux de HashMap est de 2 à la nième puissance.
Résumé : la clé dans HashMap peut avoir une valeur nulle, la valeur peut avoir plusieurs valeurs nulles, et la clé et la valeur dans Hashtable ne peuvent pas être vides. Les méthodes de positionnement de la chaîne sont différentes. HashMap obtient l'indice via l'opération &, tandis que Hashtable obtient l'indice via %, et l'opération & est plus rapide.
4. HashMap et Hashtable ont des méthodes d'expansion différentes.
Extension de la table de hachage :
@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;
}
}
}
Grâce au code source, nous avons constaté que la longueur maximale du tableau de liste chaînée Hashtable est la valeur maximale du type int - 8. L'expansion du Hashtable doublera la longueur d'origine plus 1 et la liste chaînée devra être repositionnée après l'expansion. De plus, après l’expansion, l’ordre de la liste chaînée du tableau devient l’ordre inverse de l’ordre d’origine.
Extension HashMap :
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;
}
Vous pouvez voir que la capacité d'expansion de HashMap a doublé, et il n'est pas nécessaire de repositionner la liste chaînée, car la position étendue est soit à l'original position, Soit à la position d'origine + la capacité d'origine, cela peut être déterminé en effectuant un AND sur le hachage et la longueur du tableau de liste chaînée. Si les bits hauts de la longueur du tableau participent au calcul, ils seront à la position d'origine +. la capacité d'origine. Si les bits hauts de la longueur du tableau ne sont pas impliqués dans le calcul, ils seront à la position d'origine. De plus, l'ordre des données de la liste chaînée reste inchangé une fois HashMap développé.
5. Les capacités initiales de HashMap et Hashtable sont différentes.
La capacité initiale de Hashtable est de 11 et la capacité initiale de HashMap est de 16.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!