스파 스 해시 테이블의 주요 구현 아이디어는 무엇입니까?

Question

Google의 스파 스 해쉬 오픈 소스 라이브러리에는 밀도가 높은 해시 테이블과 스파 스 (sparse) 테이블의 두 가지 구현이 있습니다.

Answer 1

밀도가 높은 해시 테이블은 일반적인 텍스트 북 해시 테이블 구현입니다.

스파 스 해시 테이블은 배열 수에 따라 실제로 설정된 요소 만 저장합니다. 스파 스 테이블의 구현의 comments 인용 위해 각 요소가 오버 헤드가 발생되도록

// To store the sparse array, we store a bitmap B, where B[i] = 1 iff 
// bucket i is non-empty. Then to look up bucket i we really look up 
// array[# of 1s before i in B]. This is constant time for fixed M. 

:

// The idea is that a table with (logically) t buckets is divided 
// into t/M *groups* of M buckets each. (M is a constant set in 
// GROUP_SIZE for efficiency.) Each group is stored sparsely. 
// Thus, inserting into the table causes some array to grow, which is 
// slow but still constant time. Lookup involves doing a 
// logical-position-to-sparse-position lookup, which is also slow but 
// constant time. The larger M is, the slower these operations are 
// but the less overhead (slightly). 

가 배열 요소를 설정하는 알 스파 스 테이블은 비트 맵을 포함 1 비트 (한도).

Answer 2

스파 스 해시는 키를 값 (키당 1-2 비트)에 매핑하는 메모리 효율적인 방법입니다. 블룸 필터는 키 당 더 적은 비트를 줄 수 있지만 외부/아마 내부 이외의 키에 값을 첨부하지는 않으며 약간의 정보보다 약간 적습니다.