해시테이블(Hash Table)
효율적인 탐색(빠른 탐색)을 위한 자료구조로, key-value쌍의 데이터를 입력받는다.
hash function h에 key값을 입력으로 넣어 얻은 해시값 h를 위치로 지정하여 key-value 데이터 쌍을 저장한다. 저장, 삭제, 검색의 시간복잡도는 모두 O(1)이다.
Direct-address Table(직접 주소화 테이블)
key값이 k인 데이터를 index k 위치에 저장하는 방식이다.
문제점
- 불필요한 공간 낭비
- key값으로 문자열이 올 수 없다.
Hash Table
위와 같은 이유로 직접 주소화 방법은 데이터 쌍을 저장하기 위한 방법으로 잘 맞지않는다.
그 대안으로는 Hash Table을 사용하는 것이다. Hast Table은 hash function h를 활용해서 key-value를 저장한다. key값을 k라고 했을 때, h(k) 함수 값에 해당하는 index에 데이터 쌍을 저장한다.
💡 h(k)는 키 k의 해시값이라고 표현한다. 모든 데이터의 key값은 무조건 존재해야 하며, 중복되는 key값이 있어서는 안된다.
key-value 데이터를 저장할 수 있는 각각의 공간을 slot 또는 bucket이라고 한다.
충돌(Collision)
서로 다른 key의 해시값이 똑같을 때를 말한다. 중복되는 key는 없지만 해시값은 중복이 될 수 있는데 이 때 Collision이 발생했다고 한다. 따라서 collision이 최대한 적게 나도록 hash function을 설계해야하고, 어쩔 수 없이 collision이 발생하는 경우 seperate chaining 또는 open addressing등의 방법을 사용하여 해결해야 합니다.
🏁