해시 테이블

• 해시 테이블 : 키(Key) + 값(Value) 으로 구성
• 해시 함수(Hash Function) : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수, 해시 함수를 사용하여 구한 Key를 해시라고함.
  ex) 제곱법, 폴딩법, 기수변환법, 대수적코딩법, 계수분석법, 무작위법

해시충돌 대처

• 해시 함수를 사용했을 때 같은 key값이 나오는 경우를 해결하는 방안

1. 체이닝(Separate Chaining)

• 해시를 변경하지 않고 연결하여 저장

1. 링크드 리스트 : 링크드 리스트를 사용해 그대로 연결하는 방식, 데이터 개수가 적을 때 유리
2. R-B Tree : 트리를 사용해 연결하는 방식, 데이터 개수가 많을 때 유리

2. 개방주소법(Open Addressing)

• 해시를 변경시켜 저장함

1. 선형 탐사(Linear Probing) : 다음이나 n개 뒤의 비어있는 해시에 데이터를 저장
2. 제곱 탐색(Quadratic Probing) : 제곱한 해시에 데이터를 저장
3. 이중 해시(Double Hashing) : 다른 해시함수를 한번 더 적용시킨 해시에 데이터를 저장

• 검색시 : O(1)