Hash Key 생성 : Hornor's Method 활용

Hash Key 생성

기본적으로 파이썬은 Hash를 이용한 딕셔너리라는 자료구조를 제공한다. 이 때, 단순히 하나의 값으로 Hash를 생성할 때는 크게 생각을 하지 않아도 된다. 이를 테면 "AB" 같은 것들은 훌륭하게 Hash Key로 사용할 수 있다. 그런데 Key로 사용되어야 할 값이 복잡해지면 고민이 생기기 시작한다. 어떻게 키를 만들지? 

이런 저런 방법이 있을 수 있는데, 나는 이전에는 주어진 문자열을 join 메서드로 붙인 값을 key로 사용해서 값을 넣어주곤 했다. 그런데 Hash에 사용할 Key를 생성할 때, 좀 더 효율적으로 사용할 수 있는 방법이 있다. 바로 Hornor's Method다. 

 

Hornor's Method 활용

한 가지 예를 들어보자. 알파벳 소문자(a-z)만 등장하는 문자열이 있다고 해보자. 이 문자열을 그냥 써도 되겠지만, 굳이 hornor's Method를 활용해서 만들 수 있다. a-z의 문자는 총 26개다. 즉, a~z를 각각 1~26으로 대입할 수 있고, 26진법으로 표현할 수 있게 된다. 

이제 위 정보를 바탕으로 Hash Key를 만들어야 한다. Hash Key의 가장 중요한 방법은 Hash Key가 충돌이 되면 안된다는 것이다. 따라서 충돌없이 Hash Key를 만들기 위해 "현재 진법 + 1"의 진법을 기준으로 각 자리 수를 표현하면 충돌없는 Hash Key를 만들 수 있다. 

예를 들어 abcd라는 문자열은 다음과 같이 Hash Key를 생성할 수 있다. a=1, b=2 등등에 대응시키고 각각의 자릿수를 27진법으로 표현해서 Hash 값을 구하는 것이다. 

 

Hornor's Method + Bucket 활용

파이썬의 딕셔너리는 Linear Proving 방식을 사용한다고 한다. 이런 방식으로 Chaining 보다는 속도가 떨어진다고 한다. 따라서 보다 나은 속도 개선을 위해 Hornor's Method + Bucket을 활용해서 Chaining 형식으로 Hash Table을 구현할 수 있다. 

다음과 같은 방식으로 직접 구현할 수 있다. Hash Value는 유니크하다. 그렇지만 모든 Hash Value에 대해 메모리 공간을 할당하는 것은 비효율적이다. 따라서 메모리 최적화를 위해 Bucket을 소수만 만들고, 각 Hash Value가 어떤 Bucket에 들어갈지를 정해서 Linked List형태로 달아주면 된다. 

 

기타

개수가 고정되어 있을 때, 수의 범위를 0부터로 맞춰주고 (max 값 + 1) 진법 변환

• -100 ~ 100 범위의 1개 정수
• 0~100 범위의 4개 정수
• -100 ~ 100 범위의 3개 정수 
• 소문자 10자리 

개수가 고정되지 않을 때, 수의 범위를 1부터로 맞춰주고 (max 값 + 1) 진법 변환

• 소문자 4~10자리
• 대소문자 4~10자리