인프런 커뮤니티 질문&답변
작성한 질문수
해쉬 충돌에 대해 질문드리고 싶습니다.
해결된 질문
작성
·
315
0
해쉬 충돌에 대해서 제대로 이해하고 싶어서 다른 자료를 찾아보다가 이해가 안되는 부분이 있어서 질문드립니다.
전제 : Key값은 상수 데이터이다.
그림 설명만 놓고 보면
키값이 달라도 해쉬 버켓 값이 동일해서
해쉬 충돌이 일어날 수 있다
라고 설명하는 것 같은데, 서로 다른 키가 같은 해쉬 버켓에 매핑 될 수 있는 경우가 해쉬 함수의 성능에 의해 결정되는지 궁금합니다.
더불어 대체적으로 어떤 경우에서 해쉬 충돌이 빈번한지에 대해 질문 드리고 싶습니다.
답변 1
0
무디
질문자
어느정도는 이해 한거 같습니다!
질문 게시글을 작성을 한 이후 스스로 곰곰히 생각을 해보고 분석을 해보았습니다.
1. 해쉬 테이블에서 키를 해쉬 함수에 입력하면 해쉬 값(또는 해쉬 코드)가 반환됨2. 해쉬 값은 해쉬 테이블의 인덱스로 사용되어 값을 저장하거나 검색 3. 그러나 해쉬 함수의 특성상 서로 다른 키가 동일한 해쉬 값을 생성할 수 있다!
해쉬 충돌의 예시
간단한 해쉬 함수가 "키를 10으로 나눈 나머지"라고 가정
이 경우, 키가 15와 25인 두 데이터는 동일한 해쉬 값(즉, 5)을 가진다.
따라서 이 두 데이터는 해쉬 테이블에서 동일한 위치(또는 버켓)에 저장되어야 한다.
이런 상황에서 해쉬 충돌 해결 방법(예: 체이닝, 오픈 어드레싱 등)을 사용하여 충돌을 처리
해쉬 함수 : key % 10
키 값: 15, 25
해쉬 값: 15 % 10 = 5, 25 % 10 = 5
해쉬 테이블:
+-------+-------+
| 인덱스 | 값 |
+-------+-------+
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | 15,25 |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
+-------+-------+
키 값 '15'와 '25'는 동일한 해쉬 값 '5'를 가지므로 해쉬 테이블의 인덱스 '5' 위치에 저장
체이닝 방식을 사용하여 인덱스 5의 위치에 연결 리스트로 15와 25를 저장할 수 있다.혹시 이해가 틀린 부분이 있다면 가르침을 주시면 성실히 공부하겠습니다.
네 이해하신 것이 맞습니다.
해쉬 알고리즘이 결국
- 최대한 빨리 실행되면서
- 최소한으로 겹치면
가장 이상적이겠죠!
그런데 어차피 메모리를 더 많이 내주면 충돌도 많이 완화되어 O(1)이라고 가정해도 무방합니다.
현실에선 1억이 넘는 데이터량을 사용할 일은 거의 없기 때문이죠.