해시 테이블 구현

Question

며칠 전에 여러 가지 데이터 구조를 구현하는 방법에 대해 읽었으며 해시 테이블을 가지고 특정 지점에 갇혀있었습니다.

해시 테이블 구현 방법에 대한 내 이해 : 키 K는 해시 함수 H에 전달되어 해시 된 버전의 K, HK를 반환합니다. HK는 아마도 충돌을 설명하기 위해 적어도 uint32_t가되어야합니다. 우리는 크기 X의 배열을 가지고 있습니다.이 배열의 인덱스 HK에 항목이 저장되어 있습니다. 그러나 이것은 미리 할당 된 uint32_t atleast 배열을 필요로하지 않습니다. (또는 H의 반환 값이 무엇이든간에)? 데이터 배열 자체에 데이터 자체를 저장하지 않고 ptr을 데이터에 저장한다고 가정하면 길이가 uint32_t 인 ptr_t 배열이 필요합니다. 64 비트에서는 메모리 사용량이 매우 낭비되는 것 같습니다. : 2^32 * 8 = 34359738368 바이트 또는 ~ 32GB의 데이터에 대한 ptrs의 배열은 실제로 실제로 구현 된 방법이 아닙니다.

그래서 나는 무엇이 누락 되었습니까?

Answer 1

구현에 따라 다릅니다. 이 작업을 수행하는 기본적인 방법은 세 가지가 있습니다.

1) 작은 해시가 사용됩니다. 따라서 32 비트 해시를 사용하는 대신 8 비트 해시가 사용됩니다.

2) 여러 수준의 해싱이 사용됩니다. 예를 들어 12 비트 해시는 항목이 들어갈 "버킷"을 결정할 수 있지만 전체 32 비트 해시가 일치하는 경우에만 충돌이 발생합니다. 각 버킷은 연결된 목록 또는 유사한 구조로 저장됩니다. (아마도 하나의 전체 32 비트 해시를 검색하기 위해 최적화되어 있습니다.)

3) 희소 배열이 사용됩니다. 이들은 채워지지 않은 슬롯을 위해 빈 공간을 실제로 저장할 필요가없는 데이터 구조입니다. 실제로는 나무와 같이 완전히 다른 것일 수 있지만 효율적인 검색 기능을 가진 희소 배열처럼 작동합니다.

Answer 2

해시 테이블을 확장 할 수 있도록 구성해야합니다. 이를 수행 할 수있는 몇 가지 방법이 있습니다. this을 읽으면 도움이 될 것입니다. 이 예제에서는 연결된 목록이 사용됩니다. 더 이상 빈 값이없는 경우 테이블을 확장해야합니다. 다음과 같은 문제가 발생합니다 :지도를 확장하면 H 기능이 이전 K 키의 새 HK 값을 반환 할 수 있습니다. 따라서이 문제를 해결하는 방법을 생각해야합니다. 방법 중 하나는 테이블을 확장 할 때 모든 값을 다시로드하는 것입니다. 자주 확장하지 않으면 정상입니다.

Answer 3

현실적으로, 크기가 더 작은 고정 된 양의 배열이 있습니다. (링크 된리스트의 결과) 또는 프로빙 (최악의 예 : hash (x)가 취해진다면 해쉬 (x) +1)을 충돌시에 시도하십시오. 버킷 크기, 가장 단순한 경우로 uint32 및 mod를 가져옵니다.

하중 계수를 정의 할 수 있습니다. 배열의 N %가 채워지면 배열의 크기를 두 배로 늘리고 모든 배열을 새 배열로 다시 채 웁니다. 예를 들어, 50 %에서 75 % 사이의 사용을 가정 해 봅시다.

음, 그렇게 비싸지 않습니까? 글쎄,별로. 매번 배열의 크기를 배가한다고 가정 해 봅시다. 따라서 N 개의 항목을 추가합니다. 마지막 항목은 사본을 트리거합니다. N은 O (1)에 추가 한 다음 O (N) 사본 하나를 추가합니다. 그러나 대기 - O (N)/N은 O (1)로 평균되므로, 상쇄 된 평균 비용은 O (1)이며, 부하 계수가 현명하게 선택되었다고 가정합니다.

Answer 4

해시 테이블의 일반적인 구현은 연결된 목록의 배열입니다. 연결된 목록은 다른 데이터 구조로 쉽게 바뀔 수 있으므로 지금부터는 Bucket이라고 부를 것입니다.

아이디어는 간단하다 :

class HashTable { 
public: 


private: 
    std::vector<Bucket*> _array; 
}; 

그런 다음 홍콩을 가지고 는 일반적으로 모듈로, 배열에 맞게에게 그것을 감소 ​​: 버킷의 인덱스를 제공 HK % size(_array)를 사용할 수 있습니다.