channing_method
앞선 Channing 에서는 한 인덱스에 같은 hash 값이 있는 key-value 쌍이 저장 됬을 경우 병렬형태로 데이터를 저장해서 충돌을 막아줬었다.
open addressing
open addressing은 channing 과 달리 비어있는 인덱스를 찾아서 그곳에 데이터를 저장함으로써 데이터 충돌을 막아주는 개념
linear probing (선형탐사)
그럼 비어있는 인덱스를 어떻게 알고 찾을까? 라는 의문이 생기는데 여기서 linear probing (선형탐사) 방법을 사용할 수 있다.
즉 충돌이 일어났을 때 인덱스를 하나씩 선형적으로 찾는 방법
quadratic probing (제곱탐사)
특정 값을 저장하려고 하는데 해시 함수의 결과가 10이 나왔다고 합시다. 인덱스 10에는 이미 데이터가 저장됐습니다.
선형 탐사를 이용했을 때는 인덱스 11을 확인하고, 인덱스 11은 차 있으니까 인덱스 12를 확인하고 이런 식으로 해서 빈 인덱스를 찾았는데요. 제곱 탐사는 처음에 1의 제곱 뒤에 있는 인덱스를 확인합니다.
1의 제곱은 1이니까 인덱스 11을 확인합니다. 인덱스 11은 차 있습니다.
그다음에는 인덱스 11에서 2의 제곱 뒤에 있는 인덱스를 확인합니다. 2의 제곱은 4입니다. 인덱스 15를 확인합니다. 인덱스 15도 차 있습니다.
그다음은 인덱스 15에서 3의 제곱 밑에 있는 인덱스를 확인합니다. 인덱스 24입니다. 인덱스 24는 비어 있습니다. 여기에 새로운 key - value 쌍 데이터를 저장합니다.
제곱 탐사는 이런 방식으로 선형적으로 바로 다음 인덱스들을 하나씩 확인하지 않고, 제곱을 한 값들을 이용해서 인덱스를 찾습니다.
-
인덱스를 하나씩 선형적으로 찾는 방법 은 linear probing
-
quadratic probing 은 hash값이 10인 인덱스에서 시작하여
1의 제곱 = 10 + 1 = 11
11 + 22 = 15
15 + 33 = 24
24 + 4**4 = 50
이런식으로 데이터를 인덱스 값에 저장해준다.
