해시 Hash
해시 함수란 데이터의 효율적 관리를 목적으로 임의의길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
매핑 전 데이터 값을 key, 매핑 후 데이터 값을 hash value라 하고, 매핑하는 과정을 해싱이라고 한다.
해시 테이블
key에 결과 값 value를 저장하는 자료구조이다.
적은 리소스로 많은 데이터를 효율적으로 관리하기 위해 사용한다. index에 해시값(key)을 사용하면서 삽입, 삭제, 탐색을 O(1) 시간 복잡도에 완료할 수 있다.
또한 다양한 길이의 key 값을 일정한 길이를 가지는 해시 값으로 변경하여 저장소를 효율적으로 운영할 수 있다.
단점
- 순서가 있는 배열에는 어울리지 않는다.
- 데이터가 저장되기 전에 미리 저장공간을 확보해야 한다.
충돌
같은 hash(key)값을 가지게 되면 충돌이 발생한다.
-
Chaining
동일한 hash값을 가지는 value를 연결리스트를 이용해 체인처럼 엮는 방법이다.
시간 복잡도
같은 해시 값에 저장된 자료의 개수(a)의 시간 복잡도를 가진다. O(a)
최악의 경우는 하나의 해시에 모든 자료가 연결되어 있는 경우로 O(N)의 시간 복잡도를 가진다.장점
한정된 저장소를 효율적으로 사용할 수 있다.
미리 공간을 잡아 놓을 필요가 없다.단점
한 hash에 자료들이 계속 연결되면 검색 효율이 떨어진다.
외부 저장 공간을 사용해야 한다. -
Open Addressing 개방주소법
비어있는 버킷에 데이터를 저장하는 방법이다.
저장소가 어느정도 채워졌을 때, 저장소의 사이즈를 늘려주면서 비어있는 공간을 확보하는 것이 중요하다.시간 복잡도
저장 공간에 데이터가 어느정도 들어있는지에 따라 달라진다. 최선의 경우 O(1), 최악의 경우 O(N)이다.장점
또 다른 저장공간 없이 해시테이블 내에서 처리가 가능하다.단점
비어있는 공간을 확보해 놔야 한다.
비어있는 공간을 찾는 알고리즘 성능에 따라 해시테이블 성능이 바뀐다.
