해시 테이블

해시(Hash): 데이터를 입력받아 완전히 다른 모습의 데이터로 바꾸는 작업.

 

해시 테이블: 데이터의 해시 값을 테이블 내 주소로 이용하는 탐색 알고리즘으로 성능이 뛰어남.

데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력받은 데이터를 해싱해 테이블 내 주소를 계산하고

이 주소에 데이터를 담는 것.

해시테이블은 여유공간이 많아야 성능을 유지함. 해시테이블의 엄청난 성능은 여유공간을 팔아 시간을 사는 방식.

 

해시 함수: 입력 값에서 테이블 내의 주소를 계산.

나눗셈 법: 입력 값을 테이블의 크기로 나누고 나머지를 테이블의 주소로 사용.

주소 = 입력값 % 테이블의 크기

어떤 값이든 테이블의 크기로 나누면 나머지는 테이블의 크기를 절대 넘지 않는다.

나눗셈 법은 테이블의 크기가 n일 때 0부터 n-1 사이의 주소 반환을 보장한다.

효율을 위해선 n을 소수(1과 자신만을 약수로 가지는 수)로 정하는 것이 좋고 특히 2의 제곱수와 거리가 먼 소수를 사용하는

해시함수가 좋은 성능을 낸다. 

 

충돌: 서로 다른 입력값에 대해 동일한 해시값, 해시 테이블 내의 동일한 주소를 반환하는 문제, 해시 함수를 쓰는 한 충돌을 피할 수 없다.

클러스터: 똑같은 해시 값이 아니더라도 해시 테이블 내 일부 지역의 주소들을 집중적으로 반환하여 데이터가 한 곳에 모이는 문제.

 

자릿수 접기: 숫자의 각 자릿수를 더해 해시 값을 만드는 것으로 문자열을 키로 사용하는 해시테이블에 잘 어울리는 알고리즘.

문자열의 각 요소를  ASCII코드로 변환 후 값들을 각각 더해서 접으면 해시테이블의 주소로 바꿀 수 있기 때문.

 

 

충돌해결 기법

개방해싱: 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 것.

폐쇄해싱: 처음에 주어진 해시테이블의 공간 안에서 문제를 해결하는 것.

 

체이닝: 개방해싱에 해당하는 방식이고 해시 함수가 서로 다른 키에 대해 같은 주소 값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입해 문제를 해결하는 기법 체이닝 기반 해시 테이블은 데이터 대신 링크드 리스트에 대한 포인터를 관리. 충돌이 일어날 때마다 데이터를 링크드리스트에 사슬처럼 주렁주렁 엮는다는 의미에서 체이싱이라고 부름.

 

탐색연산: 발생할 충돌을 고려해서 설계되어야 함

탐색순서

1) 찾고자 하는 목푯값을 해싱해 링크드 리스트가 저장된 주소를 찾는다

2) 이 주소를 이용해 해시테이블에 저장된 링크드 리스트에 포인터 생성.

3) 링크드 리스트 앞에서부터 뒤까지 차례대로 이동하며 목푯값이 저장되어 있는지 비교.

목표 값과 링크드 리스트 내의 노드 값이 일치하면 해당 노드 주소 반환

 

삽입 연산: 해시 함수를 이용해 데이터가 삽입될 링크드 리스트의 주소를 얻어낸 후, 

링크드 리스트가 비어있으면 데이터를 바로 삽입하고 그렇지 않다면 리스트의 헤드 앞에 삽입.

헤드 앞에 넣으면 순차 탐색을 할 필요가 없고 해시테이블의 성능이 저하되는 일도 없기 때문.

 

체이닝의 성능 향상: 링크드리스트의 단점을 물려받기 때문에 레드 블랙트리와 같은 이진 탐색트리를 사용하면 성능 향상 가능.

 

 

개방 주소법: 폐쇄 해싱으로 충돌 발생 시 해시 함수에 만들어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘. 충돌이 일어나면 새로운 주소를 탐사하여 충돌된 데이터를 입력하는 방식으로 동작한다.

 

선형탐사: 해시 함수로 얻어낸 주소에 다른 데이터가 있다면 현재 주소에서 고정폭으로 주소를 이동. 그 주소에도 있다면 또

이동.... 비어있는 곳에 데이터를 입력하는 방식. 선형탐사를 진행하다 보면 충돌할뻔한 데이터들이 한 곳에 모이는 클러스터 현상이 많이 발생함.

 

제곱탐사: 선형탐사에서는 고정폭만큼 이동하던 것이 이동폭이 제곱수로 늘어나는 부분이 다르다. 나머지 방식은 동일.

선형탐사와는 다른 모습이지만 역시 클러스터가 발생하는데 이는 하나의 주소에서 충돌이 발생 시 탐사할 위치가 정해져서 문제가 생김.

 

이중해싱: 탐사할 주소의 규칙성을 없애는 것이 클러스터 방지법임. 2개의 해시함수를 준비하여 하나는 주소를 얻을 때,

하나는 충돌이 일어날 때 탐사 이동폭을 얻기 위해  사용. 테이블의 끝을 넘어가는 경우 처음으로 돌아간다.

 

재해싱: 남은 공간이 거의 없는 테이블에서는 연쇄충돌 발생하는데 이 문제를 해결하는 것이 재해싱이다.

해시 테이블의 크기를 늘리고 늘어난 테이블의 크기에 맞춰 테이블 내 모든 데이터를 다시 해싱하는 것.

이렇게 하면 다시 여유 공간이 생긴다.

테이블 사용률이 70~80%일 때 성능에 저하가 생김.