HashTable

해싱(Hashing)

• 해싱이란 임의의 길이의 값을 해시 함수를 사용하여 고정된 크기의 값으로 변환하는 작업

해시 테이블(HashTable)

• 해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블이라고 한다.
• 해시함수를 사용하여 변환한 값을 색인(index)로 삼아 키(Key)와 데이터(Value)를 저장하는 자료구조다.

HashTable

해시 테이블 특징

• 순차적으로 데이터를 저장하지 않는다.
• Key를 통해서 Value를 얻을 수 있다. → 기본 연산(삭제, 삽입, 조회)의 시간 복잡도가 O(1)이다.
• 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적이다.
• Value는 중복 가능하지만 Key는 고유한 한 개의 값이다.
• 보통 배열로 정의한다.

해시 함수

• 해시 함수에서 중요한 것은 고유한 인덱스 값을 반환하는 것이다. 해시 테이블에 사용되는 대표적인 해시 함수는 4가지가 있다.

1. Division Method: 나눗셈을 이용하는 방법으로 입력 값을 테이블의 크기로 나눠서 계산한다.
   • 주소 = 입력값 % 테이블의 크기 // 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법
3. Multiplication Method: 숫자로 된 Key 값 K 와 0 ~ 1사이의 실수 A, 2의 제곱수인 m을 사용하여 계산한다.
4. Univeral Hashing: 다수의 해시 함수를 만들어 집합 H에 넣어두고 무작위로 해시함수를 선택해 해시 값을 만드는 방법

해시 충돌

• 해시 키가 중복될 때 발생하는 현상
• 해시 충돌이 절대 발생하지 않는 해시 함수를 만드는 것은 현실적으로 어렵다. 따라서 해시 충돌에 대해 대응하는 방법을 고안해야한다.
• 해시 키가 충돌한다고 해서 해시 데이터의 자료구조를 확장하는 것은 상당히 비효율적인 일이 될 수 있다. 따라서 해시 충돌이 최소한으로 발생될 수 있는 해시 함수를 구현하는 것도 중요하지만 해시 충돌 값을 어떻게 수용할지 고민해야 한다.

분리 연결법(Separate Chaining)

• 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것
• 두 개의 데이터가 동일한 공간 인덱스를 가리킨다면, 해당 공간에 새로운 이차원 배열 혹은 연결리스트 같은 자료구조를 구성하여 한 버킷에 여러 데이터를 저장하는 것
  • 큰 바구니 안에 작은 바구니 2개를 넣어서 저장하는 식
• 데이터의 수가 많아지면 동일한 버킷에 chaining 되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다.

개방 주소법(Open Addressing)

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

개방 주소법

1. Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 비어있는 버킷에 데이터를 저장한다.
   • 인접한 인덱스에 데이터를 삽입하기 때문에 데이터가 밀집되는 클러스터링 문제가 발생되고 이로 인해서 조회, 삭제 연산이 느려지게 된다.
2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2에 제곱, 3에 제곱만큼 칸을 옮기는 방식이다.
   • 해시테이블 내의 여유 공간이 충분하지 않을 때, 효율성이 떨어진다. 연속적으로 해시충돌이 발생하기 때문이다.
   • 이 방법은 데이터를 저장할 때 연속적인 제곱 위치를 탐색하게 되어 캐시 지역성을 고려하지 않기 때문에 캐시 효율성이 떨어질 수 있다.
3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들 보다 많은 연산을 하게 된다.
   • 이 방법은 해시 함수들 간의 상호작용에 의해 균일하지 않은 해시 충돌 패턴이 발생할 수 있다. 즉, 한 번의 충돌로 인해 또 다른 충돌이 발생할 수도 있고 아닐 수도 있어서 패턴을 파악하기 어렵다.
   • 해시 함수의 선택이 중요하며, 부적절한 해시 함수를 사용할 경우, 충돌이 더 자주 발생하여 성능 저하를 초래할 수 있다.

• Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다.
• 분리 연결법은 해시 테이블의 크기(메모리 사용량)을 유연하게 만들면서 해결하는 방법이고, 개방 주소법은 해시 테이블의 크기(메모리 사용량)을 고정하면서 저장할 위치를 잘 찾는 방법이라고 할 수 있다.

해시 충돌이 발생한 경우 최악의 시간 복잡도

• 해시 충돌이 발생한 경우 최기 시간복잡도가 O(1)이라고 했던거에 비해 시간이 많이 늘어나게 된다. 최악의 경우 한 개의 버킷에 모든 데이터가 포함되어있다고 보면 O(K)의 시간 복잡도를 가진다. 이 경우 일반적인 배열의 형태와 같다.

 

Hashtable VS Hashmap

Hashmap

• 해시 맵은 해시 테이블과 비슷한 구조다.
• 기본적으로 해시 맵은 해시 테이블과 달리 키와 값의 쌍으로 이루어진 데이터 구조이다. 한 개의 키 값에 여러 값을 가질 수 없지만 다중 맵을 구현해서 해시 테이블과 같은 구조를 가질 수는 있다.

Hashtable과 Hashmap의 차이

• 해시 테이블 과 해시 맵과의 큰 차이점은 Thread 관점에서 safe인지, 아닌지 차이다.
• 해시 테이블은 Null값을 허용하지 않아서 안전하지만 해시 맵은 Null값을 허용한다.
• 해시 테이블은 동기화를 지원하기 때문에 멀티 스레드 환경에서 데이터를 안전하게 사용할 수 있지만 해시 맵은 동기화를 지원하지 않기 때문에 단일 스레드 환경에서 사용해야 한다.
• 해시 맵이 해시 테이블보다 삭제, 삽입, 조회에 대한 연산이 비교적 빠르다

 

---

출처

https://baeharam.netlify.app/posts/data structure/hash-table

https://mangkyu.tistory.com/102

https://www.geeksforgeeks.org/double-hashing/