해쉬

해쉬 테이블의 개념

출처 : 위키백과 해쉬테이블

해시 테이블이란 (Key, Value) 한 쌍을 데이터로 저장하는 자료구조이며 데이터가 아무리 많아도 O(1) 의 탐색 시간을 보장 한다. 빠른 탐색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데 이터를 저장하기 때문이다. 각각의 Key 값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 

 

따라서 Key 값으로 데이터를 검색할 때 해시 함수를 수행하여 나온 고유 index로 바로 배열에 접근하면 되기에 시간 복잡도가 O(1)이 되는 것이다.

 

구성 요소

1. 해쉬

해쉬 함수의 결과물이다. 해쉬 코드라고도 한다. 해쉬 테이블의 저장소(bucket)에서 Value와 매칭되어 저장된다.

 

2. 해쉬 함수

키(Key)를 해쉬로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 고정된 길이를 갖는 해시값으로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 

 

해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 해시 테이블에 사용되는 대표적인 해시 함수로는 아래의 4가지가 있다.

Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

3. 해시 테이블

기본적으로 맨 위에서 서술한 바와 같다.

키, 해시함수, 해시, 값, 저장소(Bucket, slot)으로 이루어져있으며 key-value 한 쌍으로 데이터가 저장되고 해시 함수를 통해 나온 해시코드를 index로 사용하여 데이터에 바로 접근하게 된다.

 

4. 충돌 & 충돌 해소

충돌이란 서로 다른 Key 값이 해시 함수를 거치면서 같은 index로 변환되는 현상을 말한다. 

 

해시 테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.

- 분리 연결법 (Seperate Chaining)

Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다. 실제로 Java8의 Hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.

이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

 

- 개방 주소법(Open Addressing)
Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

 

1. Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다고 한다.

해시테이블 시간 복잡도

각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다. 하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.

충돌을 방지하는 방법들은 데이터의 규칙성(클러스터링)을 방지하기 위한 방식이지만 공간을 많이 사용한다는 치명적인 단점이 있다.

만약 테이블이 꽉 차있는 경우라면 테이블을 확장해주어야 하는데, 이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확정을 하지 않도록 테이블을 설계해주어야 한다.

(통계적으로 해시 테이블의 공간 사용률이 70% ~ 80%정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.)

또한 해시 테이블에서 자주 사용하게 되는 데이터를 Cache에 적용하면 효율을 높일 수 있다. 자주 hit하게 되는 데이터를 캐시에서 바로 찾음으로써 해시 테이블의 성능을 향상시킬 수 있다.

자바에서 사용하는 Hash

 

HashTable이란 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java2에서 처음 선보인 Java Collections Framework에 속한 API이다.
HashTable 또한 Map 인터페이스를 구현하고 있기때문에 HashMap과 HashTable이 제공하는 기능은 같다.

차이점

• 보조 해시 함수
  • HashMap은 보조 해시함수를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충동(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.
• 동기화
  • HashMap의 경우 동기화를 지원하지 않는다. 그래서 Hash Table은 동기화 처리라는 비용때문에 HashMap에 비해 더 느리다고 한다. 프로그래밍상의 편의성 때문에 멀티쓰레드 환경에서도 HashTable을 쓰기보다는 HashMap을 다시 감싸서 Map m == Collections.syschronizedMap(new HashpMap()); 과 같은 형태가 더 선호된다.

 

병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하며, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.

출처

책 윤성우의 열혈 자료구조

https://mangkyu.tistory.com/102

[자료구조] 해시테이블(HashTable)이란?

https://go-coding.tistory.com/30

[자료구조] Hash의 개념 및 설명