Java에서 HashMap과 HashTable의 차이점은 무엇입니까? HashMap과 HashTable의 간단한 비교
- 青灯夜游앞으로
- 2018-10-22 17:54:422553검색
이 기사에서 제공하는 내용은 Java에서 HashMap과 HashTable의 차이점이 무엇입니까? HashMap과 HashTable의 간단한 비교입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.
1 먼저 상속 구조를 살펴보겠습니다.
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. , 이름 전달 HashMap은 카멜 케이스 명명 규칙을 따르지만 Hashtable은 카멜 케이스 명명 규칙을 따르지 않는다는 것을 알 수 있습니다. 상속 구조를 통해 HashMap은 AbstractMap
2. jdk1.8에서 HashMap의 체인에 저장된 노드의 개수가 8보다 크거나 같을 때 클래스의 속성을 통해 알 수 있습니다. 연결된 목록 배열이 64보다 크면 레드-블랙 트리로 변환되고 Hashtable은 레드-블랙 트리로 변환되지 않습니다.
3. Hashtable의 put() 및 HashMap의 put()
Hashtable의 put 작업:
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;
}
Hashtable의 메서드에 동기화 키워드가 추가되었습니다. 그것은 동기화된 방법입니다.
if (value == null) throw new NullPointerException();}을 통해 value의 값이 비어 있는 것을 허용하지 않으며, 키가 null인 경우 key를 호출하는 것을 볼 수 있습니다. hashCode(); 널 포인터 예외가 발생하므로 Hashtable에 저장된 항목의 키와 값은 비어 있을 수 없습니다. 또한 Hashtable은 % 연산을 통해 연결된 목록의 첨자를 얻습니다.
아래 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);
}
HashMap의 키가 null을 가질 수 있음을 알 수 있습니다. 키가 null이면 해당 해시 값은 0이고 HashMap은 연결된 목록 배열. 대상 방법은 Hashtable과 다릅니다. HashMap의 배열 목록 길이는 2의 n제곱이므로 (n-1)&해시를 사용하여 계산합니다.
Summary: HashMap의 키는 하나의 null을 가질 수 있고, 값은 여러 개의 null을 가질 수 있으며, Hashtable의 키와 값은 비워둘 수 없습니다. 체인 위치를 지정하는 방법이 다릅니다. HashMap은 & 연산을 통해 첨자를 얻는 반면, Hashtable은 %를 통해 첨자를 얻으며 & 연산이 더 빠릅니다.
4. HashMap과 Hashtable은 확장 방법이 다릅니다.
Hashtable 확장:
@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;
}
}
}
소스 코드를 통해 Hashtable 연결 목록 배열의 최대 길이가 int 유형 -8의 최대값임을 확인했습니다. Hashtable의 길이는 원래 2배의 1로 변경되며 연결된 목록은 확장 후 위치를 변경해야 합니다. 게다가 확장 후에는 배열 연결 리스트의 순서가 원래 순서의 역순이 됩니다.
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;
}
HashMap의 확장 용량이 두 배로 늘어난 것을 볼 수 있으며, 확장된 위치는 다음 중 하나이므로 연결 리스트의 위치를 변경할 필요가 없습니다. 원래 위치는 원래 위치 + 원래 용량 중 하나입니다. 이는 해시와 연결된 목록 배열의 길이를 AND하여 결정할 수 있습니다. 배열 길이의 상위 비트가 계산에 참여하는 경우 해당 위치에 있게 됩니다. 원래 위치 + 원래 용량. 배열 길이의 상위 비트가 계산에 포함되지 않으면 원래 위치에 있게 됩니다. 또한 HashMap이 확장된 후에도 연결 목록 데이터의 순서는 변경되지 않습니다.
5. HashMap과 Hashtable의 초기 용량은 다릅니다.
Hashtable의 초기 용량은 11이고, HashMap의 초기 용량은 16입니다.
위 내용은 Java에서 HashMap과 HashTable의 차이점은 무엇입니까? HashMap과 HashTable의 간단한 비교의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!