#14 해싱(Hashing)

#14 해싱(Hashing)

1. 해싱(Hashing)

해싱은 데이터를 키:값의 쌍으로 구성하여 배열에서 인덱스로 데이터를 참조하듯 키로 데이터에 바로 접근할 수 있도록 하기위해

고안된 방식이다. 해시 함수(Hash Function)를 사용하여 키 값을 특정한 길이의 해시값으로 변환하고 이 해시값에 해당하는

위치에 데이터를 저장하는 것으로 삽입, 삭제, 탐색에 O(1)에 가까운 성능을 보이도록 한다. Python의 dictionary 나 Java의

HashMap, HashTable 과 같이 대부분의 언어에서 내장 라이브러리로 지원하며 굉장히 자주 사용되는 유용한 방식이다.

2. 용어

버킷(Bucket) : 해시 함수로 얻은 해시 값을 주소로 하는 저장 공간. 해시 방식은 미리 지정된 갯수만큼의 버킷을 만들어두고

데이터를 저장해나간다.

: 해시 함수로 얻은 해시 값을 주소로 하는 저장 공간. 해시 방식은 미리 지정된 갯수만큼의 버킷을 만들어두고 데이터를 저장해나간다. 슬롯(Slot) : 버킷이 데이터 하나를 저장하기 위해 사용하는 공간.

: 버킷이 데이터 하나를 저장하기 위해 사용하는 공간. 충돌(Collision) : 서로 다른 키 값에 대해 해시 함수로 얻은 해시 값이 서로 동일한 경우, 즉 같은 버킷에 다수의 데이터를

저장해야하는 상황을 의미한다.

: 서로 다른 키 값에 대해 해시 함수로 얻은 해시 값이 서로 동일한 경우, 즉 같은 버킷에 다수의 데이터를 저장해야하는 상황을 의미한다. 클러스터링(Clustering) : 연속된 주소를 가진 버킷에 데이터가 밀집되는 현상을 의미한다.

: 연속된 주소를 가진 버킷에 데이터가 밀집되는 현상을 의미한다. 부하율(Load Factor) : 전체 버킷 중 사용중인 버킷의 비율을 의미한다.

3. 해싱의 특징

삽입, 삭제, 탐색에 평균적으로 O(1)의 성능을 보인다.

해시 함수의 특성상 언젠가 충돌이 반드시 발생하며 그럴수록 성능이 저하되기 때문에 해시 함수가 얼마나

충돌이 일어나지 않도록 해시 값을 생성하느냐에 따라 성능이 크게 좌우된다.

4. 충돌(Collision) 의 처리

① 체이닝(Chaining) 기법

같은 해시 값을 가지는, 즉 같은 버킷에 저장해야할 데이터들을 연결 리스트의 형태로 이어붙이는 방식

비교적 구현이 간단하고 연결리스트를 사용하기 때문에 슬롯 갯수의 제약이 없다.

클러스터링 에 영향을 거의 받지 않기 때문에 해시 함수를 선정할 때 충돌의 최소화만을 중점적으로 고려할 수 있다.

에 영향을 거의 받지 않기 때문에 해시 함수를 선정할 때 충돌의 최소화만을 중점적으로 고려할 수 있다. 충돌이 많이 발생할 경우 최악의 경우 O(N) 수준까지 성능이 저하될 수 있다.

하나의 버킷의 슬롯 갯수가 일정 이상으로 늘어나면 연결 리스트 대신 이진 트리를 사용하여 검색효율을 높이기도 한다.

부하율 이 높아져도 성능 저하가 선형적으로 발생하기 때문에 높은 부하율이 예상될수록 개방주소기법에 비해 성능이 좋다.

이 높아져도 성능 저하가 선형적으로 발생하기 때문에 높은 부하율이 예상될수록 개방주소기법에 비해 성능이 좋다. 처음에 얻은 해시주소 내에서 문제를 해결하기 때문에 폐쇄 해싱(Closed Hashing)이라고도 한다.

② 개방주소(Open Addressing) 기법

충돌이 발생할 경우 다른 비어있는 버킷을 찾아 데이터를 삽입하는 방식

체이닝 기법과 달리 추가적인 메모리나 외부 자료구조에서의 작업을 필요로하지 않는다.

연결리스트나 트리 등 외부 자료구조를 사용하지 않기 때문에 삽입/삭제의 오버헤드가 적어 저장할 데이터가 적다면

체이닝 기법보다 좋은 성능을 보인다.

체이닝 기법보다 좋은 성능을 보인다. 저장해야할 데이터가 많아져서 부하율이 일정 이상으로 증가하면 체이닝에 비해 성능이 급격히 저하된다.

비어있는 버킷을 찾는 방식으로 선형 탐색 , 제곱 탐색 , 이중 해싱 이 있다.

, , 이 있다. 선형 탐색 은 말그대로 선형적으로 다음 버킷을 참조해나가며 빈 버킷을 찾는 방식이다.

은 말그대로 선형적으로 다음 버킷을 참조해나가며 빈 버킷을 찾는 방식이다. 제곱 탐색 은 처음 얻은 해시 값에서 제곱수만큼씩 증가해나가며 빈 버킷을 찾는 방식이다.

은 처음 얻은 해시 값에서 제곱수만큼씩 증가해나가며 빈 버킷을 찾는 방식이다. 이중 해싱은 처음 얻은 해시 값이 충돌을 일으킬 경우 2차 해시 함수를 사용하여 다시한번 해시 값을 얻는 방식이다.

가장 많은 연산을 필요로하지만 클러스터링의 영향을 거의 받지 않는다.

※ 클러스터링에 취약하다는 것은 반대로 참조 지역성(Locality of Reference)이 높다는 의미가 되기 때문에

캐싱 성능이 좋아진다. 그렇기 때문에 선형탐색 -> 제곱 탐색 -> 이중 해싱 순으로 클러스터링 방지는 잘 되지만

참조 지역성이 낮아져 캐싱 성능은 떨어진다. 체이닝 기법의 경우에도 클러스터링의 영향을 거의 받지 않기 때문에

참조 지역성이 낮아 선형탐색을 통한 개방주소 기법에 비해 캐싱 성능이 떨어진다.

5. 리사이징(Resizing) & 재해싱(Rehashing)

부하율 이 높아져 성능이 저하되는 것을 방지하기 위해 기존보다 더 많은 버킷을 할당한 뒤 기존에 저장된 데이터들을

새로운 공간간에 다시해싱하는 작업

이 높아져 성능이 저하되는 것을 방지하기 위해 기존보다 더 많은 버킷을 할당한 뒤 기존에 저장된 데이터들을 새로운 공간간에 다시해싱하는 작업 개방주소법의 경우 삭제 시 발생하는 더미 데이터 등으로 인한 성능저하 문제도 있기 때문에 주기적인 재해싱을 해줘야

성능을 유지할 수 있다.

from http://scala0114.tistory.com/142 by ccl(A) rewrite - 2021-10-26 17:27:51