몇 개의 해시 버킷

Question

해시 테이블 (또는 해시 테이블 위에 내장 된 다른 데이터 구조)이 채워지고있는 경우 더 많은 버킷이있는 새 테이블을 만드는 시점에서 어떤 시점에서 만들어야합니다. 그리고 지금까지 테이블에있는 N 항목이 주어지면 새 버킷에 얼마나 많은 버킷을 사용할 수 있는지 어떻게 알 수 있습니까?

그래서 100 개의 버킷이 있다고 가정 해 봅시다. 50 개의 항목이있을 때 재구성해야합니까? 500? 5000? 아니면 가장 가득한 양동이와 키를 찾아야합니까? 그런 다음 그 지점을 쳤을 때 새 해시 테이블을 얼마나 크게 만들까요?

이와 관련하여, 당신이 거의 얼마나 많은 품목이 들어갈 것인지 알고 있다면, 평균 성능을 얻기 위해 버킷 수를 계산할 수있는 방법이 있습니까?

실제 답변은 특정 예에서 속도 대 크기가 얼마나 중요한지와 같은 많은 다른 고려 사항에 달려 있지만 일반 길드 라인을 찾고 있습니다.

또한 좋은 프로파일 링이 병목 현상이라는 것을 나타내지 않는 한 이런 종류의 일을 최적화해서는 안된다는 것을 알고 있습니다. 나는 단지 많은 해시 테이블을 사용하고 이것에 접근하는 방법을 궁금해하는 프로젝트에 대해 생각하고 있습니다.

Answer 1

