확장 가능 해시 배열 크기

Question

확장 가능 해시를 사용하여 최대 100 개의 레코드를 저장하려면 필요한 최소 배열 크기는 얼마입니까?

나는 100 개의 배열로 충분할 것이라고 추측한다. 그러나 나는 틀릴 수도있다. 나는 또한 더 작은 배열을 사용할 수 있다고 생각한다.

Answer 1

해시 함수에 대해 알고 계십니까?

확장 가능 해시에 대해 언급했습니다.
확장 가능한 해싱을 사용하면 해시를 비트 문자열로보고 일반적으로 트라이를 통해 버킷 조회를 구현합니다. 트라이 기반 조회 대신 배열의 인덱스로 변환한다고 가정합니다.

당신은 최대 100 개의 요소가 있다고 언급했습니다. 모든 뚜렷한 해시를 원한다면 7 비트의 가장 가까운 비트 조합이므로 128 가지 가능성을 가질 수 있습니다.

해시 함수가 각 요소를 7 비트 (또는 그 이상)의 다른 비트로 해시 할 수있는 경우 버킷 크기가 1 인 가장 최적의 솔루션을 갖게됩니다. 128 개의 리프 노드 또는 크기 128의 배열을 남겨 둡니다.

해시 함수가 각 요소를 6 개 (7 비트 이상)의 서로 다른 비트로 해시 할 수있는 경우 버킷 크기는 2입니다. 64 리프 노드/조합/배열 크기가됩니다.

해시 함수가 각 요소를 해시하여 7 비트 (또는 그 이상)의 다른 비트를 가질 수있는 경우 버킷 크기는 4입니다. 32 리프 노드/조합/배열 크기가됩니다.

버킷 크기를 4로 지정 했으므로 답변이 32 일 것으로 생각하고 적어도 5 개의 첫 번째 비트를 구분할 수있는 좋은 해싱 기능이 있어야합니다.

Answer 2

고성능이 필요한지 아니면 저장 용량이 필요한지에 따라 달라질 것이라고 생각합니다. 요소를 100 개의 배열에 저장할 수 있습니다. 확장 가능한 해시에 대해 많이 알지 못합니다. 그러나 해싱에 대한 일반적인 이해는 충돌의 종류가 있으며, 더 큰 배열을 사용하여 저장하면 충돌 횟수가 줄어들고 추가/삭제 및 쿼리의 성능이 빨라집니다. 나는 적어도 128 (2^k가되기 위해서, 나는 해싱의 전문가가 아니다)를 사용해야한다고 생각한다. :)