[자료구조]해시 해시함수 해시테이블 충돌 개념, 해결법

여기서는 자료구조를 설명하는 것이 주된 목표이기 때문에 해시에 대해서는 간단하게 짚고 넘어간다.

 

1. 해시

해시는 어떤 데이터를 크기가 고정된 다른 값으로 변환하는 것을 뜻한다.

따라서 모든 해시값들은 같은 크기를 가지며, 같은 입력 데이터에는 동일한 해시값을 반환한다.

 

주로 암호학에 많이 사용되며 데이터의 무결성을 검사하는 데에 사용되기도 한다.

 

 

2. 해시 함수

입력값에 따라 일정한 값을 반환하는 함수로 수많은 함수들이 해시함수가 될 수 있지만, 몇 개의 조건이 존재한다.

일관성 : 같은 입력값에는 언제나 같은 반환값을 가져야한다.

고유성 : 입력값이 다르다면 반환하는 해시값도 달라야 한다.(서로 다른 입력에 동일한 해시값이 나오는 충돌을 최소화해야 한다.)

고르게 분포 : 가능한 모든 해시값이 균등하게 분포되어 충돌을 최소화해야 한다.

 

이외에도 따져야 할 사항들이 많으며 각각의 용도에 맞는 함수들이 존재한다.

 

 

3. 해시 테이블

해시 테이블은 해시 함수를 거친 해시값(key)과 데이터(value)의 쌍을 저장하기 위한 자료 구조이다.

만약 한 고등학교의 전교생의 학번을 키(key)로 하고, 해당학생의 성적을 값(value)으로 한다면

학번을 해시함수에 넣은 결과값을 가지고 성적을 손쉽게 검색할 수 있다.

이때 하나의 키가 가지는 정보들의 구역을 버킷(bucket)이라는 용어를 사용한다.

 

적재율 = (키의 개수) / (해시테이블의 크기) 

해시 테이블이 얼마나 사용중인지 적재율을 이용하여 구할 수 있다.

일반적으로 적재율이 0.7정도일 때 적절하다고 여겨지며, 적재율이 높은 경우 해시 충돌의 위험이 있으므로 해시 테이블을 확장하여 더 많은 키를 사용해야 한다.

전화번호를 예시로 한 해시테이블

 

 

4. 충돌 해결

다른 입력값이 동일한 해시값을 가지는 것을 충돌이라 하는데 해시를 다룰 때는 이 충돌을 관리하는 것이 매우 중요하다.

 

• 체이닝
  충돌이 일어났을 경우 같은 키값, 즉 동일한 버킷에 연결리스트로 정보를 저장한다.
  추가적인 메모리를 사용하게 된다.
• 개방 주소 방법
  충돌이 일어나면 다른 버킷에 값을 저장하는 방식
  다른 빈 버킷을 찾는 탐색 방법들을 사용하게 된다.
  탐색을 할 때에도 동일한 방법으로 다른 버킷에 있는 데이터를 찾아내게 된다.