무지개 테이블의 축소 기능

Question

레인보우 테이블 체인이 매우 길기 때문에 병합을 방지하기 위해 인덱스를 사용하는 동안 각 해시를 줄이기 위해 사용되는 여러 가지 축소 함수가 있습니까? 또는 다른 것?

Answer 1

무지개 표의 축소 기능은 모두 다르며 (열당 하나씩) 일반적으로 단일 축소 기능의 확장으로 구축됩니다.

예를 들어, r을 축소 함수 (예 : r (x) = x mod N, 여기서 N은 입력 집합의 크기 임)라고 가정 한 다음 무지개 테이블에 필요한 것으로서 감소 함수 패밀리를 생성합니다. , r_i (x) = r (x + i)를 사용할 수있다.