해시 키 유형을 선택하는 데 이론적 근거가 있습니다.

Question

남자, 저는 25 개의 다른 키 (정수)와 값을 가진 데이터 구조를 가지고 있습니다. 나는이 객체들 (50000)의 목록을 가지고 있고 그것들을 저장/검색하기 위해 해쉬 테이블을 사용할 계획이다. 나는 이러한 접근법 중 하나를 취할 계획이다.

1. 이러한 25 개의 정수 키에서 정수 해시를 만들어 해시 테이블에 저장합니다. (예! 충돌을 처리 할 수있는 방법이 있습니다.)

2. 개별 키에 문자열 연결을 만들어 해시 테이블의 해시 키로 사용합니다. 예를 들어 키 값이 1,2,4,6,7이면 해시 키는 "12467"입니다.

나는 50000 총 25 별개의 키와 값을 각각 기록했다고 가정하고,이 문자열은 검색 할 필요 비교와 삽입의 비용에 관해서 다음 내 두 번째 방법은 과잉 될 것입니다 기록?

몇 가지 추가 정보!

1. 해시 테이블의 각 버킷은 균형 잡힌 이진 트리입니다.
2. 나는 부스트 라이브러리의 hash_combine 메서드를 사용하여 25 개의 키로부터 해시를 생성하고있다.

Answer 1

두 번째 방법을 사용하는 경우 1x10^(25m), where x is the maximum length of a key 개의 슬롯을 사용할 수있는 해시 테이블이 필요하므로 절대적으로 첫 번째 방법을 사용하십시오.

예를 들어 키의 최대 수는 9999이고 m은 4가되고 테이블에 1x10^100 슬롯이 필요합니다.

---

설명 :

해시 테이블 뒤에 아이디어는 모든 요소의 해시 이 위치 가리키고 있기 때문에 당신이 무작위로 (옆으로 충돌) O (1)의 효율 어떤 요소에 액세스 할 수 있다는 것입니다 해시 테이블에 있습니다. 예를 들어, Object X를 해시하고 24의 해시가 반환되거나 (24로 밝혀지는 숫자로 변환 된 일부 문자열 해시), 나는 단순히 내 테이블의 슬롯 24로 이동합니다. 배열)을 검색 할 수 있으며 Object X를 검색 할 수 있습니다.

두 번째 방법을 사용하는 경우 (해시를 만들기 위해 25 개의 숫자를 연결하면 여기에서 항목을 단순화하기 위해 숫자를 연결 함) 가장 큰 해시는 99999999999999999999999가됩니다. 따라서 해시 테이블에서 해당 개체를 검색하려면 9999999999999999999999999 위치에서 개체를 검색해야합니다. 즉, 테이블에 적어도 그 많은 지점이 있어야합니다.

---

첫 번째로는 이진 트리를 사용하고 있으므로 충돌은 실제로 큰 차이가되지 않습니다. 최악의 시나리오는 O (log (n))의 검색/삽입 효율성이 될 것이며, 실제로 그렇게 나쁘지는 않습니다.