해시 테이블

해시 테이블 : 효율적인 탐색을 위한 자료구조로 키(Key)와 값(Value)로 구성

해시 함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수, 해시 함수를 사용하여 구한 Key를 해시라고함.

ex) 제곱법, 폴딩법, 기수변환법, 대수적코딩법, 계수분석법, 무작위법

 

해시충돌 대처 : 해시 함수를 사용하면 같은 key값이 나오는 경우가 있기때문에 이를 해결하는 방안

1. 체이닝(Chaining) : 해시를 변경하지 않고 값을 연결리스트로 연결시킴

2. 개방주소법(Open Addressing) : 해시를 변경시켜 저장함

- 선형 탐사(Linear Probing) : 다음이나 n개 뒤의 비어있는 해시에 데이터를 저장

- 제곱 탐색(Quadratic Probing) : 제곱한 해시에 데이터를 저장

- 이중 해시(Double Hashing) : 다른 해시함수를 한번 더 적용시킨 해시에 데이터를 저장

 

검색시 : O(1)