해시 테이블

해시 테이블

해시

• 해시 : 데이터를 새로운 형태의 데이터로 바꿈
• 해시 테이블 : 데이터의 해시 값을 테이블 내의 주소로 이용
• 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있음

나눗셈법

• 해시 함수가 테이블 크기로 키값을 나눈 나머지를 반환
• 나눗셈법으로 구현된 해시 함수가 테이블 내의 공간을 효율적으로 사용하기 위해서는 테이블의 크기를 2의 제곱수와 거리가 먼 소수로 지정 하는 것이 좋음

자릿수 접기

• 숫자 자릴를

충돌과 클러스터 (Collision, Cluster)

• 충돌 : 키 값이 다른 두 자료에 대해 해시 함수가 같은 해시 값을 낼 때
• 클러스터 : 해시 테이블 내의 일부 지역에 데이터가 모이는 문제

충돌 해결법

체이닝

• 충돌이 일어날 때 데이터를 해당 주소에 있는 링크드 리스트에 삽입
• 해시 테이블의 주소 바깥에 새로운 공간을 할당 → 개방 해싱
• 해시 함수에 의해 얻어진 주소만 사용 → 폐쇄 주소법
• 링크드 리스트를 이진 탐색 트리로 만들면 체이닝의 성능을 더 끌어올릴 수 있음

개방 주소법

• 충돌이 일어날 때 다른 비어있는 주소를 사용하는 것을 허용 → 개방 주소법
• 선형 탐사 : 충돌이 일어났을 때 선형적으로 빈 공간을 탐사 → 클러스터 유발 가능
• 제곱 탐사 : 클러스터를 방지하기 위해 탐사 폭이 제곱수만큼 늘어남 →같은 해시 값을 갖는 데이터에 대해 2차 클러스터를 막아주지 못함
• 이중 해싱 : 탐사 폭 또한 해시 함수를 통해 주소의 규칙성을 제거
• 재해싱 : 해시 테이블의 크기를 늘리고 늘어난 테이블 크기에 맞춰서 모든 데이터를 재해싱(통계적으로 공간 사용률 70%~ 80%에 재해싱 권장)