key-value로 이루어진 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조
해시 테이블이 빠른 검색 속도를 제공하는 이유 -> 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문.
해시 테이블은 각각의 Key값이 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 됨.
(여기서 실제값이 저장된느 장소 -> bucket 또는 slot)
key는 hash 함수를 통해 hash로 변경이 되며 (이 과정을 Hashing이라고 함) hash는 value와 매칭되어 저장소에 저장됨.
< 예시 >
Sandra Dee라는 사람의 전화번호를 찾는 과정이라면,
해시함수(Hash Function)의 입력값은 "Sandra Dee"이고 출력값은 "14"이다.
그리고 index가 "14"인 bucket에서 "521-9655"를 찾는다.
< Hash Table Data Structure >
- key : 고유한 값이며, 해시 함수의 input이 됨. 최종 저상소에 저장되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있음.
- 해시함수 : key를 hash로 바꿔주는 역할. 다양한 길이를 가지고 있는 key를 일정한 길이를 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줌.
단, 서로 다른 key가 같은 hash가 되는 경우 해시충돌(Hash Colllision)이라고 한다. -> 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요!!- 해시(Hash) : Hash Function의 결과물, 저장소(buckey, slot)에서 값(value)과 매칭되어 저장됨.
- 값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색. 접근이 가능해야 함.
해시테이블은 Key-Value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있음.
키의 전체 개수와 동일한 크기의 bucket을 가진 해시테이블
- 장점 : 키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않음.
- 단점 : 전체 키의 개수만큼의 테이블 크기를 유지하는 것은 메모리 낭비일 수 있음.
-> 실제 키 개수보다 적은 해시테이블을 사용하기 때문에 해시 충돌이 발생할 수 밖에 없고, 해시 충돌을 해결하기 위해 다양한 방법들이 고안되었음.
A,B 두가지 key가 hash function을 통해 얻은 Hash 값이 똑같을 때
Key-Value가 1:1로 매핑되어야 함
너무 많은 해시 충돌은 해시 테이블의 성능을 떨어뜨린다.
저장소(Bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법
1) 연결리스트를 사용하는 방식 (Linked List)
2) Tree를 사용하는 방식 (Red-Black Tree)
해시 충돌이 일어나면 다른 버킷에 데이터를 저장하는 방식을 개방 주소법이라고 한다.
1) 선형탐색
- 해시 충돌시 다음 버킷에 저장하는 방법
2) 제곱 탐색
- 해시 충돌시 제곱만큼 건너뛴 버킷에 데이터를 저장하는 방법
3) 이중 해시
- 해시 충돌시 다른 해시함수를 한 번 더 적용한 결과를 저장