[CS] 해시(Hash)와 해시 충돌 해결 방법

mark340 2023. 1. 28. 01:32

데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑

해시 함수: 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다.
해시 테이블: 키와 값을 매핑해둔 데이터 구조이다. 해시 함수로 얻은 해시를 키로 활용하여 index로 사용하고 해당 index에 데이터를 저장하여 효율적인 검색을 위해 사용된다.

해시 순서

추상 자료형 사전구조

해싱의 구조

어떤 항목의 탐색 키만을 가지고 바로 항목이 저장되있는 배열의 인덱스를 결정하는 기법
탐색키를 작은 정수로 매핑 시키는 함수가 필요
예를들어 영어사전에서는 단어가 탐색키가 되고 이 단어를 해싱 함수를 이용하여 적절한 정수 i로 변환한 다음, 배열 요소 ht[i]에 단어의 정의를 저장하는 것

해시 테이블의 구조

해시테이블은 n개의 버킷으로 이루어지는 테이블로서 n-1개의 원소를 가진다.
하나의 버킷은 s개의 슬롯을 가질 수있으며, 하나의 슬롯에는 하나의 항목이 저장됨
하나의 버킷에 여러개의 슬롯을 두는 이유 - 서로 다른 두 개의 키가 해시 함수에 의해 동일한 해시 주소로 변활 될 수 있으므로 여러 개의 항목을 동일한 버킷에 저장하기 위함

버킷과 슬롯

버킷
- 여러개의 슬롯을저장하는 레코드 형태의 자료 구조
- 버킷의 갯수는 고정적

슬롯
- 해시와 매핑되는 값이 저장되어 있는 공간
- 하나의 버킷 안에는 여러개의 슬롯이 존재할 수 있음
- 슬롯은 하나이상의 값을 저장할 수 있음

해시 테이블이 사용되는 이유

실제의 해싱

다른 내용의 데이터가 같은 키를 갖는 상황.
같은 키 값을 가지는 데이터가 생기는 것은 특정 키의 버켓에 데이터가 집중된다는 뜻. 너무 많은 해시 충돌은 해시 테이블의 성능을 떨어뜨린다.

해시함수의 입력값은 무한하지만 출력값의 가짓수는 유한하므로 해시충돌은 반드시 발생 (*비둘기집 원리)
클러스터링(Clustering) : 연속된 레코드에 데이터가 몰리는 현상
오버플로우(Overflow) : 해시 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하면 더 이상 버킷에 값을 넣을 수 없는 현상

*비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 존재

1. 체이닝

2. 개방 주소법

해시 충돌이 일어나면 다른 버킷에 데이터를 삽입하는 방식 (데이터의 주소값이 바뀜)
삭제의 경우 충돌에 의해 저장된 데이터가 검색되지 않을 수 있음
=> 삭제한 위치에 더미노드를 삽입 (다음 위치까지 연결 해 주는 역할)
더미 노드가 많아지면 버킷을 연속적으로 검색해야 하기 때문에
더미 노드의 개수가 일정 이상이 되었을경우 주기적으로 새로운 배열을 만들어 재해시를 해줘야 성능을 유지 가능

2.1 선형 탐색

해시 충돌시 다음 버킷, 혹은 몇 개를 건너뛰어 데이터를 삽입
장점 : 구조가 간단하고 캐시의 효율이 높음
단점 : 최악의 경우 해시테이블 전체를 검색해야 하는 상황이 발생, 데이터의 클러스터링에 가장 취약

2.2 2차 검색법

2.3 이중 해시