가정 table size m = 2^i * 해시 함수 h(x) = x mod 2**i
일반적으로는 잘 동작하지만 extream하게 poor한 케이스도 쉽게 찾을 수 있 성능상 문제 있는 케이스: 모든 숫자의 마지막 비트가 동일한 데이터 셋의 경우 그렇게 됨
이걸 해결하기 위해 아래와 같은 해시 충돌 방지 로직에는 Open addressing, Chaining이 있다.을 사용함 j = ((5*j) + 1) mod 2**i
j는 버킷의 인덱스, 이런 시퀀스는 해시테이블안에 있는 모든 m buckets을 방문할 수 있도록함 키의 높은 비트들이 해싱에 사용될 수 있도록 perturb가 기본적으로 초기화됨 h(x)에 대해 PER perturb 교란하다.
perturb >>= PERTURB_SHIFT
j = (5*j) + 1 + perturb