해시 테이블(Hash Table)
해시 테이블은 Key-Value 속성을 가진다.
key는 value를 찾는 수단이다.
- 해시(Hash)는 색인 또는 인덱스, 해시 펑션(hash function)은 key->hash로 만들어 주는 함수, 해시 테이블은 해시(Hash)를 주소로 삼아 데이터를 저장하는 자료구조이다.
해시 테이블의 장단점
장점
ㄴ 데이터 저장/읽기 속도가 빠르다. => 검색 속도가 빠르다.
ㄴ 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉽고, 충돌이 없다면 해쉬테이블은 시간복잡도 O(1)로 짧다!
단점
ㄴ 일반적으로 저장공간이 좀더 많이 필요하다.
ㄴ 여러 키에 해당하는 주소가 동일한 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다.
ㄴ 데이터 충돌이 발생한다면 Chaining에 연결된 리스트들까지 모두 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.
주요용도
ㄴ 검색이 많이 필요한 경우
ㄴ 저장, 삭제, 읽기가 빈번한 경우
ㄴ 캐쉬 구현시 (중복 확인 쉽기 때문)
시간 복잡도
- 평균 시간 복잡도는 0(1)이나 해시 충돌이 발생하였을때 최악의 시간 복잡도 0(N)이 된다.
- 즉 가장 큰 단점은 해시충돌이 발생하였을때이다.
Hash Collision(해시 충돌)
ex) A,B 두가지 key가 있을때 A와 B를 해시 펑션(hash function)으로 해시 값을 얻었는데 해시 값이 2로 똑같이 나왔다. 이런 현상을 해쉬 출동 이라고 한다.
해시 함수로 해시를 만드는 과정에서 서로 다른 key가 같은 해시로 변경되면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1로 매핑되어야 하는 해시 테이블의 특성에 위배된다.
통계적으로 해시 테이블의 공간 사용률이 70% ~ 80%정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.
보완 방법
- 연결리스트로 Chaining
- 값에서 다른 값을 가르킬 수 있는 메모리 공간을 둬 충돌이 발생하였을 때 그 그 값을 다른 값을 가르키게 하여 연결시켜주는 방식
- Open Addressing 배열로 구현 -> 다른 버킷에 저장
- 배열로 여유 메모리공간을 두어 충돌하였을때 할당된 인접 메모리 공간에 다음 값을 저장하는 방법
- Double Hasing -> 두 개의 해시함수 이용
C#, Unity