해시테이블
- key와 value구조로 이루어져 있는 자료구조
- key를 해시함수를 이용해서 index로 바꾸고 해당 index를 주소로 사용
해시함수
1. digit folding : key의 문자열을 ASCII 코드로 바꾸고 그 합을 index로 사용
2. division method : 숫자 key를 테이블의 크기로 나누어 나온 나머지를 index로 사용 (index = key % 테이블 크기)
* 테이블의 크기는 소수(prime number)
3. multiplication method : 숫자로 된 key 값에 A(0~1사이 실수)를 곱한 후 그 나머지에 2의 제곱수 m을 곱하는것을 index로 사용 (index = (K*A mod 1)*m)
충돌 회피
- 해시함수를 이용해 구한 index가 중복됐을때 이를 회피하는 방법
1. 분리 연결법(separate chaining)
동일한 value혹은 buckets에 대해서 연결 리스트, 트리 등의 자료구조를 활용하여 데이터를 저장하는것
테이블의 확장이 필요없지만 동일한 버킷에 chaining 되는 데이터가 많아지면 효율성이 감소한다
2. 개방 주소법(open addressing)
테이블의 공간을 활용하는 방법(다른 index로 이동하는 방법)
다음과 같은 종류가 있음
2.1 linear probing : 현재 버킷 index로 부터 고정폭 만큼 이동하여 비어있으면 저장. 한번 충돌이 발생하면 그 주변에 계속 해서 데이터가 쌓이는 군집화 문제가 발생할 수 있음
2.2 quadratic probing : 제곱수만큼 이동하는것(1^2, 2^2, 3^2, 4^2...)
2.3 double hasing probing : 해시된 값을 한 번 더 해싱하는 방식. 기존 방식보다 더 많은 연산 필요