알고리즘 5 해시 테이블

해시테이블

- 데이터의 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘 

 

예 ) 

엄청 크기가 큰 배열 -> 주소 다수 / 

특정 데이터를 조회하는 시나리오에서

-> 통상적으로, 순차탐색 / 이진탐색 등 사용 -> 시간 오래 걸림

조회하고자 하는 데이터를 해시함수를 통해 바로 테이블 내 주소값으로 그라운딩

 

ex) 

123817을 조회하고자 할 때, 

123817 해싱 -> 3819 얻음

해시테이블 Table[3819] = 123817

 

해시함수 

나눗셈법 ; 주소 = 입력값 % 테이블 크기 -> 테이블 안의 범위에 그라운딩 되는 걸 보장 

자릿수접기 ; 숫자의 각 자릿수를 더해 해시값을 만드는 것 

 - 한계 : 나머지 값이 같은 경우, 충돌이 일어날 가능성 

 - 클러스터링 ; 일부 지역 주소들을 집중적으로 반환하여 한 곳에 뭉치는 현상

 

충돌해결기법

- 개방 해싱 ; 해시 에이블 주소 바깥에 새로운 공간 할당

- 폐쇄 해싱 ; 해시 테이블 주소 안에서 문제를 해결 

체이닝 ; 충돌 발생 시, 각 데이터를 해당 주소의 링크드 리스트에 삽입 

개방주소법 ; 충돌 시, 다른 주소를 사용할 수 있도록 허용하는 기법 

 -> 1차 클러스터/ 2차 클러스터를 유발하여, 클러스터링 되는 문제 있음 

 -> 이중 해싱 기법 ; 개방주소법에서 충돌 발생했을 경우, 이동거리를 해시 함수로 게산하는 법

재해싱 ; 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블 크기에 맞춰 모든 데이터 재해싱 

 

해시테이블의 성능저하

- 일반적으로 70-80%에 이르면 성능 저하가 일어남 

 

 

GitHub - Sukmin-LanternK/HashTable