[자료구조] 해시 (Hash)

해시

 

현대 사회에서 데이터를 저장하거나 탐색할 때 가장 쉽게 떠올릴 수 있는 방법은 "순차 탐색" 이다.

가장 확실하게 찾을 수 있지만 최악의 경우 탐색할 때마다 모든 데이터를 살펴봐야하기 때문에 효율적이진 않다.

 

이 방법을 개선하기 위해 찾아야 할 값이 어디에 있는지 알아낼 방법이 필요하다.

즉, 어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있으면 탐색 필요 없이 바로 데이터를 찾을 수 있다.

이러한 자료구조를 "해시(Hash)"라고 한다.

 

해시의 개념

• 해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.
• 키를 활용해 데이터 탐색을 빠르게 할 수 있다.

 

해시의 특징

1. 해시는 단방향으로 동작한다.

• 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수 없다.

2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다.

• 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.

3. 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.

 

해시 테이블(Hash Table)

• 키와 대응한 값이 저장되어 있는 공간이다.
• 해시 테이블의 각 데이터를 "버킷(Bucket)" 이라고 한다.

 

해시의 특성을 활용하는 분야

특정 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋다.

• 비밀번호 관리
• 데이터베이스 인덱싱
• 블록체인

---

해시 함수

자바에서는 해시셋(HashSet) 혹은 해시맵(HashMap)이라는 표준 API를 제공합니다.

 

해시 함수를 구현할 때 고려할 내용

1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다.

 

만약 해시 테이블의 크기가 N인 경우, 해시 함수의 결과는 인덱스 0 ~ N-1 사이의 값을 내야 한다.

키 -> 해시함수 -> 해시테이블 인덱스

 

2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.

 

충돌 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미

 

만약 키가 홍길동, 홍길서일 때, 해시 함수를 통한 결과의 인덱스가 같은 값을 가진다면 저장 위치가 같기 때문에 충돌이 발생한다. (충돌이 아예 발생하지 않는 해시 함수는 거의 없다.)