위키원
"해시충돌"의 두 판 사이의 차이
| 1번째 줄: | 1번째 줄: | ||
| + | '''해시충돌'''이란 서로 다른 내용의 데이터가 같은 키를 갖는다는 것을 뜻한다. | ||
| + | ==개요== | ||
| + | 입력값은 다른데 출력값이 같다는 것은 특정 키의 버켓에 데이터가 집중된다는 것을 의미하기 때문에 해시 충돌은 [[해시테이블]]의 성능을 저하시킨다. | ||
| + | [[해시테이블]]에서 사용 가능한 모든 키의 숫자는 [[테이블 인덱스]]의 개수보다 많기 때문에 불가피한 충돌을 야기하고, 그렇기 때문에 해시충돌을 피할 수 있는 [[해시 알고리즘]]은 없다. 이때 [[비둘기집 원리]], [[생일 패러독스]]가 적용된다고 한다. | ||
| + | |||
| + | ===비둘기집 원리=== | ||
| + | [[비둘기집 원리]]란, n+1개의 물건을 n개의 상자에 넣는다고 할 때, 적어도 어느 한 상자에는 두 개 이상의 물건이 있는데, 이 원리를 비둘기집 원리라고 한다. | ||
| + | |||
| + | ===Birthday Paradox=== | ||
| + | [[생일 패러독스]](Birthday Paradox)란 366명의 사람이 모였을 때, 생일이 겹치는 사람이 최소 2명이 넘는다는 것으로, 가짓수를 넘어서는 통계 표본이 존재할 때, 중복되는 값이 필연적으로 발생한다. | ||
| + | |||
| + | ==해시충돌 시, 해시테이블에서의 해결법== | ||
| + | ==='''Open Addressing'''=== | ||
| + | 해시값과 실제 저장된 위치가 다를 수 있으므로 충돌이 발생한다면 다른 인덱스에 저장한다. | ||
| + | * 이중해시(Double hashing) | ||
| + | 기본적으로 사용하는 해시 함수와 별개로 해시 충돌 시 사용할 두 번째 해시 함수를 만들어놓고 조정한다. | ||
| + | * 선형탐사(Linear probing) | ||
| + | 충돌이 일어난 바로 뒷자리를 보거나, 테이블의 경계를 넘어간다면 맨 얖으로 돌아간다. | ||
| + | * 제곱 탐사(Quadratic probing) | ||
| + | 선형 조사와 달리 이차함수를 고려하며 뒷자리를 본다. | ||
| + | |||
| + | ==='''Close Addressing'''=== | ||
| + | 해시값과 실제 저장된 위치가 다를 수 있으나 충돌이 발생해도 해당 위치에 저장한다. | ||
| + | * 버켓 | ||
| + | 배열의 한 요소가 다시 배열이므로 충돌 발생 시 타 위치로 조정 없이 해당 위치에 배열로 쌓는다. | ||
| + | * 체이닝 | ||
| + | 충돌된 값들을 [[linked-list]]로 연결한다. 삽입 시 뒤에 삽입한다면 삽입 시마다 연결 리스트를 따라 뒤로 이동해야 하기 때문에 효율성을 위해 맨 앞에 삽입한다.<ref>kkd927,〈[https://itstory.tk/entry/%ED%95%B4%EC%8A%81%EC%97%90%EC%84%9C%EC%9D%98-%EC%B6%A9%EB%8F%99%ED%95%B4%EA%B2%B0Collision-Resolution 해슁에서의-충동해결]〉, 《it-story》, 2014-06-17</ref><ref>표준입출력,〈[https://stdin2stdout.tistory.com/entry/Q-%ED%95%B4%EC%89%AC-%EC%B6%A9%EB%8F%8C%EC%9D%B4-%EB%AC%B4%EC%97%87%EC%9D%B4%EA%B3%A0-%ED%95%B4%EA%B2%B0%EC%B1%85%EC%9D%84-%EC%95%8C%EA%B3%A0-%EC%9E%88%EB%82%98%EC%9A%94 해쉬 충돌이 무엇이고, 해결책을 알고 있나요?]〉, 《티스토리》, 2014-07-13</ref> | ||
| + | |||
| + | ==참고자료== | ||
| + | |||
| + | ==같이보기== | ||
| + | * [[해시]] | ||
| + | * [[해시맵]] | ||
| + | * [[해시함수]] | ||
| + | * [[해시테이블]] | ||
{{블록체인 기술|토막글}} | {{블록체인 기술|토막글}} | ||
2019년 7월 22일 (월) 17:08 판
해시충돌이란 서로 다른 내용의 데이터가 같은 키를 갖는다는 것을 뜻한다.
목차
개요
입력값은 다른데 출력값이 같다는 것은 특정 키의 버켓에 데이터가 집중된다는 것을 의미하기 때문에 해시 충돌은 해시테이블의 성능을 저하시킨다. 해시테이블에서 사용 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많기 때문에 불가피한 충돌을 야기하고, 그렇기 때문에 해시충돌을 피할 수 있는 해시 알고리즘은 없다. 이때 비둘기집 원리, 생일 패러독스가 적용된다고 한다.
비둘기집 원리
비둘기집 원리란, n+1개의 물건을 n개의 상자에 넣는다고 할 때, 적어도 어느 한 상자에는 두 개 이상의 물건이 있는데, 이 원리를 비둘기집 원리라고 한다.
Birthday Paradox
생일 패러독스(Birthday Paradox)란 366명의 사람이 모였을 때, 생일이 겹치는 사람이 최소 2명이 넘는다는 것으로, 가짓수를 넘어서는 통계 표본이 존재할 때, 중복되는 값이 필연적으로 발생한다.
해시충돌 시, 해시테이블에서의 해결법
Open Addressing
해시값과 실제 저장된 위치가 다를 수 있으므로 충돌이 발생한다면 다른 인덱스에 저장한다.
- 이중해시(Double hashing)
기본적으로 사용하는 해시 함수와 별개로 해시 충돌 시 사용할 두 번째 해시 함수를 만들어놓고 조정한다.
- 선형탐사(Linear probing)
충돌이 일어난 바로 뒷자리를 보거나, 테이블의 경계를 넘어간다면 맨 얖으로 돌아간다.
- 제곱 탐사(Quadratic probing)
선형 조사와 달리 이차함수를 고려하며 뒷자리를 본다.
Close Addressing
해시값과 실제 저장된 위치가 다를 수 있으나 충돌이 발생해도 해당 위치에 저장한다.
- 버켓
배열의 한 요소가 다시 배열이므로 충돌 발생 시 타 위치로 조정 없이 해당 위치에 배열로 쌓는다.
- 체이닝
충돌된 값들을 linked-list로 연결한다. 삽입 시 뒤에 삽입한다면 삽입 시마다 연결 리스트를 따라 뒤로 이동해야 하기 때문에 효율성을 위해 맨 앞에 삽입한다.[1][2]
참고자료
같이보기
- ↑ kkd927,〈해슁에서의-충동해결〉, 《it-story》, 2014-06-17
- ↑ 표준입출력,〈해쉬 충돌이 무엇이고, 해결책을 알고 있나요?〉, 《티스토리》, 2014-07-13
