해시 테이블의 크기를 정적으로 두십시오 (한 번 설정합니다). 엔트리 수에 따라 설정하고 싶습니다. 검색은 크기가 소수이고 2 * N (내가 추측하는 가장 가까운 소수)과 같아야 함을 확인했습니다. 여기서 N은 항목 수입니다.해시 테이블의 크기
해시 테이블은 새로운 항목을 허용하지 않으며 삭제하지 않는다고 가정합니다.
항목의 수는 2 * N이 나에게 너무 많은 것 같습니다 크기를 설정, 그러나
200, 2000, 20000 및 2000000 될 것입니다. 그렇지 않아? 왜? 그것이 있다면, 나는 골라야하는 크기입니까?
충돌을 피하고 싶습니다. 또한 해시 테이블에 이상적인 크기가 없다는 것을 이해하지만 출발점을 찾고 있습니다.
나는 C를 사용하여 나 자신을 교육하기 위해 자신의 구조를 만들고 싶다.
크기는 소수이어야하며 2 * N 소수라고 생각합니다). 여기서 N은 항목의 수입니다.
확실히 은이 아니어야합니다. 아마도이 권장 사항은 0.5의 부하 계수가 최소한 기본적으로 좋은 절충안이라는 것을 의미합니다.
크기의 소수성은 무엇을 당신이 선택 collision resolution algorithm에 따라 달라집니다.일부 알고리즘 은 프라임 테이블 크기 (이중 해싱, 2 차 해싱)가 필요하고 다른 알고리즘은 그렇지 않습니다. 그리고 매우 저렴한 모듈로 연산을 허용하기 때문에 테이블 크기는 2입니다. 그러나 가장 가까운 "사용 가능한 테이블 크기"가 2 배로 다를 경우 해시 테이블의 메모리 사용량이 신뢰할 수 없습니다. 따라서 선형 해싱 또는 별도의 연결을 사용하는 경우에도 2 크기의 비 출력을 선택할 수 있습니다.
prime table size를 선택하면 알고리즘이이를 필요로하기 때문에 또는 power-of-error에 의해 암시 된 메모리 사용에 대한 만족도가 만족스럽지 않기 때문에, 다음과 같은 이유로 소수의 소수를 선택하는 것이 중요합니다. 2 크기), 표 슬롯 계산 (표 크기에 따라 모듈)이 해싱과 결합 될 수 있습니다. 자세한 내용은 this answer을 참조하십시오.
해시 함수 배급이 나쁜 경우 (Neil Coffey의 답변에서) 2의 거듭 제곱의 표 크기가 바람직하지 않은 점은 잘못된 해시 함수가 있더라도 avalanching이더라도 여전히 힘의 힘을 사용하기 때문에 실용적이지 않기 때문에 실용적이지 않습니다. 2 크기는 프라임 테이블 크기로 전환하는 것보다 빠르다. 왜냐하면 단일 적분은 여전히 최신의 CPU에서 더 느리기 때문에 멀티 어 플리케이션과 시프트 연산이 필요하다. 지. MurmurHash3에서.
항목은 200, 2000, 20000 및 2000000
난 당신이 무슨 뜻 않았다 이해하지 못하는 것입니다.
그러나 크기를 2 * N으로 설정하는 것은 나에게 너무 많이 보인다. 그렇지 않아? 왜? 그것이 있다면, 나는 골라야하는 크기입니까?
일반적인 규칙은 space-time tradeoff입니다. 해시 테이블에 할당하는 메모리가 많을수록 더 빠른 해시 테이블이 작동합니다. Here이 것을 보여주는 몇 가지 차트를 찾을 수 있습니다. 따라서, 테이블 크기 ~ 2 * N을 할당하면 메모리를 낭비 할 것이라고 생각하면 더 작은 크기를 자유롭게 선택할 수 있지만 해시 테이블에서의 연산이 평균적으로 느려질 것입니다.
나는 충돌을 피하고 싶습니다. 또한 해시 테이블에 이상적인 크기가 없다는 것을 이해하지만 출발점을 찾고 있습니다.
충돌을 완전히 피할 수는 없습니다 (birthday paradox 기억 : 특정 비율의 충돌은 일반적인 상황입니다. 이 비율은 평균 작동 속도에만 영향을 미칩니다 (이전 섹션 참조).
충돌이 발생하면 버킷에 목록이 생기고 무차별하게 검색 할 것입니다. "항목은 200, 2000 ..."항목의 수는 200 등이 될 것입니다. 나는 그 트레이드 오프를 이해합니다. 그러나 다른 대답으로 당신은 또한 내 해시 테이블의 크기를 제안하지 않습니다. 먼저 해쉬 함수를 선택해야하기 때문입니까? – gsamaras
@ G.Samaras는 기본적으로 2 * N에 가장 근접한 2 크기의 힘이어야합니다. 메모리 사용에 대한 더 나은 제어가 필요한 경우에만 기본 크기를 사용하십시오. – leventov
성능 그래프가있는 링크 된 기사에 재미있는 부가 메모가 있습니다. 해시 테이블에 할당 된 메모리가 CPU 캐시보다 크면 알고리즘 이익이 CPU 캐시 미스에 의해 상쇄되는 경향이 있으므로 추가 메모리 크기에는 이점이 없습니다. –
질문에 대한 답변은 해시 기능의 품질에 따라 다릅니다. 당신이 좋은 품질의 해시 함수가있는 경우 (즉 the bits of the hash code will be "distributed evenly" 평균 한) 다음 :
그래서 첫 번째로 소수의 버킷을 사용하는 것이 본질적으로 해시 기능이 좋지 않은 상황을 완화하는 데 도움이됩니다. 좋은 품질의 해시 함수를 제공한다면 버킷의 수에 실제로 제약 조건이 있다는 것은 분명하지 않으며 일반적인 선택은 2의 거듭 제곱을 사용하여 모듈러스가 비트 AND 일뿐입니다 그건 요즘은 중요하지 않습니다.) 좋은 해시 테이블 구현에는 원래 해시 함수의 품질이 좋지 않은 상황을 완화하고 완화하기위한 보조 해시가 포함됩니다. 예를 들어 Java HashTable의 소스 코드를 참조하십시오.
일반적인로드 요소는 0.75입니다 (즉, 75 개의 항목마다 100 개의 버킷이 있음). 이것은 버킷의 약 50 %가 하나의 항목 만 가지고 있기 때문에 성능면에서는 좋은 결과를 얻을 수 있습니다. "정확한"부하율은 사용자가 원하는 시간/공간 트레이드 오프에 달려 있습니다.
매우 높은 성능의 응용 프로그램에서 잠재적 인 설계 고려 사항은 실제로 메모리에서 구조/버킷을 구성하여 CPU 캐시 성능을 최대화하는 방법입니다. ("최상의"구조에 대한 답은 근본적으로 "데이터로 실험하는 데 가장 잘 수행되는 것"입니다.)
내 해시 기능을 결정하지 않았습니다. 첫 번째 링크를 통해 내가 결정할 수 있다고 생각합니다. 나는 부분적으로 당신의 대답을 이해합니다. 예를 들어 완벽한 해시 함수가있는 경우 해시 테이블의 크기는 N (버킷 당 하나의 항목)이어야합니다. 푸 아송 분포는 항목이 삽입되는 방법과 관련이 있습니까? 아이템이 특정 버킷에 삽입되어야 할 가능성이 있다는 것을 의미합니까? 부하 요인에 관해서는, 나는 어떻게 든 방정식에 그것도 넣어야합니까? 네가 나라면, 테이블의 크기를 어떻게 정 하겠니? 나는 2 진 테이블을 사용하는 것에 관심이 없다. – gsamaras
아니요, "완벽한"해시 함수는 효과적으로 100 개의 임의 숫자를 고려하여 100 개의 무작위로 선택된 항목을 나타낼 수있는 해시 함수입니다. 그래서 당신은 100 개의 버킷을 가지고 있고, 1-100의 범위에서 100 개의 무작위 수를 선택한다고 생각합니다. 즉, 항목과 동일한 수의 버킷을 갖는 것과 같은 사고 실험입니다. 실제로 100 개의 임의의 숫자를 선택하면 각 숫자가 정확히 한 번만 기대됩니다. 오히려 2 ~ 3 번 복제 된 숫자가 전혀 없을 것입니다 ... –
... "낭비"가 없도록 모든 단일 버킷을 정확히 채우는 "이상적인" 일반적인 경우에 대처하는 현실적인 목표가 아닙니다. 이것은 당신의 해시 함수가 불완전한 것과는 관련이 없습니다; 오히려 "완벽한"해시 함수로 통계적으로 기대하는 상황은 주어진 버켓에 많은 항목이있는 것을 피하려면 실제로 낭비되는 것입니다. –
최적의 크기를 모르지만 해시 충돌이 있음을 명심하십시오. 이상적인 버켓 수는 해시 공간의 크기 및 해시 충돌 확률과 관련이 있다고 생각합니다. N이 클 경우 2 * N은 과도한 메모리 사용으로 보입니다. N이 작 으면 해시 충돌이 매우 드뭅니다. 따라서 2 * N도 낭비입니다. –
@EricJ. 내 질문을 업데이트했습니다. – gsamaras
"자신을 교육하기 위해"- 크기의 범위를 실험하고 결과를 이해하기 위해 초당 결과 작업을 계획하십시오. –