hash table collision 관련 질문

안녕하세요. 정명구님

답변이 늦어 죄송합니다ㅜ

바로 답변 드릴게요!

클러스터링이 발생하는 이유
"인", "프", "런" ,"질", "문", "하", "기" 라는 7개의 key가 있다고 할게요. 이들은 hash table에 저장하기 위해 hash function을 사용하여 해시값으로 index값을 결정해야하는데, 우연히 모두 3이라는 값이 나왔다고 가정해 볼게요.
hashfunction("인") => 3
hashfunction("프") => 3
hashfunction("런") => 3
hashfunction("질") => 3
hashfunction("문") => 3
hashfunction("하") => 3
hashfunction("기") => 3

"인"이 먼저 3을 차지했다면 "프", "런" ,"질", "문", "하", "기" "입장에서는 collision이 발생했으니, linear probing으로 collision을 해결하기 위해 해시값에 +1을 각자 해줬다고 해볼게요
hashfunction("프") => 4
hashfunction("런") => 4
hashfunction("질") => 4
hashfunction("문") => 4
hashfunction("하") => 4
hashfunction("기") => 4
이번엔 "프"가 먼저 4를 차지했으니 나머지 "런" ,"질", "문", "하", "기"가 또 collision이 발생했죠. 이렇게 한번 충돌이 난 key값들은 linear probing이든, quadratic probing이든 계속 겹치게 돼요. 즉 이동폭이 같으면 계속 같이 충돌할 수 있죠. 이것을 clustering이 발생한다고 말합니다!
모든 방식에는 장단점이 존재하죠!
각 언어가 해당 방식을 채택한 정확한 이유를 알 수는 없지만, seperate chaining의 장점을 명확히 알려드릴 수 있습니다. seperate chaining의 경우 Linked List를 이용해서 추가적인 메모리를 사용해야 하지만, 그만큼 초기 hashtable의 크기를 작게 잡을 수 도 있고, 메모리를 좀 더 효율적으로 사용할 수 있어요. 예를 들면 내가 hash table에 저장할 데이터의 갯수가 100개인데, 초기 hashtable의 크기를 30으로 잡으면 open addressing의 경우에는 더 큰 hash table를 다시 선언해서 일일이 옮겨야 될 수 있어요. 그렇다고 hashtable의 크기를 마냥 크게 잡았다가 데이터가 얼마 들어오지 않으면 그것도 낭패죠!
하지만 sepearte chaining의 경우에는 초기 hashtable의 크기를 30으로 잡았는데, 100개의 데이터가 들어와도 끄떡 없어요. linked list로 연결만 해주면 되거든요. 단적인 예지만 이런 장점도 있답니다.
그리고 seperate chaning의 worst case는 실제에선 거의 발생하지 않는다고 보시면 돼요! 일단 hashfunction을 잘 설계하면 collision이 한 곳에서만 발생하는 경우는 가능성이 극도로 낮아져요. 특히 언어에서 사용하는 hash function은 더더욱 clustering이 발생하지 않도록 randomic hash value를 반환하도록 설계되어 있습니다.

혹시 조금 해결이 됐을까요?

더 궁금한 점이 있다면 얼만든지 질문 남겨주세요! 감사합니다.

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