해시 테이블 충돌(Hash, Hash Collision)

해싱(Hashing)은 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것.

그리고 해싱은 해시 테이블(Hash Table)과 해시 함수(Hash Function)로 구성된다.

 

해시테이블(Hash Table, Hash Map 이라고도 불림)은 key와 Value를 갖는 자료구조이다.

주로 효율 적인 검색에 활용되는데, 이는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문.

버킷(bucket)이란?

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다


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

1. Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.

2.Digit Folding : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.

3. Multiplication Method : 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m

4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

위 그림에서 John Smith라는 사람의 전화번호를 찾아야 한다고 가정해보자.

해시함수의 입력값은 "John Smith"이고 출력값은 "01"이다.

그리고 "01"에 해당하는 값인 "521-8976"을 bucket에서 가져온다.

 

즉, 해시함수를 사용해 John Smith의 Key(index)를 "01" 로 만들고, 이를 이용해 "521-8976"란 값을 가져옴.

 

이러한 특성 덕분에 순차검색에 비해, 해시테이블을 이용한 검색은 속도 측면에서 획기적이라고 할 수 있다. 

---

해시에서 Key를 생성하기 위한 다양한 알고리즘이 존재한다.

MD-5나 SHA이 그 유명한 해시 알고리즘 중 하나이다.

 

'apple' 이라는 문자열이 주어졌다고 가정해보자.

우리는 Key를 만들기 위해서, 특정한 소수인 '5381' 을 이용해보자.

 

 

Key는 최대한 중첩되지않고, 고르게 만드는 것이 좋다고 알려져있다.

그렇게 만들기 위해서 아래와 같은 과정을 거칠 것이다.

 

(1) Hash 값을 왼쪽으로 5번 비트연산시킨다.

(2) 원본 Hash 값을 더한다.

(3) 한 문자의 ASCII 값을 더한다.

(4) 위의 결과를 모든 문자에 대해서 반복한다.

(5) 최종 값이 해시테이블의 범위를 벗어나면, 나머지 연산을 취해준다.

 

Hash의 최대 테이블 크기를 '8191'로 가정해보자.

상세한 과정을 보이면 아래와 같다.

 

 

이러한 간단하면서도 일반적인 계산은 나름 분포도가 좋은 계산이 나오는 것으로 보여진다.

 

참고 : https://kbw1101.tistory.com/55

---

해시 충돌(Hash Collision)

 

위와 같이 데이터를 Key로 간소화하여 저장하고, 만들어진 Key의 위치에 자료를 삽입할 수 있다.

그런데, Key라는 것은 최대한 분포도가 넓게 만들긴 했지만

언젠가는 다른 문자열에 대해서 동일한 Key값이 발생할 수 있다.

 

이러한 상황을 해시 충돌(Hash Collision)이라고 한다.

같은 키값을 갖는 데이터가 생긴다는 것은, 특정키의 버켓에 데이터가 집중된다는 뜻이다.

그래서 너무 많은 해시 충돌은 해시테이블의 성능을 떨어트린다.

 

그러므로 해시 함수를 잘 정의하여 해시 충돌을 최소화 하는 것이 성능 개선에 도움이 된다.

해시함수의 입력값은 무한하지만,

출력값의 가짓수는 유한(출력값, 즉 키가 유한하지 않다면 해시기법을 사용하는 의미가 없다.)하므로

해시 충돌은 반드시 발생한다.

 

위 그림에서 Sandra Dee라는 사람의 연락처를 삽입하려고 한다.

하지만 Sandra Dee의 키는 John Smith의 키와 결과값이 같다.

둘 사이의 충돌이 일어난 것!

충돌이 일어난 주소의 bucket에 데이터가 추가로 담긴 것을 확인할 수 있다.

 

만약에 해당 bucket에 충분한 공간이 없다면 오버플로우가 발생한다.

 

1. 체이닝(Chaining)

버켓 내에 연결리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식.

위 그림에서 John Smith와 Sandra Dee의 해시 충돌이 발생하자, Sandra Dee의 연락처를 삽입할 때 연결리스트로 데이터를 연결하는 것을 확인할 수 있다.

2. 개방 주소법(Open Addressing)

체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing)

하지만 개방 주소법의 경우에는 다르다.

해시 충돌이 일어나면 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. (충돌이 일어난 인덱스를 뛰어넘어서, 빈 공간이 있는지 탐색 후 삽입)

개방 주소법은 대표적으로 3가지가 있다.

 

선형 탐색(Linear Probing) : 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.

제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)

이중 해시(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

 

 

 

 

◎ 체이닝(Chaining)의 장점  
 → 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.
 → 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다.

◎ 개방주소법(Open Addressing)의 장점  
 → 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.    
→ 삽입,삭제시 오버헤드가 적다.  
→ 저장할 데이터가 적을 때 더 유리하다.
→ Open Addressing에서 데이터 삭제 시, 삭제된 공간은 Dummy Space로 활용된다. 따라서 Hash Table을 재정리 해주는 작업이 필요하다.

---

해시 테이블(HashTable) 시간 복잡도

 

• 데이터 조회
  
  평균: O(1) - 각각의 Key값은 해시함수에 의해 고유한 index를 가지므로 데이터에 바로 접근
  
  최악: O(N) - 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로
  
  
• 충돌을 방지하는 방법들은 데이터의 규칙성(클러스터링)을 방지하기 위한 방식이지만 공간을 많이 사용한다는 치명적인 단점이 있다. 
  만약 테이블이 꽉 차있는 경우라면 테이블을 확장해주어야 하는데, 
  이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확정을 하지 않도록 테이블을 설계해주어야 한다.
  (통계적으로 해시 테이블의 공간 사용률이 70% ~ 80%정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.)
  
  해시 테이블에서 자주 사용하게 되는 데이터를 Cache에 적용하면, 자주 hit하게 되는 데이터를 캐시에서 바로 찾을 수 있으므로 해시 테이블의 성능을 향상시킬 수 있다.