1. 해시(Hash)
해시 함수(hash function) 또는 해시 알고리즘(hash algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬, 해시 등으로 부른다.
해시는 input 데이터의 길이에 상관 없이 일정한 길이의 ouput을 출력한다. 이러한 값을 간단히 해시라고 부르며 이를 해시 테이블(Hash Table)이라는 자료구조로 저장한다. 해시 테이블은 해시 함수를 사용하여 키를 해시값으로 매핑하고 이 해시값을 주소(인덱스)로 삼아 key와 데이터를 함께 저장하는 구조이다.
2. 해시 충돌(Hash collision)
해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.
해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다. 서로 다른 입력 키 값이 서로 다른 해시 값(인덱스)으로 매핑될 경우 해시 테이블 조회에 걸리는 시간은 상수 시간이 된다. 그러나 여러개의 서로 다른 키 값이 동일한 인덱스로 매핑될 경우, 해시 충돌이 발생하여 해시 테이블의 성능을 떨어뜨리게 된다.
- 해결 방법
- 체이닝(chaining) 각각의 해시 테이블 인덱스에 해당하는 자료구조를 연결 리스트로 만드는 방법
- 개방 번지화(open addressing) 해시 테이블 인덱스 중 비어있는 공간을 할당하는 방법
3. 장단점
- 장점 - 해시테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로O(1)의 시간복잡도를 가지고 있다.
- 단점 - 해시 충돌이 발생한다.
- 데이터가 저장되기 전에 미리 공간을 만들어 놔야 하므로 사용되지 않는 공간이 발생한다. - hash function 의존도가 높다.
출처
https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98
https://go-coding.tistory.com/30
곰팡이 진화 과정