해싱 (Hashing) (3)

Hashing

좋은 해쉬 함수의 조건

- 현실에서의 키들은 무작위값이 아니다.

- 만일 키들의 통계적인 분포에 대해 알고 있다면 이를 활용하여 해쉬 함수를 고안할 수 있겠지만 현실적으로 할 수 없는 방법이다.

- 키들이 어떤 특정한(가시적인) 패턴을 가지더라도 해쉬함수 값이 불규칙적이도록 하는 것이 바람직하다. 이는 곧 해쉬합수의 값이 키의 특정 부분에 의해서만 결정되지 않도록 만들어야 한다는 뜻이다.

해쉬 함수를 만드는 방법

- Division 기법

h(k) = k mod m => 거의 모든 해쉬함수들이 가장 마지막에 수행하는 경향이 있다.

Ex) m = 20, k = 91 -> h(k) = 11

장점 : 한 번의 mod연산으로 계산하기 때문에 속도가 빠르다.

단점 : 어떠한 m값에 대해서는 해쉬 함수의 값이 키 값의 특정 부분에 의존하여 결정되는 경우가 있다. 예를 들어 $m=2^p$라면 어떠한 키의 하위 p비트가 해쉬 함수의 값이 된다.

- Multiplication 기법

0에서 1사이의 상수 A를 선택한다 (0 < A < 1)

kA의 소수부분만을 취한다.

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

Ex)  m = 8, word size = w = 5, k = 21

A = 13 / 32를 선택했다.

kA = 21 * 13 / 32 = 273 / 32 = 8 + 17 / 32 (정수 부분인 8을 제거한다.)

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

∴ h(21) = 4

Hash code in Java

- Java의 Object클래스는 hashCode()메소드를 가지고 있다. 따라서 모든 클래스들은 hashCode()메소드를 상속받게 된다. 이 메소드는 하나의 32비트 정수를 반환하게 된다. (음수값일 수도 있다.)

- 만약 x.equals(y)라면 x.hashCode() == y.hashCode()이다. 하지만 그의 역은 성립하지 않는다.

- Object 클래스의 hashCode()메소드는 객체의 메모리 주소를 반환한다고 알려져 있다. (but, it's implementation-dependent.)

- 필요에 따라 각 클래스마다 이 메소드를 override하여 사용한다.

Ex) Integer 클래스는 정수값을 hashCode로 사용한다.

해쉬함수의 예 : hashCode() for Strings in Java

- h(s) = $31^{L-1}$ * $s_0$ + ... + $31^1$ * $s_{L-2}$ + $31^0$ * $s_{L-1}$

- L : String의 길이, s : 유니코드값

pulbic final class String {

private final char[] s;

...

public int hashCode() {

int hash = 0;

for (int i = 0; i < length(); i++)

hash = s[i] + (31 * hash);

return hash;

}

}

사용자 정의 클래스의 예시

- 데이터 클래스 내에 있는 모든 멤버들을 사용하여 hashCode를 생성한다.

- 만약 데이터 클래스 내에서 한 가지 멤버만 사용해 hashCode를 생성한다면 그 멤버와 값이 같기만 하다면 해쉬코드의 값이 같아지는 문제가 발생하게 된다.

public class Record {

private String name;

private int id;

private double value;

...

public int hashCode() {

int hash = 17; // 0이 아닌 상수값은 아무거나 상관없음 (보통은 소수를 사용한다.)

hash = 31 * hash + name.hashCode();

hash = 31 * hash + Integer.valueOf(id).hashCode();

hash = 31 * hash + Double.valueOf(value).hashCode();

return hash; 

}

}

hashCode와 hash function

- Hash Code : $-2^31$에서 $2^31$사이의 정수범위를 가지고 있다.

- Hash Function : 0에서 M - 1까지의 정수 범위를 가지고 있다. (배열 인덱스)

- Ex

private int hash(Key key) {

return (key.hashCode() & 0x7fffffff) % M;

}

HashMap in Java

- TreeMap 클래스와 유사한 인터페이스를 제공해준다. (둘 다 java.util.Map인터페이스를 구현한 클래스이다.)

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

- 해쉬 함수는 일반적인 구성을 취하고 있다. (바로 위의 예시와 유사하다.)

- chaining으로 충돌 문제를 해결하고 있다.

- load factor를 지정할 수 있다. (0 ~ 1 사이의 실수값)

- 저장된 키의 개수가 load factor를 초과하게 된다면 더 큰 배열을 할당하고 저장된 키들은 재배치시키게 된다. (re-hashing)

- 코드

HashSet<MyKey> set = new HashSet<>();

set.add(MyKey); // 요소 추가 가능

if (set.contains(theKey)) // 요소 존재 여부 검사 가능

...

int k = set.size();

set.remove(theKey); // 요소 제거 가능

Iterator<MyKey> it = set.iterator(); // iterator 가능

while (it.hasNext()) {

MyKey key = it.next();

if (key.equals(aKey))

it.remove();

}