자바 의 HashTable 에 대한 자세 한 설명
HashTable 은 남 겨 진 클래스 입 니 다.많은 맵 의 상용 기능 은 HashMap 과 유사 합 니 다.다른 것 은 Dictionary 류 를 계승 하고 스 레 드 가 안전 하 며 동시 다발 성 은 Concurrent HashMap 보다 못 합 니 다.Concurrent HashMap 은 세그먼트 자 물 쇠 를 도 입 했 기 때 문 입 니 다.
Hashtable 은 새 코드 에서 사용 하 는 것 을 권장 하지 않 습 니 다.스 레 드 안전 이 필요 없 는 경우 HashMap 으로 교체 할 수 있 습 니 다.스 레 드 안전 이 필요 한 경우 ConcurrentHashMap 으로 교체 할 수 있 습 니 다.
HashMap 의 초기 용량 비교
기본 11 의 초기 용량
주의해 야 할 것 은 Hashtable 의 기본 초기 용량 크기 는 11 이 고 HashMap 은 16 이지 만 로드 인 자 는 모두 0.75f 입 니 다.
/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
this(11, 0.75f);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
임 의 지정 비 마이너스 용량또 하 나 는 Hashtable 의 initial Capacity 입 니 다.즉,초기 용량 은 당신 이 지정 한 모든 비 마이너스 정수 일 수 있 습 니 다.즉,0 을 설정 해도 됩 니 다.
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
그러나 HashMap 의 초기 용량 을 보면 말 을 잘 듣 지 않 습 니 다.기본 적 인 상황 에서 HashMap 의 초기 화 용량 을 설정 할 때 실제 HashMap 은 이 수치 보다 큰 첫 번 째 멱 을 초기 화 용량(0 1 제외)으로 사용 합 니 다.
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
HashMap 의 null 값 에 대한 지원 비교HashTable key value 는 null 을 지원 하지 않 습 니 다.
우선 HashMap 은 null 값 을 key 와 value 로 지원 하지만 HashTable 은 지원 되 지 않 습 니 다.key 도 지원 되 지 않 고 value 도 지원 되 지 않 습 니 다.
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;
}
똑똑 한 당신들 은 발 견 했 습 니까?위의 값 에서 value==null 은 NPE 를 던 졌 지만 key 를 말 하지 않 았 습 니 다.key 가 null 이 라면 key.hashCode()는 이상 을 던 질 수 있 기 때문에 판단 할 필요 가 없 지만 value 는 던 지지 않 습 니 다.그러나 주의해 야 할 실제 HashMap 은 null 값 을 지원 하지만 hash 값 의 계산 방법 에서 볼 수 있 습 니 다.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
HashTable 을 업그레이드 하여 null 을 value 로 지원 합 니 다.대부분의 코드 는 직접 copy 의 HashTable 로 value 의 빈 값 만 제거 합 니 다.
public class BuerHashTable<K, V> extends Hashtable<K, V> {
// ..... , copy HashTable , BuerHashTable.Entry
public synchronized V put(K key, V value) {
// 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;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
BuerHashTable.Entry<?,?> tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
BuerHashTable.Entry<K,V> e = (BuerHashTable.Entry<K,V>) tab[index];
tab[index] = new BuerHashTable.Entry<>(hash, key, value, e);
count++;
}
}
다음은 null 값 을 value 로 BuerHashTable 에 저장 할 수 있 습 니 다.
BuerHashTable<String, String> buerHashTable = new BuerHashTable<>();
buerHashTable.put("a", null);
Hash Table 의 상속 관계 비교Dictionary
이 종 류 는 HashTable 특유 의 계승 이다.HashMap 은 계승 되 지 않 았 다.그러나 이 추상 류 는 큰 의미 가 없다.왜냐하면 그의 방법 은 모두 Map 인터페이스 에 있 기 때문이다.사실은 이것 은 역사 문제 이다.Map 인 터 페 이 스 는 자바 1.2 에 추가 되 었 기 때문에 Dictionary 추상 류 는 자바 1.0 에 존재 한다.
public abstract
class Dictionary<K,V> {
public Dictionary() {
}
abstract public int size();
abstract public boolean isEmpty();
abstract public Enumeration<K> keys();
abstract public Enumeration<V> elements();
abstract public V get(Object key);
/**
* @exception NullPointerException if the <code>key</code> or
*/
abstract public V put(K key, V value);
abstract public V remove(Object key);
}
이 곳 의 NullPointer Exception 은 HashTable 에서 put 방법 중의 null 값 검 측 에 대응 합 니 다.마지막 으로 Dictionary 추상 류 의 주석 이다.새로운 실현 은 이 추상 류 가 아니 라 Map 인 터 페 이 스 를 실현 해 야 한다.
NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class
사실 HashMap 은 AbstractMap 류 에서 계승 한 것 이지 Map 인 터 페 이 스 를 직접 실현 한 것 이 아니 기 때문에 Dictionary 라 는 추상 류 가 실현 한 실제 Map 인터페이스 라면 HashMap 과 Hashtable 은 계승 관계 에서 일치 합 니 다.Hashtable
스 레 드 보안
사실 HashTable 은 할 말 이 많 지 않 습 니 다.비교적 중요 한 것 은 스 레 드 안전 입 니 다.그러나 이 스 레 드 안전 의 실현 방식 은 모든 조작 에 synchronized 키 워드 를 추가 한 것 입 니 다.하하!synchronized 에 대해 서 저희 가 나중에 얘 기 할 게 요.
public synchronized int size() {}
public synchronized boolean isEmpty() {}
public synchronized boolean contains(Object value) {}
public synchronized boolean containsKey(Object key) {}
public synchronized V get(Object key) {}
public synchronized V put(K key, V value) {}
public synchronized V remove(Object key) {}
HashMap 은 라인 이 안전 하지 않 습 니 다.contains 방법
HashMap 에는 Hashtable 의 contains 방법 이 없고 contains Value 와 contains Key 만 있 습 니 다.contains 방법 은 오 해 를 사기 쉽 기 때 문 입 니 다.
Hashtable 은 contains,contains Value,contains Key 세 가지 방법 을 보류 하 였 으 며,contains 와 contains Value 기능 이 같 습 니 다.
debug 소스 코드 put 방법
public synchronized V put(K key, V value) {
// Make sure the value is not null value null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
// , key , ,
Entry<?,?> tab[] = table;
// ,HashTable hashCode。 HashMap hash ( 16 16 )
int hash = key.hashCode();
// HashMap key hash tab.length-1 ;
// HashTable key hash 0x7FFFFFFF , tab.length
// hash&0x7FFFFFFF , length , 0x7FFFFFFF hash , hash , &0x7FFFFFFF , ,
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// index , key , old value,
// addEntry
Entry<K,V> entry = (Entry<K,V>)tab[index];
// key
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);
// null
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
//
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
// e tab[index] , tab[index] = new Entry<>(hash, key, value, e); ,e new Entry<>(hash, key, value, e) next
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
여기 서 우 리 는 HashMap 의 추가 방법 을 비교 해 보면 다른 사람들 이 모두 추 가 된 링크 꼬리 부분 이 분명 하 다.HashTable 은 스 레 드 가 안전 하기 때문에 이 전제 에서 헤드 검색 법 을 사용 하 는 성능 이 더욱 좋 고 그렇지 않 으 면 링크 의 끝 부분 에 삽입 되 어 있 기 때문이다.
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
마지막 으로 용량 을 늘 리 는 방법 을 다시 한 번 보도 록 하 겠 습 니 다.
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 2 +1
int newCapacity = (oldCapacity << 1) + 1;
//
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
// MAX_ARRAY_SIZE
newCapacity = MAX_ARRAY_SIZE;
}
//
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
// threshold
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// ,
for (int i = oldCapacity ; i-- > 0 ;) {
// for
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;
}
}
}
총결산지난 절 과 마찬가지 로 여기 서 저 는 이 사고 문 제 를 제 시 했 습 니 다.비록 우리 의 주장 이 틀 릴 수 있 지만 우 리 는 소스 코드 작가 가 그 당시 의 높이 에 서 있 지 못 할 수도 있 습 니 다.그러나 우 리 는 여전히 적극적으로 생각 하고 대담 하 게 토론 합 니 다.
자바 소스 코드 의 산 은 매우 높 지만,당신 이 뛰 어 넘 고 싶다 면,적어도 당신 은 등산 의 용 기 를 가 져 야 합 니 다.여기 서 나 는 나의 약간의 우견 을 제시 합 니 다.여러분 의 아 낌 없 는 가르침 을 바 랍 니 다.
int hash = key.hashCode();
addEntry(hash, key, value, index);
private void addEntry(int hash, K key, V value, int index) {
// ,
modCount++;
Entry<?,?> tab[] = table;
// count key-value , HashMap size
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
// , key hash ,
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
물론 이것 은 작은 문제 일 뿐 이지 만 다른 작은 문제 도 많 습 니 다.예 를 들 어 index 를 구 할 때 계산 방식 은 직접 모델 링 을 하 는 것 이지 연산 을 사용 하 는 것 이 아 닙 니 다.가장 큰 문 제 는 디자인 에 있 습 니 다.예 를 들 어 hash 값 의 계산 방식 은 HashMap 디자인 이 좋 지 않 습 니 다.그리고 빨 간 검 은 나무의 지원 이 없 으 면 스 레 드 안전 한 실현 방식 도 효율 적 이지 않 습 니 다.그래서 우 리 는 그것 이 남 겨 진 것 같다 고 말한다.HashTable 은 자바 1.0 시대 에 존 재 했 고 HashMap 은 자바 1.2 에 만 있 었 다.이상 은 자바 의 HashTable 에 대한 상세 한 내용 입 니 다.자바 HashTable 에 관 한 자 료 는 다른 관련 글 을 주목 하 세 요!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.