Hashing
Hashing이란 임의의 길이의 값을 해시 함수(Hash function)을 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.
해시는 다양한 목적으로 사용될 수 있지만, 주로 다음과 같은 용도로 사용된다.
- 해시 테이블을 이용한 탐색
- 암호화 : 해시를 통해 변환된 데이터는 원본의 모습을 알아볼 수 없을 정도로 완전히 달라지므로, 이를 이용해 암호화라를 진행한다. SHA(Secure Hash Algorithm)알고리즘이 그 대표적인 예이다.
- 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이 특성을 이용하면 커다란 데이터를 '해시'하면 짧은 길이로 축약할 수 있다. 이렇게 축약된 데이터끼리 비교를 수행하면 커다란 원본 데이터들을 비교하는 것에 비해 엄청난 효율을 거둘 수 있다.
Hash Table
해시 테이블은 (Key, Value) 형태로 데이터를 저장하는 자료구조 중 하나로 빠른 데이터 검색을 위해 쓰인다.
테이블은 각각의 Key값에 해시 함수를 적용 해 배열의 고유한 index를 생성하고, 이 index를 활용 해 값을 저장하거나 검색하게 된다.
예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자.
hash function을 통해 index 값을 계산하고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.
이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 따라서 해시테이블의 평균 시간복잡도는 O(1)이다.
그러나 Hash Table은 순서가 있는 배열에서는 사용할 수 없고, Hash function의 의존도가 높은 단점이 있다.
Hash Function
Hashing을 할 때 사용되는 함수를 Hash function이라고 부른다. 이 때 사용되는 함수로는 다음과 같은 방법들이 있다.
- Division Method : 해시 값을 입력값 % 테이블의 크기로 구한다. 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
- Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법
ex) 8129335 = 8 + 1 + 2 + 9 + 3 + 3 + 5 = 31
Hash 충돌
해시 테이블을 사용하기 위해 데이터들을 해시값으로 변환하다 보면, 서로 다른 데이터에 대해 같은 해시 값을 갖는 경우가 발생할 수 있다. 이를 충돌(Collision)이라고 한다.
어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못하지만, 최대한 이를 해결하기 위한 두 가지 방법이 있다.
첫 번째는 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 개방 해싱(Open Hashing)이고, 또 다른 하나는 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결하는 폐쇄 해싱(Closed Hashing)이다.
분리 연결법(Separate Chaining)
Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 해시값을 갖는 경우, 연결 리스트를 이용하 데이터들을 연결을 해서 관리한다.
이러한 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.
개방 주소법(Open Addressing)
Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하는 방법은 다음과 같다.
- Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
- Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
- Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.
장점으로는 또 다른 저장공간에서의 추가적인 작업 없이 해시 테이블 내에서 저장 및 처리가 가능하다는 점이 있고, 단점으로는 해시 함수의 성능에 전체 해시 테이블의 성능이 좌지우지 되는 단점이 있다.
출처
'Computer Science > 알고리즘, 자료구조' 카테고리의 다른 글
| Heap과 Priority Queue (0) | 2023.04.03 |
|---|---|
| 탐색 알고리즘 (0) | 2023.04.01 |
| 그래프와 탐색 (0) | 2023.04.01 |
| 시간 복잡도 (0) | 2023.03.31 |
| 자료구조 - Tree, Binary Tree (0) | 2023.03.31 |
