알고리즘 9장 - 해쉬 알고리즘(1) -

알고리즘 9장

- 해쉬 알고리즘(1) -

 

Direct-address tables 는 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식이다. 이 때 중복되는 key는 없다고 가정한다. 이는 데이터를 저장하는 방식인데 전체 크기가 U인 곳에서 actual key인 K가 존재한다고 생각한다. 해당되는 데이터를 table에 저장하고 table에서 필요한 key 값과 그에 해당하는 data를 확인하는 자료구조이다.

Direct-address tables을 사용하게 되면 수행시간이 매우 짧다는 장점이 있다. 우리가 알고자 하는 data의 key 값을 알고 있으면 table을 통해 바로 원하는 data를 찾을 수 있기 때문이다. 이에 해당하는 Pseudo code는 다음과 같다.

하지만 이런 방식이 공간 복잡도 측면에서는 매우 좋지 않다. 우리가 table을 설계할 때 U정도에 해당하는 크기의 data 수들이 들어온다고 생각하고 만든다. 하지만 실제로 table에 들어오는 데이터는 U만큼이 아니고 원하는 key에 해당하는 값들만 들어오게 된다. 따라서 실제 공간 사용을 전체 공간으로 나눈 K/U (key 값들의 수/전체 크기)가 적재율에 해당하게 된다. 만약 적재율이 낮다면 실제로 대부분의 공간이 낭비되고 있다는 것을 말하게 된다.

Hashing은 key k를 저장할 때 slot k에 저장하는 것이 아니라 slot h(k) 에 저장하는 것을 의미한다. 이것을 key k가 slot h(k)로 해쉬 되었다고 하며 h(k)를 key k의 해쉬 값이라고 부른다. 이 때 h()를 해쉬 함수라고 부른다. 해쉬 함수는 임의의 크기의 data를 받아서 고정된 크기의 data로 만들어준다. actual key들에 대해서 해쉬 함수를 통해 table에 저장하게 된다. 이렇게 되면 동일한 hash 값을 가질 수 있게 되고 이는 하나의 공간에 저장될 수 있게 된다. 이는 충돌 문제를 야기 시킨다.

Hash table의 경우 충돌 문제가 발생할 수 있다. 두 개의 key가 동일한 hash 값을 갖는 경우 충돌이 발생했다고 한다. 충돌을 피하는 방법은 충돌이 적은 좋은 해쉬 함수를 사용하는 것이다. 하지만 테이블의 크기가 해쉬 함수의 치역 영역보다 크다면 충돌을 피하는 것은 매우 어렵다. 따라서 중복되는 key 값이 있을 경우 해당 슬롯을 연결리스트로 저장한다. 그러면 하나의 공간에 리스트의 형태로 존재하므로 충돌에서 벗어날 수 있다.

하지만 이럴 경우 시간 복잡도 측면에서 문제가 발생할 수 있다. 하나의 table 공간에 많은 k에 대한 해쉬 값들 들어가게 되면 아주 긴 리스트가 존재하게 된다. 이에 대해 자신의 key가 맞는지를 계속 찾아 들어가야 한다. 이는 hash table을 사용하는 이점을 없애는 것이 된다.

그러면 어떤 해쉬 함수가 좋을까? 좋은 해쉬 함수는 simple uniform hashing을 만족하는 해쉬 함수이다. 각각의 key는 중복 없이 m개의 slot으로 동일한 확률로 해쉬되며 각각의 key는 다른 key 값의 해쉬값과 관계없이 해쉬 되는 경우이다. 즉 모든 값이 골고루 나오게 하는 것이다. m개의 slot이 있으면 중복 없이 확률적으로 m개의 slot에 골고루 나누어지는 것이 좋은 경우이다.

해쉬 함수로 사용하는 대표적인 방법이 나눗셈 방법이다. 해쉬 함수로 나눗셈을 이용하는 방법으로 키값 k를 m으로 나누고 나머지를 이용하여 h(k) 값을 나타내어 주는 것이다. 여기서 m을 잡는 것이 매우 중요하게 되는데 2의 지수 승을 피하는 것이 좋다. 일반적으로 소수를 잡는 것이 효율적이라고 할 수 있다.