엄지 손가락의 좋은 규칙 (항상 이상적이지는 않습니다. 즉, 내부에 100 개의 버킷과 80 개의 품목이 있다면, 이전에 몇 번의 충돌이 있더라도 용량을 늘리는 데 시간이 걸립니다.

얼마나 늘려야합니까? 글쎄, 완벽한 가치도 없습니다. 가장 간단한 솔루션은 각 증가 할 때마다 용량을 두 배로 늘리는 것입니다. 그래서 그것은 200, 400, 800 등으로갑니다. 이것이 너무 많다고 생각한다면 (결국 해시 가능이 실제로 커지고 16MB를 채우지 않을 때 8MB 메모리에서 16MB로 점프 할 경우) 더 작은 성장 요인을 선택하십시오. 최소한 1/3이 권장됩니다 (100에서 133으로 성장함). 타협으로 매번 50% 성장할 수 있습니다.

이 모든 것은 충돌 방법에 따라 다릅니다. 그들을 다루는 간단한 방법 (내가 개인적으로 좋아하는)은 충돌이있을 때 링크 된 목록에 항목을 저장하는 것입니다. 3 개의 항목이 동일한 키에 배치되면 여전히 최대 3 개만 비교할 수 있습니다. 링크 된 목록은 검색에 매우 효과적이지 않기 때문에 60% 용량을 사용하여 해시 가능을 빠르게 유지하는 데 용량을 일찍 늘릴 수 있습니다. Otoh, 당신은 더 정교한 일을하고 충돌 횟수에 대한 통계를 유지할 수 있습니다. 충돌이 거의없는 한 (해시 기능이 매우 양호한 경우) 용량의 99%가 사용중인 경우에도 전혀 다시 할 필요가 없습니다. 또한 정교한 방식으로 충돌을 처리하는 경우 (예 : 각 노드는 다시 정렬 된 테이블이므로이 내에서 이진 검색을 수행 할 수 있음) 테이블이 200%로로드되면 조회가 충분히 빠를 수 있습니다 (따라서 품목의 두 배나 많은 항목이 있습니다. 용량으로). 이 경우 가장 큰 분류 테이블이 얼마나 큰지 통계를 유지할 수 있으며 8 개의 항목보다 더 커지면 너무 느려지고 다시 할 수 있다고 생각합니다.

재 경적은 매우 느리기 때문에 가능한 한 자주 피해야합니다. 따라서 다시 할 수있는 경우 용량을 너무 적게 늘리지 마십시오. 그렇지 않으면 더 많은 항목을 추가 할 때 곧 다시 다시 호흡해야합니다. 따라서 다시 호흡해야 할 때는 현재 테이블에있는 항목 수보다 용량을 크게 크게 크게 높이면 다른 모든 것이 용량이 너무 적습니다.

Answer 2

일반적으로, 당신은 공식적으로 α =로 정의 된로드 계수 (비공식적으로 이미 말한)를 찾습니다.N / N, 즉, 총 버킷과의 비율. 해시 테이블이 올바르게 작동하기 위해 (또는 적어도 수학적 용어로의 성능에 대해 추론하기 위해) α <1이어야합니다.

다른 모든 것은 실제로 경험적 테스트에 달려 있습니다. 해시 테이블이 α> 0.5에서 시작하지 않는다면 그 값을 유지하십시오. 이 값은 또한 충돌 해상도 기술에 따라 다릅니다. 체인을 사용하여 해싱하려면 열린 주소로 해싱보다 다른 하중 계수가 필요할 수 있습니다. 또 다른 요인은 캐시 지역입니다. 테이블이 너무 커지면 기본 메모리에 맞지 않습니다. 배열에 대한 액세스가 무작위이므로 캐시에서로드하면 병목 현상이 될 수 있습니다.

Answer 3

해시 테이블에는 일반적으로 개방 및 닫는 두 가지 유형이 있습니다.

열린 해시 테이블에서 해시를 기반으로 오른쪽 버킷을 찾은 다음 해당 버킷에서 매달려있는 항목 목록을 작성합니다.

폐쇄 된 해시 테이블에서 해시 값을 사용하여 초기 버킷을 찾을 수 있으며 차단 된 경우 다음 값을 조사합니다. 단순한 경우에는 다음 무료 버킷을 찾아서이 작업을 수행하거나 항목에서 두 번째 해시 값을 만들 수 있고 그로 인해 단계를 밟을 수 있습니다 (그러나 이것이 해시 테이블 크기의 프라임 모듈로서 모든 것을 방문해야합니다. 버킷).

열린 해시 가능은 일반적으로 크기가 조정되지 않습니다. 초기 크기를 문제에 대해 합리적이라고 생각하는 것으로 설정했습니다. 다른 사람들이 지적했듯이 당신은 열린 해시 테이블에서 크기를 조정할 수 있지만,이 데이터 구조의 성능에 대한 추론은 이제 매우 어려워집니다. 주어진 버킷의 길이가 L 일 때 크기를 조정하면 ~할 것 같다 전체 해시 테이블의 L 항목 만 크기를 조정하면 매우 비효율적입니다.

폐쇄 된 해시 테이블은 하중 계수 (해시 가능 / 버킷의 항목의 없음)가 사전 정의 된 값을 누르면 크기가 조정됩니다. 나는 80%를 사용하는 경향이 있지만 정확한 값은 너무 중요하지 않을 것입니다.

폐쇄 된 해시 테이블의 이점은 상각 항목을 삽입하는 비용은 항상 O (1)입니다 (좋은 해시 기능을 가정). 크기 조정 비용으로 인해 특정 항목을 삽입하는 것은 O (n) 일 수 있지만 매우 드물게 이루어집니다.

Answer 4

건축중인 해시 테이블의 유형에 따라 다릅니다. 고정 어레이 기반 해시 테이블을 사용하는 경우 (버킷의 링크 된 목록과 반대로) 테이블이 가득 찼을 때 또는 최대 프로브 수에 도달했을 때 배열을 크기를 조정해야합니다 (속도에 더 관심이 있는지 여부에 따라 메모리). 링크 된 목록을 사용하는 경우 메모리가 그 이후로 관심이 없으며 빈 공간을 조사 할 필요가 없으므로 크기 조정은 거래에 크게 크지 않습니다.

해시 테이블의 키는 버킷 수가 아닌 해싱 알고리즘입니다. 이상적으로는 항상 각 버킷에서 최대 하나의 항목을 원하므로 해시 테이블의 항목 수 = 버킷 수를 할 때 이상적으로 크기를 조정해야합니다. 데이터가 균등하게 분산되지 않으면 더 나은 크기 조정 전략보다 더 나은 해시 알고리즘을 사용하는 것이 좋습니다.

Answer 5

선형 해싱을 사용하는 경우 일정한 하중 계수를 유지하여 테이블 자체가 자동으로 크기 조정을 처리합니다.