동적 완벽한 해시 및 유니버설 해시 함수 - 설명해주세요.

Question

그래서 해시 테이블, 해시 함수 등에 대해 읽었습니다. 위키 피디 어에서 "동적 완벽한 해싱"이 특정 버킷 내에 여러 값을 저장하는 데이터 구조로 두 번째 해시 테이블을 사용하는 방법에 대해 흥미롭게 읽었습니다.

그러나 내가 잃어버린 부분은, 보편적 인 해시 함수가 선택되어 두 번째 해시 테이블에 대한 해싱을 수행하는 방법에 관한 것입니다. 누구나이 범용 해시 함수가 양동이에 저장된 값으로부터 어떻게 결정되는지 설명 할 수 있습니까? 위키 피 디아의 "universal hash function"페이지에서이 논리와 논리를 막연히 따랐지만, 그것에 직관력을 갖기 위해 고심하고 있습니다. 특히 이러한 기능이 충돌을 어떻게 보장합니까? 또는 적어도 충돌이 감지되면 새로운 것을 생성하고, 새로운 충돌이 발생하면 어떻게하면 현실적인 시간 내에 완료 될 수 있는지를 어떻게 알 수 있습니까?

무당 벌레 책 설명 부탁드립니다.

Answer 1

완벽한 해시는 최악의 경우에도 읽기 액세스가 일정 시간이 걸린다는 것을 의미합니다.

키를 삽입하는 데 최악의 경우는 없으므로 시간 범위는 평균 (또는 아마 상각)에만 적용됩니다.

삽입 속도를 충분히 높이려면 두 번째 수준 해시 테이블이 충돌 횟수가 충분하지 않을만큼 충분히 큰 키 수 (k)에 대해 매우 크게 선택됩니다. 이것은 문제가되지 않습니다. 왜냐하면 첫 번째 레벨 해시가 키를 균등하게 분배하므로 평균적으로 두 번째 레벨의 해시 테이블이 여전히 작기 때문입니다.

두 번째 수준 테이블에 대한 해시 함수는 매개 변수화 된 해시 함수 집합에서 임의로 선택됩니다.

Answer 2

MIT 강의를 시청하는 것은 어떻습니까? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing