프로그래밍을 하다보면 자료구조에 대한 이해가 필요하다. 단순무식하게 한다해도 원하는 결과를 얻을 수는 있지만, 적절한 자료구조를 이용하면 메모리, 속도 면에서 상당한 효율을 볼 수 있다. 실제로, 파이썬의 딕셔너리(Dictionary)가 해시의 원리를 이용한 것이다.
해시(Hash), 해시함수(Hash Function)란?
- 해시함수(Hash Function)
특정한 규칙을 이용하여 임의의 길이를 가진 데이터를 일정한 길이를 가진 데이터와 매핑(mapping)해주는 함수
- 해시 값(Hash Value)
해시함수에 의해 얻어지는 값. 간단히 해시(Hash)라고도 한다.
해시 테이블(Hash Table)
해시 테이블이란, 검색하고자 하는 키(key)값으로 해시 함수를 돌려서 반환받은 해시 값을 배열의 인덱스로 환산해서 데이터에 접근하는 방식의 자료구조다. 여기서 키(key)값은 어떤 자료형이든 될 수 있다.
해시 테이블의 장점
- 검색 속도가 매우 빠르다.
해시 함수를 이용해서 만든 해시값은 정수다. 배열 공간을 고정된 크기만큼 만들어놓고 해시값을 배열의 개수로 나머지 연산을 해서 배열에 나눠 담는 것임. 즉, 해시값 자체가 배열의 인덱스로 쓰이기 때문에 검색 자체가 필요없고 해시값으로 데이터의 위치에 직접적으로 접근하기 때문에 빠른 것이다.
해시 충돌(Hash collision)
해시 충돌이란, 해시 함수가 서로 다른 입력값에 대해 동일한 출력값(해시 값)을 내는 현상을 말한다. 그 이유는 키값은 어떠한 자료형이 될 수 있고, 그 가짓수가 무한한데, 해쉬값은 정수개만큼 존재 할 수 밖에 없기 때문에 알고리즘이 아무리 좋다해도 어떤 키는 중복되는 해시값을 가질 수 밖에 없다. 혹은 해시함수가 서로 다른 해쉬값을 만들어내도 배열 공간이 한정되어 있기 때문에 같은 공간 내에 위치할 수 있다.
해시 테이블에서는 이 해시 충돌을 최소화시키는 좋은 해쉬함수를 만드는 것이 중요하다.
해시 충돌 해결법 - Chaining
해시충돌을 방지해주기 위해서는 배열 공간 안에 링크드 리스트(Linked List)를 넣고, 그 안에 값을 하나씩 넣어주면서 충돌을 피한다.