Rehash 수행시 성능을 향상시키는 방법은 무엇입니까?

Question

어느 시점에서 우리는 해시의 크기를 늘릴 필요가 있으며 일반적으로 우리는 다시 해쉬하기 때문에 해시 전체를 다시 구성해야합니다.

크기를 늘릴 때 전체를 다시 만들 필요가 없도록 더 나은 해결책이 있습니까?

Answer 1

언제든지 다시 해시 할 때마다 실제로 해시해야한다고하는 내용은 없습니다. 사실 실제로는해야하며 다시해야합니다 (즉, 모든 위치를 변경).

해시 (hehe, 닥터 서스 북의 시작 소리처럼)를 캐시하면 한 번만 계산하면됩니다. 따라서 실제 데이터와 함께 해시를 저장하면 나중에 해시를 다시 계산하지 않아도됩니다. 그러나 나는 당신이 이미 이것을하지 않고 있다고 가정하고 있습니다, 당신은 현재의 과정을 정확하게 설명하지 않았습니다.

// Store these instead of the data directly. This assumes immutable data. 
struct hashable_item 
{ 
    data dat; 
    int32 hash; 
} 

Answer 2

AFAIK는 주로 디스크상의 데이터베이스에 사용되지만 http://en.wikipedia.org/wiki/Extendible_hashing을 사용할 수 있습니다.

일부 상환 비용을 완화하는 일반적인 방법이 있습니다. 이에 대한 시작점은 http://en.wikipedia.org/wiki/Static_and_dynamic_data_structures 및 http://en.wikipedia.org/wiki/Dynamization입니다. 이것을 해시 테이블에 적용하면 크기가 N이고 크기가 2N 정도 인 테이블 두 개를 항상 유지해야합니다. 더 작은 오버플로가 발생하면 크기가 4N 인 테이블을 만들기 시작하지만 바로 채우지 마십시오. 크기가 2N 인 테이블을 사용하는 동안 증분 채워집니다. 크기가 2N 인 테이블이 가득 차면 크기가 4N 인 테이블을 준비해야합니다. 해시 테이블의 특별한 경우에는 확장 가능한 해싱이 더 좋습니다.