[Algorithm] 해시법

이번 포스팅은 해시법을 공부하며 제가 이해한 대로 정리해본 글입니다. 표현이 적절하지 않거나 틀릴 수도 있다면 댓글로 피드백을 부탁드립니다.

 

 

핵심 아이디어

데이터를 저장할 위치를 인덱스로 나타내어 간단한 연산을 통해 구하는 것이다.

 

방법

길이가 N인 배열이 있다면 배열의 모든 원소(이를 배열의 키라고 한다.)를 N을 나누어 준다. 이때 나누어져 나온 값들을 해시값이라고 하고 해시값으로 만든 테이블을 해시 테이블이라고 한다. 또한, 이와 같이 키를 해시값으로 변환하는 과정을 해시 함수라고 한다. 마지막으로 해시테이블에서 만들어진 원소를 버킷이라고 한다.

 

활용

해시법은 검색 뿐 아니라 데이터의 추가와 삭제에도 효율적으로 활용할 수 있다.

 

 

해시 충돌

배열의 모든 원소를 배열의 길이 만큼 나눈 나머지가 무조건 서로 다를 일은 없다. 즉, 버킷이 중복되는 현상이 발생할 수 있는데 이를 해시 충돌이라고 한다. 이를 해결하기 위한 방법으로 2가지가 있다.

 

체인법 (오픈 해시법)

해시값이 동일한 데이터를 연결리스트로 연결하는 방법을 말한다. 리스트의 수직 방향으로 늘어놓는 것을 생각하면 이해하기 쉽다. 체인법의 핵심 아이디어는 배열의 각 버킷에 저장하는 값이 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드를 참조하는 것이다. 연결리스트에서 원소를 추가할 경우 마지막 연결 리스트에 추가하고 앞쪽 노드를 참조하도록 한다. 또한, 해시값을 삭제할 경우 뒤쪽 노드가 앞쪽 노드를 참조하도록 한다.

 

오픈주소법 (선형 탐사법)

해시 충돌이 발생하면 재해시를 수행하여 빈 버킷을 찾는 방법이다. 이때 재해시를 위한 해시 함수는 임의로 지정할 수 있다. 오픈주소법으로 원소를 추가할 경우 충돌이 일어날 경우 재해시를 반복하여 수행하여 빈 버킷에 해시값을 넣는다. 또한, 해시값을 삭제할 경우 비어 있는 경우와 삭제한 것을 구분해준다. 이유는 삭제한 해시값이 채워져 있어 재해시로 다른 곳에 삽입된 해시값을 검색할 때 원래 그 자리가 비어있다고 판단하여 검색에 실패할 수 있기 때문이다.

 

 

참조: 

- Bohyoh Shibata,『자료구조와 함께 배우는 알고리즘 입문 파이썬 편』, 이지스퍼블리싱(2020), p.131~152

 

 

-히비스서커스-