정의
Hashing은 입력값을 해시 함수를 활용하여 고정된 크기의 문자열을 출력하는 과정을 말한다.
요약: 키를 해시함수로 암호화한 것
키에 대한 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라고 부름.
그리고 해시 테이블을 활용해서 값을 찾는 것을 해싱이라고 함.
충돌 (conflict)
다른 키를 가진 항목이 같은 해시주소를 가르키는 현상을 말함.
오버플로우 (overflow)
해시 주소에 더 이상 빈 버킷(공간)이 남지 않으면 발생함.
오버플로우는 충돌이 발생하고, 오버플로우가 발생하면 해시테이블에 항목을 저장하는 것이 성립이 안됨.
다 갈아 엎어짐
계량 주소법 (open addressing)
현재 사용되고 있지 않은 공간을 찾아 저장하는 방법이다.
충돌이 났을 때 대처하는 방법에 따라 4가지로 나뉜다.
1. 선형 조사법 (linear probing)
선형 조사법은 충돌이 났을 때 다음 거, 다음 거 이런식으로 순차적으로 확인하는 방법이다.
하지만, 이 방식을 사용하면 Clustering 문제(한 번 충돌 시작 시 계속 충돌이 집중되는 현상)에 빠진다.
2. 이차 조사법 (quadratic probing)
이차 조사법은 + n^2 만큼 더 해서 탐색하는 방법이다.
1, 4, 9, 16 만큼씩 계속 늘어난다.
3. 이중 해싱법 (double hashing)
이중 해싱법이 조사되는 위치는 해싱함수를 한번 더 검색해서 검색한다. h라는 해싱함수와 h'라는 해싱함수를 동시에 사용하는 것이다.
이 방법을 사용하면 클러스터링 문제가 덜 발생할 수 있다.
4. 체인법 (chaining)
이 방법은 연결 리스트(Linked List)로 해시 주소마다 존재하면 그 노드에 맨 끝에 위치하게 한다.
아니면, 그 노드 자체를 리스트 타입으로 만들어서 해결하는 방법도 있다.
이 방법을 사용하면 클러스터링 문제가 생기지 않게 된다.
