해시 테이블 및 분리 된 연결 : 버킷 목록에서 반환 할 값을 어떻게 알 수 있습니까?

Question

데이터 구조 및 알고리즘 클래스의 해시 테이블에 대해 배우고 있으며 별도의 연결을 이해하는 데 어려움을 겪고 있습니다.

나는 각 버킷에 키 - 값 쌍이 들어있는 노드에 대한 포인터가 있으며, 각 노드에는 현재 버킷의 미니 링크 된 목록에있는 다음 (잠재적 인) 노드에 대한 포인터가 들어 있습니다. 이것은 주로 충돌을 처리하는 데 사용됩니다.

이제 단순성을 위해 해시 테이블에 5 개의 버킷이 있다고 가정합니다. 적절한 해시 테이블 인스턴스를 만든 후 내 메인에 다음 코드 줄을 작성했다고 가정합니다.

myHashTable["rick"] = "Rick Sanchez"; 
myHashTable["morty"] = "Morty Smith"; 

이의 두 문자열 키 rick 및 morty에 대해 동일한 버킷 인덱스를 생성하는 일이 어떤 해싱 우리가 너무 사용하는 기능을 가정 해 봅시다. 단순화를 위해 버킷 인덱스가 인덱스 0이라고 가정 해 봅시다.

우리 해시 테이블의 인덱스 0에서 우리는 두 번째 노드에 넣기로 결정한 순서대로 Rick Sanchez과 Morty Smith의 값을 갖는 두 개의 노드를 갖습니다.

내가 여기에 우리의 코드 당 Rick Sanchez입니다 rick에 해당하는 값을 표시하려면, 어떻게 반환 할 필요가있는 노드로 결정 0

의 버킷 인덱스를 생성합니다 해싱 함수? 키가 rick과 일치 할 때까지 노드를 반복합니까?

Answer 1

해시 테이블 충돌을 해결하려면 해시 값이 이고 다른 해시 값과 충돌하는 항목을 해시 테이블에 넣거나 가져 오는 것이 좋습니다 이행; 이것은 일반적으로 연결된 목록입니다. 충돌의 경우 이것은 해시 테이블 구조에 대한 최악의 경우이며 O (n) 작업으로 끝나고 연결된 목록의 올바른 항목으로 이동합니다. 그게 바로 당신이 말한 루프입니다. 일치하는 키으로 항목을 검색합니다. 그러나 균형 잡힌 트리와 같은 데이터 구조를 검색하는 경우 Java8 구현과 같이 O (logN) 시간이 될 수 있습니다. JEP 180: Handle Frequent HashMap Collisions with Balanced Trees으로

는 말한다 :

주요 아이디어는 해시 버킷 의 항목 수는 특정 임계 값 이상으로 증가하면, 그 양동이가 균형에 항목의 연결리스트를 사용하여 전환하는 것입니다 나무. 충돌이 많으면 O (n)에서 O (log n)까지 최악의 성능이 향상됩니다. 그 코드의 155 부분을 다시 할 것입니다이 기술은 이미 JEP의 일부입니다 java.util.concurrent.ConcurrentHashMap 클래스도 JDK 8에 포함시킬 을 예정 의 최신 버전에서 구현 된

HashMap 및 LinkedHashMap 클래스에서 같은 아이디어를 구현하는 데 사용됩니다.

필자는 항상 기존 구현을 살펴볼 것을 강력하게 제안합니다. 하나에 대해 말하면 Java 7 구현을 살펴볼 수 있습니다. 그러면 코드를 읽는 기술이 향상 될 것입니다.이 기술은 거의 중요하거나 코드 작성보다 더 자주 사용됩니다. 나는 그것이 더 노력이지만 그것이 효과가 있다는 것을 압니다.

예를 들어, 자바 7에서 HashTable.get 방법을 살펴 : 여기

public synchronized V get(Object key) { 
    Entry<?,?> tab[] = table; 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % tab.length; 
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { 
     if ((e.hash == hash) && e.key.equals(key)) { 
      return (V)e.value; 
     } 
    } 
    return null; 
} 

는 우리가 보는 그 경우 ((e.hash == 해시) & & e.key.equals (키))가 일치하는 키가있는 올바른 항목을 찾으려고합니다.

그리고 여기에 전체 소스 코드입니다 HashTable.java