해쉬 함수에 검색하고자 하는 키 값을 넣으면 해쉬 알고리즘에 의해 해쉬코드가 나온다. 이 해쉬코드를 가지고 배열의 인덱스로 환산해서 값에 접근한다. 그렇기 때문에 해쉬코드만 알면 바로 값을 알 수 있어 검색 시 속도가 굉장히 빠르다. 키는 문자열, 정수, 파일값 등 다양한 입력 자료형이 올 수 있다. 해쉬코드는 항상 같은 길이의 값이 나오게 된다.
collision??
시간 복잡도 O(1)이지만 collision이 많을 경우 O(n)이다. collision은 동일한 인덱스 공간 안에 값이 여러 개가 있는 경우이다. 해쉬코드로 인덱스 접근을 했는데 보니까 n개의 값이 들어있다면 일일이 확인해야 하므로 최악의 경우 O(n)이다. 이런 문제를 해결하기 위해 값을 골고루 분산시키는 해쉬 알고리즘이 중요하다.
해쉬함수는 서로 다른 키로 동일한 해쉬코드를 만들기도 하는데 이런 경우도 collision이다. 동일한 해쉬코드가 생성되는 이유는 해쉬코드의 길이가 항상 동일하기 때문이다. 입력으로는 무한한 경우의 수가 있지만 출력인 해쉬코드는 길이가 정해져 있어 유한한 값이기 때문이다.
같은 인덱스에 다른 해쉬코드가 들어갈 수 있다.
간단한 예
해쉬함수 : 자료형이 문자열인 키의 각 문자의 아스키 코드를 더해서 해쉬코드를 만든다.
해쉬테이블 : 고정된 길이의 배열의 인덱스(해쉬코드%배열의 길이)에 해쉬코드를 넣는다. 배열에 그냥 해쉬코드를 삽입할 경우 collision이 발생할 때 값이 덮어씌워진다. 그러므로 linked list로 해쉬코드를 연결해야 한다.
검색 요청이 호출될 경우, 키를 해쉬함수의 인자로 넣고 결과로 나온 해쉬코드를 배열의 길이로 나눈 나머지를 인덱스 삼아 배열의 인덱스에 있는 linked list에서 찾는다.
'과목 > 자료구조' 카테고리의 다른 글
| 파이썬 연결 리스트 singly linked list (0) | 2019.08.03 |
|---|