[자료구조] 해시 테이블이란? (해시 함수, 해시 충돌과 해결 방법, 자바에서 HashMap과 HashTable)

목차

• 해시 테이블이란?
• 해시 함수
• 해시 충돌과 해결 방법
  • Seperate Chaining 방식
  • Open Address 방식
• Resizing (테이블 크기 재할당)
• 자바에서 HashMap, HashTable

 

---

1. 해시테이블이란?

해시 테이블은 key-value 형태로, 각각의 key 값에 해시 함수를 적용해 배열의 인덱스를 생성하고, 인덱스에 데이터를 저장하거나 검색할 수 있는 자료구조이다. 해시 테이블은 내부적으로 배열을 이용하고 있고 key를 통해 배열의 인덱스에 접근할 수 있기 때문에, 속도가 매우 빠르다는 장점을 가지고 있다. 하지만 해시 함수에 의존하고 있기 때문에, 충돌이 일어나지 않고 빠르게 해시를 만들어내는 해시 함수의 역할이 중요하다.

 

(특징)

• 삽입, 삭제, 검색 모두 평균적으로 O(1)의 시간복잡도를 가진다. (충돌이 없을 경우)
• 모든 key에 대해 충돌이 발생할 경우, 삽입, 삭제, 검색 모두 O(n)의 시간복잡도를 가진다.
• 대표적인 해시 알고리즘으로 MD5가 있다.

 

(장점)

• 빠른 검색, 삽입, 삭제 기능을 가지고 있다.
• key와 해시가 연관이 없어 보안에 유리하다.
• 데이터의 중복을 제거하는 데에 유리하다.

 

(단점)

• 해시 함수에 대한 의존성이 크고, 해시 충돌 가능성을 가지고 있다.
• 데이터가 저장되기 전 배열을 미리 확보해야 하기 때문에, 공간 효율성은 떨어진다.
• 메모리 공간에서 순차적으로 저장되지 않는다.
• 모든 key에 대해 충돌이 발생할 경우, 배열과 다를 게 없다.

 

---

2. 해시 함수

해시 함수는 키를 이용해 해시, 즉 배열의 인덱스로 변환하는 함수이다. 어떤 해시 함수를 사용하냐에 따라 충돌 발생 빈도, 연산 속도, 키 분포가 달라진다. 따라서 좋은 해시 함수를 사용해 해시 테이블을 구성해야 하며, 대표적인 해시 함수는 나눗셈법, 곱셈법 등이 있다.

 

** 나눗셈법

해시 테이블의 크기를 N으로 설정한 상태에서, N으로 나눈 나머지를 해시값으로 사용하는 방법이다. 이때 N은 2의 제곱 형태는 피하는 것이 좋고, 소수를 사용하는 것이 좋다.

 

---

3. 해시 충돌과 해결 방법

해시 충돌은 서로 다른 key가 같은 해시 값을 가지는 상황을 의미하며, 충돌이 발생했을 때 Seperate Chaining과 Open  Addressing으로 충돌을 해결해야 한다.

 

1) Seperate Chaining

: 충돌이 발생한 인덱스에 리스트나 트리를 삽입해, 여러 개의 값을 저장하여 충돌을 해결하는 방법이다. 이 경우에는 key를 이용해 인덱스에 접근한 후, 리스트나 트리를 조회하여 데이터를 가져온다. 만약 인덱스가 특정 하나로 계속해서 충돌이 일어나면, 체인이 길어져 시간복잡도가 O(n)이 될 수도 있다.

 

(특징)

• JAVA에서 해시 테이블은 Tree를 이용한 Seperate Chaining 방식을 해시 충돌을 해결하고 있다.

(장점)

• 연결을 위해 새로운 메모리 공간을 할당해주기만 하면 되므로 테이블 리사이징에 대한 메모리 소모가 적다.

(단점)

• 하나의 인덱스에 여러 개의 데이터를 연결할 경우, 최악의 경우 시간복잡도가 O(n)이 된다.
• 연결리스트나 트리를 이용하기 때문에, 캐시 성능이 떨어진다.
• 링크 주소를 저장하기 위한 추가 메모리 공간이 필요하다.

 

 

2) Open Addressing

: 충돌이 발생하면 새로운 해시를 찾아, 해당 인덱스에 데이터를 저장하여 충돌을 해결하는 방법이다. 선형 탐사와 제곱 탐사를 통해 주변에 비어있는 해시를 찾는 방법도 존재하지만, 이중 해시를 통해 새로운 해시를 탐색한다. 이중 해싱은 다른 해시 함수를 거치면서 각기 다른 인덱스가 나올 확률이 크기 때문에, 선형 탐사  및 제곱 탐사에서 발생하는 클러스터링 문제를 해결할 수 있다.

 

(특징)

• Python에서 해시 테이블은 Open Adressing 방식으로 해시 충돌을 해결하고 있다.

(장점)

• key-value에 대한 1대 1 구조로 이뤄진다.
• 배열을 이용하기 때문에 캐시 효율이 좋다.

(단점)

• 데이터가 늘어나는 만큼 데이터를 저장하기 위한 메모리를 확보해야 한다.
• 충돌이 많이 발생할수록 데이터가 뭉치는 클러스터링 문제가 발생할 수 있다.

 

---

4. Resizing : 테이블 크기 재할당

해시 테이블은 유한한 데이터 공간을 가지기 때문에, 어느 순간 테이블이 꽉 차는 상황이 발생할 수 있다. Open Address 방식을 사용하는 경우에는 더 이상 데이터를 저장할 공간이 없고, Seperate Chaining 방식을 사용하는 경우에는 연결된 데이터가 길어지면서 해시테이블에 대한 장점이 사라지게 된다. 따라서 저장 공간의 75%가 채워지면 테이블을 두배로 확장된다.

 

---

5. 자바에서 HashTable과 HashMap

JAVA에서 해시 테이블은 동기화를 지원하고, 해시맵은 동기화를 지원하지 않는다. 따라서 병렬 처리를 위해 자원의 동기화를 고려해야 할 경우 해시 테이블을 사용하고, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않을 경우에는 해시맵을 사용해야 한다.