[알고리즘] 해싱(Hashing) - 3

해싱(Hashing) - 3

그렇다면 좋은 해시 함수란 무엇일까

현실에서 키 들은 랜덤 하지 않다. 

따라서, 만약 키 들의 통계적 분포에 대해서 알고있다면 

이를 이용해서 해시 함수를 고안 하는것이 가능하겠지만 현실적으로 어렵다.

그러므로, 키 들의 어떤 특정한(가시적인) 패턴을 가지더라도 

해시 함수의 값이 불규칙 적이 되도록하는것이 바람직하다.

즉, 해시 함수의 값이 키의 특정 부분에 의해서만 결정되지 않도록 해야한다.

그래서 대부분의 해시함수를 구현할때 사용하는 연산들이 위와 같은 목적을 가지고 이루어 지게된다.

전형적인 해시함수는 여러가지 방법으로 만들어 질수 있는데,

첫번째로 Division기법이있다.

이는 키를 테이블 사이즈로 나누어서 나머지를 구하는 연산이다.

h(k) = k mod m

위와 같은 식이 나오게 되는데 0에서 m-1의 인덱스로 깔끔하게 나오기 때문에 자주 사용하게 된다.

장점은 한번의 mod 연산으로 계산되므로 매우 빠르다.

단점은, 어떤 m값에 대해서는 해시 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있다.

가령, m=2^p이면 키의 하위 비트 p가 해시 함수값이 되는것이다.

두번째는 multiplication 기법이다.

0에서 1사이의 상수 A를 선택하고 K_a의 소수 부분만을 선택한다.

소수 부분에 m을 곱한 후 소수점 아래를 버린다.

예를 들면 다음과 같다.

m=8, word size = w=5, k=21 일 때

1) A = 13/32를 선택

2) K_a  = 21*13/32 =273/32 = 8 + 17/32

3) m(k_a mod 1) = 8 * 17/32 =17/4 = 4.~~~~

4) 즉, h(21) = 4가 된다.

그렇다면 자바에서 해시는 어떨까.

자바는 해시를 체계적으로 제공해주는 프로그래밍 언어중에 하나이다.

java의 object 클래스가 hashcode()라는 메소드를 가지고 있다.

따라서, 자바의 모든 클래스가 hashcode 메소드를 상속받아 가지고 있다는 것이다.

이 메서드는 32비트 정수를 반환한다.

만약 x.equals(y)이면 x.hashcode() === y.hashcode()이다.

하지만 역은 성립하지 않는다.

object 클래스 안의 hashcode 메소드는 객체의 메모리 주소를 반환하는걸로 알려져있다.

그러나 공식 문서 상에 기재된 내용은 없다.

(it's implementation-dependent)

필요에 따라 이 메소드를 오버라이드 해서 사용한다.

위는 자바에서 string 클래스의 hashcode 메소드를 예로 든것이다.

hashcode 내부의 31진수 처럼 표현해서 사용 하는 것을 볼 수 있다.

파란색 코드 부분은 아래의 수식을 계산하는 코드이다.

만약 사용자 정의 클래스에서 사용하고 싶다면

해당 클래스 내에서 hashcode를 오버라이딩 해주면 된다.

위의 코드는 hashcode 메소드 내에서 재귀적으로 사용되는 예를 보여 주고 있다.

hash code와 hash함수를 구분할 필요가 있는데

hash code는 임의의 -2^31에서 2^31 사이의 정수이다

따라서, 이 값을 바로 해쉬 함수의 값으로 쓰는 것이 아니라 

내가 원하는 테이블 안에 들어가는 인덱스로 변환해주는 함수가 필요하다.

 즉, 위와 같은 별도의 함수가 필요 하다는 것이다.

위의 코드는 첫비트를 양수로 변환해준후 m으로 나눈 나머지를 구하는 코드이다.

이 함수를 수행하면 0에서 m-1까지의 인덱스가 나오게 된다.

다시 자바로 돌아와서, 

자바가 제공해주는 해시 테이블은 Hashmap이라는 Treemap과 유사한 인터페이스를 제공하며,

이는 내부적으로 하나의 배열을 해시 테이블로 사용한다.

또한 chaining으로 충돌을 해결한다.

그리고 load factor를 지정할 수 있는 특징을 가지고 있다.

이 때, 저장된 키의 개수가 load factor를 초과하면 더 큰 배열을 할당하고 

저장된 키들을 재배치(re-hashing)한다.

마지막으로 Hashset이라는 인터페이스도 제공하는데 set이라는 이름대로 집합의 성질을 지닌다.

해당 원소의 추가, 제거, 심지어 이터레이터 까지 제공하게 된다.

이러한 인터페이스를 제공하는것이 Hashset이다.