효율적인 해시 맵 사용

문제

해시 맵을 사용하기위한보다 효율적인 접근법은 무엇입니까?

a) 여러 개의 작은 해시 맵을 사용하십시오

b) 모든 물체를 하나의 거대한 해시 맵에 보관합니까?

(키에 대한 해싱 알고리즘이 상당히 효율적이라고 가정하여 충돌이 적습니다).

설명 : 옵션 B는 기본 키에 의한 분리를 의미합니다. 즉, 사용할 실제 해시 맵을 결정하기 위해 추가 조회가 필요하지 않습니다. (예를 들어, 조회 키가 영숫자 인 경우 해시 맵 1은 A를 저장하고 Hashmap 2는 B를 저장합니다.)

해결책

확실히 B. 해시 테이블의 장점은 조회 당 평균 비교 수가 크기와 무관하다는 것입니다.

당신이 당신의 맵을 n 개의 작은 해시 맵으로 나누면, 각 조회에 대해 평균적으로 절반을 검색해야합니다. 더 작은 해시 맵이 더 큰 맵과 동일한 하중 계수를 갖는 경우, 총 비교 수를 대략 N/2의 계수로 증가시킵니다.

더 작은 해시 맵에 하중 계수가 더 작은 경우 메모리를 낭비하고 있습니다.

작은 해시 맵 사이에 키를 무작위로 배포한다고 가정하는 것은 모든 것입니다. 키의 일부 함수 (예 : 문자열 접두사)에 따라 배포하면 생성 한 내용은 트리, 일부 응용 프로그램에 효율적입니다 (예 : 웹 양식의 자동 완성.)

다른 팁

이지도는 논리적으로 별개의 장소에 사용됩니까? 예를 들어, 키가 충돌하지 않을 것임을 알기 때문에 사용자, 캐시 된 쿼리 결과, 로거 등이 포함 된 맵이 하나도 없습니다. 그러나 나는 단일 맵을 여러 맵으로 나누지 않을 것입니다.

각각에 대해 하나의 해시 맵을 유지하십시오 논리적 키에서 값으로 매핑.

또한 @Jon의 답변뿐만 아니라 별도의 해시 테이블을 유지하려는 실질적인 이유가있을 수 있습니다.

다른 매핑에 대한 별도의 테이블이있는 경우 각 매핑을 독립적으로 '지우기'할 수 있습니다. 예를 들어 '클리어'를 호출하거나 해당 테이블에 대한 참조를 제거함으로써.

별도의 테이블이 캐시 된 항목에 매핑을 보유하면 다른 전략을 사용하여 각 항목을 '연령'할 수 있습니다.

응용 프로그램이 다중 스레드 인 경우 별도의 테이블을 사용하면 잠금 경합이 줄어들 수 있으며 (일부 프로세서 아키텍처의 경우) 프로세서 메모리 캐시 적중률을 높일 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow