해시

안녕하세용

오늘부터 프로그래머스 코딩테스트 고득점 kit 부분을 하나씩 정리해나가겠습니당 !

코테 공부는 이것부터 시작하면 된다는게 맞나욤 •••

 

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit 

프로그래머스

 

 

각설하고 ...

 

해시(Hash)

 해시는 데이터를 다루는 기법 중의 하나로, 검색과 저장을 아주 빠르게 하는 자료구조입니다.

데이터를 저장할 때 key-value 형태로 데이터가 존재하고, key 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어납니다.

 

먼저 그림을 살펴보겠습니다. 

 

사람 이름이 key로 들어가 있는데, 이 key에 해당하는 임의 길이의 string을 hash 함수에 input으로 넣으면 01, 02, 04 ... 와 같이 "고정된 길이의 int 데이터"로 변환되는 것을 볼 수 있습니다. 여기까지가 hash function의 역할입니다. 위에서 말했던 "임의 길이 데이터를 암호화된 고정 길이 데이터로 전환하는 함수"인 것입니다.

 

또 다른 그림을 통해서도 살펴보겠습니다.

 

 buckets 라고 하는 칸에는 key 인 사람의 전화번호가 들어 있습니다. 해시 테이블에서는 bucket은 key에 해당하는 데이터입니다. 여기서 착각하면 안되는게, 이 bucket에 들어가는 데이터는 hash function 과는 아무런 상관이 없습니다. 그냥 원래 우리가 배열에 넣고 싶었던 데이터입니다. 따라서 뭔가 변환하고 이런 것 없이 곧장 넣습니다. 

 

즉, key 값을 hash function에 넣어 얻은 hash value를 배열의 인덱스로 쓰는 테이블을 우리는 hash table 이라고 합니다. 그런 면에서 보다 이해하기 쉬운 해시테이블의 정의는 다음과 같습니다.

 

Hash table : key를 hash function에 넣어 얻은 hashed를 index로 value 데이터와 매핑하는 array 형태의 자료구조

 

 이 때 해시 함수는 Key 값을 고정된 길이의 hash로 변환하는 역할을 하고, 이렇듯 해시 함수에서 key 값을 hash로 변환하는 과정을 해싱(hashing)이라고 합니다. 해시 함수에서 Key 값을 해싱 과정을 통해 해시 값(hasg value) 또는 해시 코드(hash code)로 변경하며 이 해시 값이 저장위치가 됩니다.

 

 서로 다른 key가 같은 해시가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요합니다.

 

해시 테이블(Hash Table)

 해시 테이블은 연관 배열구조를 이용하여 데이터를 key 와 value 로 저장하는 자료구조입니다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산합니다.

 

✔️ 연관 배열 구조
 자료구조의 하나로, 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있습니다.

✔️ 연관 배열은 일반적으로 다음의 명령을 지원합니다.

• 키와 값이 주어졌을 때, 연관 배열에 그 두 값을 저장하는 명령
• 키가 주어졌을 때. 연관되는 값을 얻는 명령
• 키와 새로운 값이 주어졌을 때, 원래 키에 연관된 값을 새로운 값으로 교체하는 명령
• 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 명령

 

즉, 키 값이 있을 때, 해시 함수를 통해서 데이터를 바꾸어 버킷에 저장합니다.

특징

 

연산의 (평균)시간복잡도가 O(1)으로, 매우 빠르게 값을 찾아낼 수 있다.

 

그렇다면 어떻게 평균 시간 복잡도가 O(1)이 나올 수 있을까요? 해시 테이블에 우리가 입력한 key에 대응하는 bucket을 찾는 과정을 살펴봅시다. 

 

1) 해시 함수에 key를 입력해 해시 값을 받아내는 과정 ([key] -> [hasg func] -> [hash==h(key)]) : O(1)

 

 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱(Hashing)이라고 합니다. 가장 단순한 해싱 알고리즘 중 하나로 정수형 해싱 기법인 모듈러를 예시로 들어봅시다. 모듈러 함수는 나머지를 연산하는데 이로 부터 해싱 인덱스를 뽑아냅니다. 예를 들어 John Doe를 해싱 함수에 넣는다고 해봅시다. 먼저 John Doe를 함수 내부적으로 정한 규칙에 따라 정수로 바꿉니다. 그 다음, 내부적으로 정한 특정 값(보통 2의 멱수에 가깝지 않은 소수)으로 이 수를 나눈 나머지를 구합니다. 이 나머지 값이 hash index가 됩니다. 

 

이 과정은 나머지 연산만 하면되므로 시간복잡도가 O(1)입니다.

 

2)테이블에서 해당 인덱스로 이동하는데 걸리는 시간 : O(1)

 

 array 의 가장 큰 장점 중 하나는 특정 인덱스를 찾는데 걸리는 시간이 O(1)이라는 점입니다. 예를 들어 우리가 14번째 bucket을 찾는다고 했을 때. 00번째 index에 +14만 해주면 됩니다. 여기서는 앞에서 살펴보았듯 key와 hash index가 대응하므로 hash 연산만 돌리면 곧바로 bucket의 index를 찾아낼 수 있습니다. 그러니 전체적으로 해시 테이블에서 bucket 데이터를 찾는데 걸리는 시간이 O(1)입니다. 

 

 

이와 동일한 로직으로, search, insert, delete 에 걸리는 평균 시간복잡도는 O(1)이 됩니다. 공간이야 array 형태이기 때문에 데이터 수에 비례하는 O(n)입니다. 그런데 최악의 경우 왜 search/insert/delete의 worst case가 O(n)일까요?

 

바로 충돌(collision) 때문입니다.

 

충돌(Collision)

서로 다른 key에 대해 동일한 hash 값(index)가 부여되는 상황

 

 앞서 해시 충돌에 관해 언급하였습니다만, hash collision 이란 서로 다른 문자열이 해시 함수를 통해서 해싱한 해시 값이 중복인 경우를 말합니다. 충돌이 많아질 수록 시간 복잡도가 O(1)에서 점점 O(n)에 가까워집니다. 그렇기 때문에 충돌을 줄여주는 해시 함수를 사용하는 것이 좋습니다.

 

 

그렇다면 충돌은 어떻게 줄일 수 있을까요?

 

충돌을 해결해주는 방법은 크게 2가지가 있습니다.

1. Separating Chaining - LinkedList, Tree(Red-Black Tree)
2. Open addressing - Liniear Probinf, Quadratic Probing, Double hashing

* Red Black Tree가 궁금하다면 .. https://minzzl.tistory.com/55

 

Separating Chaining

충돌 발생 시 동일한 hash index에 다른 value를 연결리스트로 연결해 충돌을 해결하는 방법

 

 JDK 내부에서 사용하는 충돌 처리 방식으로, LinkedList를 사용하는 방식입니다. LinkedList 뿐만 아니라 Tree(Red-Black Tree)를 사용하기도 합니다. 두개의 기준은 data가 6개 이하면 Linked list를, 8개 이상이면 tree를 사용합니다. 만일 7개일 경우 데이터를 삭제하게 되면 LinkedList로 바꿔야하고, 추가되면 tree로 바꿔야합니다. 이 때 바꾸는데 오버헤드가 있어서 기준이 6과 8이 되는 것입니다.

 

 

가장 일반적인 충돌 해결 방식으로, 보통 해시 테이블이라 하면 이 형태를 뜻합니다. 이를 구현하는 방식은 아래와 같습니다.

 

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 만약 같은 인덱스가 있다면 연결리스트로 연결한다.

 

 LinkedList를 사용할 경우, 인덱스 충돌이 났을 때 인덱스가 가리키고 있는 LinkedList에 노드를 추가하여 삽입합니다. 데이터를 탐색할 때는 키에 대한 인덱스가 가리키고 있는 LinkedList를 선형 검색하여 해당 키에 대한 데이터를 반환합니다. 삭제하는 것 또한 비슷하게 키에 대한 인덱스가 가리키고 있는 Linked List에서 그 노드를 삭제합니다. Separating Chaining 방식은 LinkedList 구조를 사용하기에 추가할 수 있는 데이터수의 제약이 작습니다.

 

아까 위에서 search/insert/delete에 걸리는 평균 시간 복잡도는 O(1)이라고 했습니다. 이는 하나의 index에 여러개의 데이터가 연결리스트로 늘여져있는 것이 아니라, 값이 고르게 분산된 경우입니다.

 

O(n)이 나올 때는 언제일까요? 극단적으로 위의 글미에서 모든 데이터가 하나의 index에 줄줄이 연결리스트로 연결되어 있는 경우입니다. 이 경우에는 연결리스트 내에서는 O(N)으로 하나하나 값을 체크해가며 값을 찾아야합니다. 그러니 최악의 케이스는 O(N)입니다. 아까 JDK에서는 red-black tree를 이용한다고 했습니다만, 이를 활용하여 탐색/삽입/삭제에 걸리는 최악의 시간 복잡도를 O(N)에서 O(logN)으로 급격히 줄어들게했습니다. 

 

 

Open Addressing

충돌 발생 시 테이블 공간을 탐사해 빈 공간을 찾아나서는 방식

 위의 개별 체이닝 방식은 버킷의 크기에 상관없이 연결리스트에 데이터를 줄줄이 달아놓음으로써 무한정으로 저장할 수 있지만, 오픈 어드레싱은 전체 테이블 내 슬롯 개수 이상을 저장이 불가능합니다. 즉, 인덱스에 대한 충돌 처리에 대해서 LinkedList와 같은 추가적인 메모리를 사용하지 않고, Hash Table Array 의 빈공간을 사용하는 방법입니다. 추가적인 메모리 공간을 사용하지 않기 때문에 Separate Chaining 방식에 비해 메모리를 덜 사용합니다.

Linear Probing, Quadratic Probing, Double hashing 등이 있습니다.

 

오픈 어드레싱을 구현하는 대표적인 방법은 선형탐사(Linear Probing)입니다. 이는 충돌이 발생하면 해당 위치부터 순차적으로 탐사를 하나씩 진행합니다. 만약 특정 위치에 이미 값이 선점되었다면 바로 그 다음 위치를 확인합니다. 그렇게 한 칸씩 이동하며 선형적으로 찾다가 빈 공간을 발견하면 그 자리에 삽입합니다. 

 

ex)

 

인덱스가 중복되는 충돌이 발생할 때 인덱스 뒤에 있는 버킷 중 빈 버킷을 찾아 데이터를 삽입합니다. 그림의 경우 Sandra의 키 앖은 152을 가리킵니다. 하지만 John과 충돌이 나기 때문에 그 다음인 153에 삽입합니다. 

 

Linear Probing 방식에서의 탐색은 Sandra의 키에 대해서 검색하면 index가 152이기 때문에 key 가 일치하지 않기에 뒤의 index에서 key가 없을 때까지 검색을 진행합니다. 삭제는 더미 노드를 넣어서 검색할 때 다음 인덱스까지 검색을 연결해주는 역할을 해워야합니다. 그렇기 때문에 삭제가 어렵습니다.

 

하지만 open addressing 또한 문제점이 있습니다. 바로 clustering 입니다.

클러스터링이란, 해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 현상을 뜻합니다. 뭉치는게 왜 문제일까요? 클러스터가 점점 커지면 근처에 있는 클러스터와 서로 합치는 일이 일어나는데, 이러면 해시 테이블에 데이터가 한쪽으로 편중되고 다른 쪽에는 데이터가 거의 없습니다. 이렇게 클러스터링 현상이 생기면 탐사시간이 오래걸립니다. linear probing 방식으로 데이터를 삽입하면 해당 키에 접근한다고 해서 한번 만에 우리가 원하는 데이터를 찾을 수 없습니다. 해당 키에 대응하는 데이터를 기준으로 선형적으로 한칸씩 내려오면서 쭉 찾아야하는데, 이 과정이 길어질 수록 효율이 떨어집니다. 

 

또한 오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 데이터를 삽입할 수 없습니다. 오픈 어드레싱은 무조건 빈 버킷에 데이터를 하나씩만 삽입하는 방식이기 때문입니다. 따라서 기준이 되는 load factor 비율을 넘어서면 정해놓은 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 뒤 새 버킷에 복사하는 리해싱이 필요합니다.

 

리사이징(resizing)

 

Separate Chaning 의 경우, 버킷이 일정 수준으로 차버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에 검색성능이 떨어지게 되므로 버킷의 개수를 늘려줘야합니다. 또한  open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장시킬 필요가 있습니다.

이렇듯 확장 시키는 것을 resizing이라고 합니다.

 

보통 두 배로 확장하는데, 확장하는 임계점은 현재 데이터 개수가 해시 버킷 개수의 75%가 될 때입니다. 0.75라는 숫자는 load factor라고 불립니다. 리사이징은 더 큰 버킷을 가지는 array를 새로 만든 다음, 기존 array의 hash를 다시 계산해서 복사해줘야합니다.

 

 

언어별 해시 테이블 구현 방식

 

파이썬에서는 자료구조 중 딕셔너리가 해시 테이블로 구성되어 있습니다. 그렇다면 파이썬은 충돌 시 어떤 방식으로 해결할까요? 파이썬에서는 오픈 어드레싱으로 해결합니다. 가장 보편적인 방법이 오픈 어드레싱입니다.

 

언어	방식
C++	개별 체이닝
Java	개별 체이닝
Golang	개별 체이닝
루비	오픈 어드레싱
Python	오픈 어드레싱

 

* 다음의 글을 참고하여 작성하였습니다.

https://woonys.tistory.com/entry/%ED%95%B4%EC%8B%9CHash-%EA%B0%9C%EB%85%90-%EC%A0%95%EB%A6%ACFeat-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B8%ED%84%B0%EB%B7%B0

https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C