데이터구조 - (10) 해시 테이블

삽입, 검색, 삭제

배열 또는 연결 리스트는 평균적으로 빅세타 n,

이진 검색 트리는 평균 빅세타 logn,

균형 이진 검색 트리는 최악의 경우 빅세타 logn,

균형 다진 검색 트리는 최악의 경우 빅세타 logn 정도가 걸린다.

​

이것을 더 빠르게 사용하기 위해 해시 테이블을 사용한다.

이는 평균적으로 빅세타 1이 걸린다.

 

해시 테이블

출처 : 쉽게 배우는 자료구조 with 파이썬

검색 키 값을 해시 함수를 통해 해시 테이블에 적재하는 것을 말한다.

검색, 삽입, 삭제에 극한에 달하는 효율을 가진다.

해시 테이블에 적재율이 올라갈수록 충돌 확률이 올라가며, 이는 성능 저하를 의미한다.

충돌은 같은 해시 테이블 자리에 값이 다시 배정되는 것을 말하며 충돌 처리가 해시 테이블에서 중요하다.

출처 : 쉽게 배우는 자료구조 with 파이썬

 

해시 함수

입력 키를 해시 테이블에 고루 분산시켜 저장해야 한다.

해시 함수는 대표적으로 나누기 방법과 곱하기 방법이 있다.

​

 

위와 같이 입력 키 x를 소수인 값 m으로 나누어 해시 테이블에 저장하는 방법이다.

​

곱하기 방법은 0~1 사이의 소수로 대응시킨 다음 해시 테이블 m을 곱하여

0~m-1사이로 팽창시키는 방법이다.

 

충돌 해결

충돌 해결 방법은 체이닝과 개방 주소 방법으로 나뉜다.

개방 주소 방법은 선형 탐색, 이차원 탐색, 더블 해싱으로 다시 나뉜다.

​

- 체이닝 : 충돌이 일어난 원소들은 하나씩의 연결 리스트로 관리하는 방식

출처 : 쉽게 배우는 자료구조 with 파이썬

나누기 방식으로 해시 테이블에 적재하여 만약 충돌이 발생하면

연결 리스트를 사용해 꼬리 물기 식으로 계속 저장하는 방법이다.

이는 적재율이 1을 넘어갈 수 있으나, 추가 메모리를 사용해야 한다.

​

- 개방 주소 방법

체이닝과 달리 추가 공간을 사용하지 않는다.

하지만 모든 키가 반드시 자신의 해싯값과 일치하는 주소에 저장된다는 보장을 할 수 없다.

또한 주어진 공간만을 사용하여 적재율이 1이 넘을 수 없다.

추가로 적재율이 임계점 이상 넘어가면 효율이 떨어져, 이 값을 넘으면 해시 테이블 크기를 2배로 키운다.

테이블 크기가 바뀌면 해시 함수가 바뀌므로 모든 키를 다시 해싱해야 한다.

​

1. 선형 탐색

출처 : 쉽게 배우는 자료구조 with 파이썬

나누기 방식 후에 충돌이 발생하면 바로 뒷자리에 저장하는 방식이다.

하지만 계속해서 뒷자리에 값이 있으면 자리를 찾기 위해 반복해야 한다.

경계를 넘어가면 맨 앞으로 간다.

​

​

​

2. 이차원 탐색

출처 : 쉽게 배우는 자료구조 with 파이썬

이차원 탐색은 선형 탐색과 마찬가지로 뒤에 있는 빈 자리를 찾는데,

그 보폭을 이차 함수로 넓혀서 진행한다.

그렇기에 1차 군집이 생겨도 특정 영역을 빠르게 벗어날 수 있다.

그렇지만 여러 개의 키가 동일한 초기 해시 함숫값을 가지며 모두 같은 순서로 탐색하게 되는

2차 군집 현상이 발생한다.

​

​

3. 더블 해싱

더블 해싱은 2개의 함수를 사용한다.

그렇기에 첫 번째 해시값이 값아도 두 번째 해시값까지 같을 확률은 굉장히 낮기에

서로 다른 보폭으로 찾게 된다. 이 때 사용하는 m값은 해시 테이블의 크기보다

조금 작은 소수를 사용한다.

​

추가로 삭제할 때 주의할 점은 삭제된 자리를 null 값으로 채우면

검색에서 존재하는 원소를 없다고 대답할 수 있다. 그렇기에 지운 자리에 DELETED로 할당 후에

삽입할 때 이를 제거하면 된다.

 

 

해싱의 효율

좋은 해시 함수는 계산이 빨라야 하며, 키들을 모든 영역에 고루 분산시킬 수 있어야 한다.

키가 비슷하다고 더 가까이 놓이면 좋지 않다.

추가로 적재율이 낮을 때는 충돌 해결 방법들은 큰 차이가 없다.

성공적인 검색은 삽입할 당시의 궤적을 그대로 밟는다.