[C++] Hash

 

해시 코드 ( HashCode )

객체를 식별하는 정수 값(Key)이다

 

Key	Data
...
6	203
7	15

 

객체의 주소 값을 변환하여 생성한다

객체를 비교할 때 드는 비용을 낮추기 위해 사용한다 

HaspMap에서 HashCode를 이용하여 객체를 매핑하며 객체를 찾을 때 사용한다

 

HashCode가 다르면 두 객체는 다르다

HashCode가 같으면 두 객체는 같거나 다르다

equals()로 비교해서 true면 같고 false면 다르다

 

 

 

---

Hash의 충돌

 

• Key값이 같을 경우

해결법은 개방주소법과 체이닝이 있다

 

 

• 개방주소법(Open Addressing)

충돌이 발생한 인덱스를 건너뛰고 빈공간이 있는지 탐색 후 삽입한다.

인덱스를 증가시켜주는 안정적 방식

체이닝과 달리 포인터가 필요 없고, 추가적인 메모리가 불필요하다삽입/삭제시 오버헤드가 적다

 

 

비어있는 인덱스를 탐색하는 방법에는 

선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing)이 있다

 

선형 탐사 : n개의 인덱스를 건너 뛰고 데이터를 삽입한다

                    -> Cluster현상 (value가 특정 부분에 밀집되는 현상) 이 발생할 수 있다

제곱 탐사 : n^2개의 인덱스를 건너 뛰고 데이터를 삽입한다

                    -> 2차 Cluter현상 발생할 수 있다

이중 해싱 : 해시 함수를 하나 더 사용하여 증가폭을 구한다

 

 

• 체이닝(Chaining)

충돌이 일어난 지점에 연결리스트로 묶어서 사용한다.

정해진 해시테이블 이외의 주소를 추가로 할당, 확장해서 사용하는 방식

개방주소법에 비해 복잡한 계산식의 필요성이 적다

 

 

 

 

해시 충돌을 최소화 하는 법

 

잘 만들어진 해시 함수를 사용한다

해시 테이블의 크기를 소수로 설계한다

해시 테이블의 크기를 크게 만든다