1. 선형 조사법
해쉬함수가 %7이면 9와 2는 충돌이 일어난다.
이 때, 충돌이 일어난 데이터는 그 옆칸의 저장을 한다는 것이 바로 선형 조사법이다.
이는 교과서적인 방법이고 특정 영역에 데이터가 몰리는 클러스터 현상이 발생하여 사용하지 않는다.
즉, 이는 클러스터 현상이 가져오는 문제점을 언급하기 위한 예시고 실재로 활용하지는 않는다.
(내 생각 : 그리고 3이 저장되면 또 2와 충돌되는데 이 역시 굉장히 큰 문제 아닌가?)
2. 이차 조사법
이차 조사법 : f(k) + n^2
클러스터 방법을 확실하게 피할 수 있는 방법은 아니나 좀 더 개선할 수 있는 방법이다.
여기서 DELETED status가 따로 필요한 방법을 알아보자.
9가 저장된 후 그다음에 2가 저장되었다고 가정하자.
그리고 9가 삭제되었을 때, 2를 찾으려고 인덱스가 2인 곳을 찾아갔을 때, 비어있다고 2는 저장이 안 되어있다고 해선 안된다.
즉 아무것도 저장이 안된 상태와 기존에 저장이 됐으나 현재는 비어있는 상태를 구분하여 DELETED일 때는 이차조사법을 이용해 다음 인덱스를 찾아야한다.
이것이 DELETED status가 필요한 이유이다.
그런데 이런 식으로 하면 언젠가는 모든 슬롯이 deleted상태가 될 수 있고, 이러면 좋은 성능을 보장할 수 없다.
3. 체이닝 (닫힌 어드레싱 모델)
위의 것들은 해쉬값이 2인 데이터들이 배열 3번째 칸에 저장되는 등, 해쉬값이 3인 칸이 저장되어야 하는 칸에 다른 해쉬값을 가진 데이터가 이를테면 '침범'할 수 있었다.
이를 열린 어드레싱 모델이라 하는데, 닫힌 어드레싱 모델은 그렇지 않다.
다른 해쉬값을 가진 데이터가 저장되는 칸을 사용하지 않아야 하므로 배열을 2차원의 형태로 선언한다.
또는 각 해쉬값 별로 연결리스트를 구성하여 '체이닝'의 형태를 만들 수도 있다.
4. 체이닝의 구현
내 생각
헤쉬 벨류의 범위만큼 칸을 가지는 1차원 배열을 선언하고
각 배열에 연결리스트의 head를 저장
해당 해쉬 값을 가진 데이터가 들어올 때마다 각 배열에 저장된 연결리스트에 그 데이터를 저장
(malloc을 이용해 node를 만들고 이전 마지막 node의 next에 해당 데이터가 저장된 노드의 주소 저장)
