Hashtable 기본 자리 표시 자?

Question

HashTable 데이터 구조를 이해하려고합니다. 나는 HashTable에서 먼저 해시 코드의 키를 가리킨 다음 모듈러스 연산자를 사용하여 Hash code을 정수 인덱스로 변환하고 데이터가 배치 된 HashTable에서 위치를 가져 오는 데 사용되는 HashFunction을 이해합니다.

높은 수준에서 흐름은 다음과 같습니다.

Key ->Hash Function ->Hash code ->Modulo operator ->integer index ->Store in HashTable

키는 나머지 연산자 방출로 인덱스에 기초하여 저장되어 있기 때문에, 내 의심되면, 내부 데이터 구조가 무엇 실제 데이터를 보유하는 데 사용됩니까? 그것은 배열이 색인을 사용하여 액세스 할 수 있기 때문에 배열입니다.

아무도 이해할 수 있습니까?

Answer 1

구현에 완전히 의존하지만, 배열이 저렴한 비용으로 요소에 액세스하기 쉽고 링크 된 목록이 해시 충돌을 처리하는 데 필요하므로 기본 데이터 구조가 링크 된 목록의 배열이라는 데 동의합니다. 여기

는 처음에는 초기 용량 배열을 만들고 그것을 java openjdk Hashtable
구현되는지 상세한 예이다

새로운 요소가 추가 될 때 용량 임계 매번를 확인

table = new Entry<?,?>[initialCapacity]; 

. 한계치에 도달 할 때 다시 해싱 행하고 Entry 형태 연결리스트

int newCapacity = (oldCapacity << 1) + 1; 
    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; 

해시 테이블 오래 어레이의 더블 인 새로운 배열을 생성한다. 해시 충돌시 2 개의 다른 값에 대한 인덱스가 같고 링크 된 목록을 통해 필요한 값을 검사하므로 사용됩니다.

private static class Entry<K,V> implements Map.Entry<K,V> { 
    final int hash; 
    final K key; 
    V value; 
    Entry<K,V> next; 

당신은 더 나은 이해를 위해 해시 테이블의 other more simple 구현을 확인 할 수 있습니다.