[Study] Hash Algorithm
Intro
‘코드업'이나 ‘백준'에서 일주일에 일정량의 문제를 풀어나가는 스터디를 진행했다. 스터디를 진행해 나아가면서 어려운 문제에 접근할 때 어떤 알고리즘으로 접근을 하고 해석을 해야하는지 감이 잡히지 않았다.
그래서, 일주일마다 하나의 알고리즘을 공부하고 관련된 문제를 풀어나가는 스터디를 진행하기로 했다.
처음 공부할 알고리즘은 ‘해시 알고리즘 (Hash Algorithm)’이다.
- What is ‘Hash Algorithm’
해시 함수란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어에 널리 사용된다고 한다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 DB 검색이나 테이블 검색의 속도가 빠르다.
- Direct Addressing Table
key-value 쌍의 데이터를 배열에 저장할 key 값을 직접적으로 배열의 인덱스로 사용하는 방법이다. 똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에 각 key마다 자신의 공간이 존재하므로 그 위치에 저장을 한다. 삭제 시에는 해당 키의 위치에 NULL 값을 넣어준다. 탐색 시에는 해당 key의 위치를 그냥 찾아가서 참조하면 된다.
데이터의 key만 알고 있으면 즉시 위치를 찾는 것이 가능하기 때문에 탐색, 저장, 삭제, 갱신은 모두 선형시간인 O(1)로 빠른 속도로 처리가 가능하다. 하지만, key 값의 최대 크기만큼 배열이 할당되기 때문에 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다.
- Hash Table
Direct Addressing Table과 달리 key값을 함수를 이용해 계산한 후, 그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key 값을 계산하는 함수를 Hash Function이라고 부르며, Hash Function은 입력으로 key를 받아 0부터 배열의 크기 -1 사이의 값을 출력한다. 이 경우 k 값이 h(k)로 Hash되었다고 하며, h(k)는 k의 Hash 값이다.
> 충돌 (Collusion)
Hash Table은 충돌이 일어날 수 있다는 문제점이 존재한다. 다른 k값이 동일한 h(k) 값을 가져 동일한 slot에 저장되는 경우를 말한다.
> 충돌 최소화 방법
— Chaining Method
데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, Hash Table에서 동일한 Hash 값이 출력되어 충돌이 일어나면 그 위치에 있던 데이터에 key 값을 포인터로 뒤이어 연결한다.
따라서 최초로 h(k) 위치에 저장된 데이터를 시작으로 그 이후의 h(k) 값이 출력되는 데이터는 모두 연결 리스트의 형태를 취한다.
— Simple Uniform Hash
충돌이 적은 좋은 Hash Function을 만드는 방법이다.
- 계산된 Hash 값들은 0부터 배열의 크기-1 사이의 범위를 동일한 확률로 골고루 나타낼 것
- 각각의 Hash 값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것
— Division Method
Modular 연산 방법을 이용하는 Hash Function인데, 특정 key를 어떤 수로 나눈 나머지를 Hash 값으로 사용한다.
- Open Addressing
key 값을 테이블에 저장하는 Direct Addressing Table과는 다르게 모든 데이터 (key + Data)를 테이블에 저장하는 방법이다. 장점은 데이터를 직접 모두 읽어오기 때문에 포인터를 쓸 일이 없어 오버헤드를 방지할 수 있다. 포인터가 필요 없어 구현이 훨씬 용이하고 포인터 접근에 필요한 시간이 없어 큰 성능 향상을 이끌었다.
> 충돌 최소화 방법
Open Addressing은 포인터를 사용하지 않기 때문에 Chaing 방법은 사용 불가능하다.
— Liner Probing
key 값으로 인덱스를 계산할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음 인덱스에 저장한다. 즉, 충돌이 일어나지 않을 때까지 다음 인덱스로 이동하여 빈 공간을 찾아 저장하는 방식이다.
구현이 용이하지만 Primary Clustering이라는 문제점을 갖고 있다. 충돌이 나면 뒤 slot에 데이터를 넣어 하나의 데이터 덩어리를 이루기 때문에 데이터들이 특정 위치에만 밀집하는 현상을 말한다. 이 현상으로 slot이 많아지면 많아질수록 탐색 시간이 엄청나게 증가한다.
— Quadratic Probing
Primary Clustering을 방지하기 위해 Hash Function을 2차식의 형태로 만드는 것이다. Liner Probing과는 달리 2차식의 형태를 취해 한칸씩 이동하지 않고 여러칸(c1 * i + c2 * i²) 만큼 이동한다.
Secondary Clustering이라는 문제점을 가지고 있는데, 처음 시작 Hash 값이 같을 경우 그 이후의 Hash 값들 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나는 것을 말한다.
— Double Hashing
Secondary Clustering을 해결하기 위해 사용하는 방법이다. Hash Function을 2가지로 구성하는 것이다.
- 참고자료
> 해시 함수
