인프런 커뮤니티 질문&답변

내용이 길어져서 설명하지 못해서 아쉬웠는데, 좋은 질문 남겨주셨네요!!

답은 '빈공간이 나올 때까지' or '원하는 key값을 찾을 때 까지' 계속 해싱값만큼 건너 뛰면서 살펴보는 것입니다.

(key, value)

(1, one)

(3, three)

(7, seven)

이중해시를 사용한 해시테이블에 위의 순서로 데이터를 저장해볼게요.

해시테이블에 (1, one)를 저장하는 과정 :

key값 1 -> 1차_hash_function(1) = 5

---------------------

index  key  value

0

1

2

3

4

5           1       one

6

---------------------

해시테이블에 (3, three)를 저장하는 과정 :

1차_hash_function(3) = 0

해시값으로 0이 나왔으니 0번 index에 저장해볼게요

---------------------

index  key  value

0           0       three

1

2 

3

4

5           1       one

6

---------------------

해시테이블에 (7, seven)를 저장하는 과정 :

key값 7 -> 1차_hash_function(7) = 5

해시값이 5가 나와서 충돌이 발생하게 됩니다. 그래서 2차 해시값, 2차_hash_function(7) = 2 만큼 건너뛰어 저장을 하려고합니다. index 5에서 2를 건너뛰니 index 0이 나오네요. 우연히도 또 충돌이 발생했네요. 그러면 또 다시 2만큼 건너 뛰어 index 2에 저장을 하게 됩니다.

---------------------

index  key  value

0           0       three

1

2           7       seven

3

4

5           1       one

6

---------------------

이제 저희는 key값 7을 가진 데이터를 찾고자 합니다. 그 과정은 다음과 같습니다.

key 7 -> 1차_hash_function(7) = 5

index 5에 가봅니다. key값을 대조해보니, key 1이 저장되어 있네요. 그렇다면 둘중에 하나입니다. key 7은 충돌로 인해 다른 곳에 저장되어 있거나, 해시테이블에 저장되어 있지 않거나 입니다. (우리는 저장되어있는걸 알지만, 컴퓨터 입장에서는 모릅니다.)

그럼 이번엔 다음 index로 가봅니다. 2차 해시값인 2차_hash_function(7) = 2만큼 건너 뛰어서 탐색을 해봅니다. index 5에서 2칸 건너뛴 곳은 index 0입니다. 이곳에도 key 3이 있을 뿐, key 7은 없네요. 또 한번 2만큼 건너 뛰어 index 2를 탐색해봅니다. key 7이 저장되어 있군요!! 이런식으로 찾게 됩니다.

추가적으로 key 9가 저장되어있는지 살펴볼까요? 

key 9의 1차 해시값은 0이고, 2차 해시값은 2가 나왔습니다. 

1차 해시값이 0이기 때문에 index 0을 탐색해봅니다. key 3이 저장되어있네요. 충돌이 되어 다른곳에 저장되어있거나 (9, nine)은 해시테이블에 저장되어 있지 않을 수 있겠네요. 아직 불확실하기 때문에 2차 해시값인 2만큼 건너 뛰어 봅니다. 

index 0 에서 index 2로 가보니까 key 7이 저장되어 있네요. 여기에도 없으니 2만큼 더 건너뛰어볼까요?

index 2에서 index 4로 왔는데, 아무 데이터도 없어요. 이 경우엔 key 9 이 저장되어 있지 않은 것을 확신할 수 있게 된겁니다. 

장황하게 설명드렸는데 이해 되셨나요?? 초반에 말씀드렸듯이 '빈공간이 나올 때까지 (저장되어 있지 않다는 뜻)' or '원하는 key값을 찾을 때 까지' 계속 해싱값만큼 건너 뛰면서 살펴보는 것입니다. 

혹시 더 궁금하신 점이나 이해가 되지 않는 점 있으시면 말씀해주세요 :)