해쉬 충돌에 대해 질문드리고 싶습니다.
해쉬 충돌에 대해서 제대로 이해하고 싶어서 다른 자료를 찾아보다가 이해가 안되는 부분이 있어서 질문드립니다.
전제 : Key값은 상수 데이터이다.
그림 설명만 놓고 보면
키값이 달라도 해쉬 버켓 값이 동일해서
해쉬 충돌이 일어날 수 있다
라고 설명하는 것 같은데, 서로 다른 키가 같은 해쉬 버켓에 매핑 될 수 있는 경우가 해쉬 함수의 성능에 의해 결정되는지 궁금합니다.
더불어 대체적으로 어떤 경우에서 해쉬 충돌이 빈번한지에 대해 질문 드리고 싶습니다.
Answer 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를 저장할 수 있다.혹시 이해가 틀린 부분이 있다면 가르침을 주시면 성실히 공부하겠습니다.
1
네 이해하신 것이 맞습니다.
해쉬 알고리즘이 결국
- 최대한 빨리 실행되면서
- 최소한으로 겹치면
가장 이상적이겠죠!
그런데 어차피 메모리를 더 많이 내주면 충돌도 많이 완화되어 O(1)이라고 가정해도 무방합니다.
현실에선 1억이 넘는 데이터량을 사용할 일은 거의 없기 때문이죠.
Generic에 대한 질문 있습니다.
0
95
2
2022 버전에 커뮤니티 버전이 없는데 2026 버전으로 해도 무관?
0
201
2
다형성 캐시 문제
0
112
3
.
0
71
1
프로퍼티 강의 질문 있습니다.
0
78
1
이후 커리 질문
0
86
1
static
0
91
2
강의에는 새로운 클래스 파일을 생성하면...
0
72
1
생성자의 이름 선언
0
65
1
9:03 Divide(10 , 3) 부분 질문입니다
0
88
1
깃허브 관련 질문 있습니다.
0
239
1
비쥬얼 스튜디오 업데이트가 된건가요..? 매개변수 오류 관련 질문
0
249
1
C# 시리즈 || C++ 시리즈 자료구조 강의에 대한 질문입니다!
0
306
2
Activator 질문있습니다
0
332
1
이넘 타임 선언 질문
0
346
1
Sort 오름차순, 내림차순
0
323
1
질문 있습니다.
0
249
1
팩토리얼 문제
0
270
1
Sort함수 질문있습니다.
0
265
1
다형성 함수 질문 있습니다.
0
221
1
질문이 있습니다.
0
226
1
섹션2 연습문제 질문입니다.
0
213
1
안녕하세요~서버에 대해 질문이 있습니다.
1
281
1
텍스트 색깔이 제 편집기와 달라서 수강에 어려움이 있습니다ㅜㅜ
0
393
1