면접 질문 답변으로 떠올리지 못했던 hash table에 대해

 

 최근 추천받은 책에서 안전 해시 설계에 대한 글을 보면서 전에 기술면접때 받은 한 질문이 떠올랐다.

질문은 무수히 긴 스트링 값이 있을때, 거기서 해당 단어가 있는지 없는지 확인하고자 한다면 어떻게 해야할까?였다.

분명 좋은 방법이 있을텐데 당시 난 아무런 방법을 떠올리지 못했고, 단순히 contains을 통해 포함 유무를 확인했을 것 같다고 했다. 면접이 끝날 때쯤 질문시간에서 난 해당 질문에 대해 해결 키워드를 질문을 했고, 해시 테이블을 사용해 보라는 답변을 받았다.

말을 듣고, 해시테이블에 해당 해시코드로부터 인덱스를 가져와 나눠져서 저장하는 그림이 연상되었다. 하지만 하나의 스트링을 나눠서 저장하는 로직에 대한 전처리에 대한 것은? 이런 의문은 들었지만 솔직히 해시 테이블이나 해시 맵을 떠올리지 못했고 뭔가 중요한 또 하나를 배운 것 같은 마음이 더 컸다.

 

아무튼 이렇게 떠오른 김에 다시 한번 알아보는 시간을 가졌다.

 

Hash Table

1. 데이터 저장/검색에 주로 사용 - 해시 테이블은 Key,Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 때문에 해당 책에서 분산하여 데이터를 서버에 나눠서 저장하고 해당 서버에서 가져온다고 할 때 해시 테이블을 사용하고, 유투브에서 동영상의 중복 여부등을 판단할때도 사용한다고 한다.

이럴수 있는 이유는 사용되는 해시함수는 큰 데이터를 동일한 크기의 해시 키 값으로 변경하며, 이 키의 사이즈는 크지 않기 때문이다.

 

2. hash collision - 하지만 동일한 키 값으로 변경함으로써, 무수히 많은 데이터를 저장하다보면 중복되는 경우가 발생하는데 이게 해시충돌(Hash Collision)이다.

해결 방법으로는 크게 open addressing과 seprate chaining 두가지로 나눌 수 있다.

1) open addressing

원래라면 해시함수로 얻은 해시값에 따라서 데이터와 키값을 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 하는 기법

 

 

위에서 살펴본 동일한 충돌에 대해서 이번엔 체이닝 방식을 적용하지 않고 그 다음으로 비어있는 주소인 153 에 저장하는 것을 볼 수 있다. 이러한 원리로 탐색, 삽입, 삭제가 이루어지는데 다음과 같이 동작한다.

• 삽입: 계산한 해시 값에 대한 인덱스가 이미 차있는 경우 다음 인덱스로 이동하면서 비어있는 곳에 저장한다. 이렇게 비어있는 자리를 탐색하는 것을 탐사(Probing)라고 한다.
• 탐색: 계산한 해시 값에 대한 인덱스부터 검사하며 탐사를 해나가는데 이 때 “삭제” 표시가 있는 부분은 지나간다.
• 삭제: 탐색을 통해 해당 값을 찾고 삭제한 뒤 “삭제” 표시를 한다.

해당충돌 기법으로는 선형탐사(Linear Probing, 제곱탐사(Quadratic Pronbing), 이중해싱(Double Hashing)이 있다.

 

2) Separate Chaining

open addressing과 다르게 추가적인 메모리를 사용해 동일한 버킷에 값이 있으면 링크드 리스트로 해당 value를 뒤에 저장하는 방법.

일반적으로 Open Addressing 은 Separate Chaining 보다 느리다. Open Addressing 의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case 에 가까워 지는 빈도를 줄일 수 있다. Java 7 에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다. Separate Chaining 방식으로는 두 가지 구현 방식이 존재한다.

 

Open Address vs Separate Chaining

일단 두 방식 모두 Worst Case 에서 O(M)이다. 하지만 Open Address방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다. 따라서 데이터의 개수가 충분히 적다면 Open Address방식이 Separate Chaining보다 더 성능이 좋다. 한 가지 차이점이 더 존재한다. Separate Chaining방식에 비해 Open Address방식은 버킷을 계속해서 사용한다. 따라서 Separate Chaining 방식은 테이블의 확장을 보다 늦출 수 있다.

보조 해시 함수

보조 해시 함수(supplement hash function)의 목적은 key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다. Separate Chaining 방식을 사용할 때 함께 사용되며 보조 해시 함수로 Worst Case 에 가까워지는 경우를 줄일 수 있다.

 

해시 버킷 동적 확장(Resize)

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다. 그래서 HashMap 은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다. 또 애매모호한 '일정 개수 이상'이라는 표현이 등장했다. 해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor 라고 불린다.

 

 31을 승수로 한다.

 

 

출처: wikiepedia hash table separate chaining

출처 - https://mangkyu.tistory.com/102

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