해시 테이블
- 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이다.
- 서로 다른 두개의 해시코드가 같은 인덱스를 가리킬 수도 있다.
- 서로 다른 두개의 해시코드가 같은 인덱스를 가르키는 경우를 충돌이라고 하는데, 충돌을 해결하기 위한 방법을 Chaining이라고 한다.
- 배열의 각 인덱스에는 키(Key)와 값(Value) 로 이루어진 연결리스트를 선언한다.
- 해시 테이블의 성능은 공간을 팔아 얻어낸 것이다.
- 해시 테이블은 데이터 없는 여유 공간이 있어야 성능을 유지할 수 있다.
(70% ~ 80%의 사용률이 넘어가면 성능의 저하가 온다고한다.)
해시 테이블 구성법
1. Division Method(나눗셈 법)
- 나눗셈법은 입력 값을 테이블의 크기로 나누고, 그 '나머지'를 테이블의 주소로 사용한다.
- KEY = VALUE % 테이블의 크기
특징 :
- 어떤 값이든 테이블의 크기로 나누면 그 나머지는 절대 테이블의 크기를 넘지 않는다.
- 테이블의 크기를 n이라 할때, 0~n-1 사이의 주소를 반환함을 보장.
- 테이블의 크기 n을 소수(Prime Number)로 정하는 것이 좋다고 알려져 있다.
2. Digit Folding(자릿수 접기)
- 숫자의 각 자릿수를 더해 해시 값을 만드는 것.
특징 :
- 문자열을 키로 사용하는 해시 테이블에 특히 잘 어울린다.
- 문자열의 각 요소를 ASCII 코드 번호(0~127)로 바꾸고 이 값을 각각 더하여 접으면 문자열을 해시 테이블 내의 주소로 변환 가능하다.
체이닝 (Chaining)
Open Hashing
- 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 방법
특징:
- 새 데이터를 링크드 리스트의 가장 앞(즉, 헤드의 앞)에 삽입한다.
- 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점을 가짐.
- 삽입의 속도는 빠르나 탐색과 삭제의 속도가 느리다.
Closed Hashing
- 해시 테이블 내의 새로운 주소를 탐사(Probe)하여 충돌된 데이터를 입력하는 방식
- Linear Probing:
현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다. - Quadratic Probing:
해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다. - Double Hashing Probing:
해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.
