해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다.
이를 충돌(collision)이라고 부른다.
충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다.
double hashing은 선형 프로빙의 문제를 부분적으로는 해결해준다.
아래의 글에서 선형프로빙의 단점(문제점)을 확인할 수 있다.
2021.12.21 - [알고리즘] - [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing)
더블 해슁은 두개의 hash function을 사용하는 것이다. 하나는 처음에 key를 저장할 index를 찾기 위한 것이고, 나머지 하나는 충돌 발생 시 저장할 index를 찾기 위한 것이다.
충돌 발생 시 저장할 index를 찾기 위한 hash function은 첫번째 hash function과 달라야 하고, hash function을 수행한 결과값이 0이 되면 안된다.
[이것이 코딩테스트다 with 파이썬] 그리디 (0) | 2023.02.21 |
---|---|
[알고리즘] 백준 2667번: 단지번호붙이기 (c언어) (0) | 2022.07.02 |
[알고리즘] 해쉬 테이블(hash table) - Quadratic Probing (0) | 2022.06.24 |
[알고리즘] 해쉬 테이블(hash table) - 오버플로 체인(overflow chaining) (0) | 2022.06.16 |
[알고리즘] 넓이 우선 탐색 (BFS) (1) | 2021.12.27 |
댓글 영역