13-3. 해슁 3

좋은 해쉬 함수란?

- 현실에서는 키들이 랜덤하지 않음

- 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움

- 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 게 바람직

- 해쉬함수 값이 키의 특정 부분에 의해서만 결정되지 않아야..

 

Division 기법

- h(k) = k mod m

- 예 :  m = 20 and k = 91 -> h(k) = 11

- 장점 : 한 번의 mod 연산으로 계산. 따라서 빠름.

- 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음.

         가령 m = 2^p이면 키의 하위 p비트가 해쉬함수 값이 됨.

 

Multiplication 기법

- 0에서 1 사이의 상수 A를 선택 : 0 < A < 1

- kA의 소수부분만을 택한다. (정수는 안 씀)

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

 

 

Hash code in Java

- Java의 Object 클래스는 hashCode() 메서드를 가짐. 따라서 모든 클래스는 hashCode() 메서드를 상속 받는다. 이 메서드는 하나의 32비트 정수를 반환한다.

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

- Object 클래스의 hashCode() 메서드는 객체의 메모리 주소를 반환하는 것으로 알려져 있음 (but its implementation-dependent)

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

   - 예) Integer 클래스는 정수값을 hashCode로 사용...

 

// 해쉬 함수의 예 : hashCode() for Strings in Java
public 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;
    }
}

 

 

piblic class Record
{
	private String name;
    private int id;
    private double value;
    ...
    
	// 내가 원하는 hash 함수를 작성한다.
    public int hashCode()
    {
    	int hash = 17;	// nonzero constant
        hash = 31 * hash + name.hashCode();
        hash = 31 * hash + Integer.valueOf(id).hashCode();
        hash = 31 * hash + Double.valueOf(value).hashCode();
        return hash;
    }

}

 

 

 

hashCode과 hash함수

- hashCode : -21^31에서 2^31 사이의 정수

- hash 함수 : 0에서 M-1까지의 정수.. (배열 인덱스)

// hashCode를 hash 함수로 만들기

private int hash (Key key) {

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

}

 

 

Java에서는 HashMap과 HashSet이 있다.

C++에서는 #include <unordered_set>이 있다. (자바의 HashMap에 대응..)