Hash (1)

해시 함수를 만들 때 고려해야 할 것들

1. Property of the data
2. Be fast to compute
3. "equal" things should return the same value

- 물론 "equal"은 자료구조를 만드는 사람이 정의하는 것.
4. Always return the same value for an object during one run of the code
- 한 번의 런타임 동안 하나의 객체에 대해선 하나의 결과가 나와야 저장한 값을 찾을 수 있다.
5. Possible to return different values for an object in separate runs
- 교수는 이걸 싫어해서 가급적 피하려고 한다.
- 특히, 데이터를 디스크에 저장하고 꺼내 쓰는 프로그램의 경우 이런 특성이 있으면 절대로 안된다.
- Object 객체의 hashCode 가 이렇게 동작함. 메모리 주소를 기반으로 값을 반환하기 때문에 오버라이딩 필요!
6. Minimize collisions
- 해시 충돌을 최소화해야 한다.

 

Hash function

key 역할을 할 클래스에는 hashCode 함수가 오버라이딩 되어 있어야 한다. Object 클래스의 hashCode 함수는 객체의 메모리 주소를 반환하기 때문이다. 실제 String 클래스의 hashCode는 아래와 같이 정의되어 있다.

 

public int hashCode(String s) {
    int g = 31;
    int hash = 0;

    for(int i = 0; i < s.length(); i++) {
        hash = g*hash + s.charAt(i);
    }

    return hash;
}

 

hashCode 함수는 overflow로 인해 음수값을 반환할 수도 있다는 점을 유의해야 한다. 

 

Hash Value

hashCode 함수가 반환하는 값을 table index로 사용할 수 있도록 바꿔줘야 한다.

 

1. & 0x7FFFFFFF를 적용해주면 음수를 양수로 바꿔줄 수 있다.
- 여기서 0x7FFFFFFF = 0111 1111 1111 1111 1111 1111 1111 1111

- 즉, 0x7FFFFFFF는 첫번째 비트를 0으로 바꿔준다.

2. % tableSize를 적용해주면 table index로 사용할 수 있게 된다.

( table size를 odd prime으로 하면 나머지가 더 고르게 분포해서 좋다. )

int hashval = data.hashCode(s);
hashval = hashval & 0x7FFFFFFF;
hashval = hashval % tableSize;

 

Load Factor

Load factor : 테이블에 데이터가 차있는 비율

 

$\lambda$ = $\cfrac{\text{number of entries}}{\text{total size of the array}}$

Resolve collisions in a hash : Open addressing

1. linear probing
- 충돌이 일어나면 빈 공간을 찾을 때까지 hv+1, hv+2, hv+3, ... 과 같이 linear한 방식으로 조사한다(probe). 
- 탐색, 제거시에도 같은 방법으로 조사한다.
- 점차 데이터가 뭉치게 된다.

 

2. quadratic probing
- 충돌이 일어나면 빈 공간을 찾을 때까지 hv+$1^2$, hv+$2^2$, hv + $3^2$, ... 과 같이 quadratic한 방식으로 조사한다(probe). 

- 탐색, 제거시에도 같은 방법으로 조사한다.

- 점차 데이터가 뭉치게 된다.

 

3. double hashing
- 1st hash function을 $h_1$, 2nd hash function을 $h_2$라고 하자. $h_1(k)$가 중복된다면 중복을 피할 수 있을 때까지 $h_1(k) + i\cdot h_2(k)$를 조사한다.

- 당연히 $h_2$는 0을 반환하지 않아야 한다.

- $h_2$는 $h_1$과 independent 해야 한다. 이 때 $h_1(k_1) = h_1(k_2)$ 일 때 $h_2(k_1) = h_2(k_2)$ 일 확률이 매우 낮아 clustering이 크게 줄어든다.

 

Resolve collisions in a hash : Chaining

◎ 배열을 만들고 배열의 각 위치에 연결 리스트를 생성한다. (키, 값)을 추가하면 연결 리스트에 추가해서 이어준다.

◎ Chaining (or chained hash)는 굉장히 안정적이고 보편적으로 사용되는 좋은 자료구조다. 교수 강추!

◎ 파이썬 딕셔너리도 chaining 기반으로 만들었다.

◎ 장점

- add, remove, getValue의 시간 복잡도 $O(1)$
- unlimited size
- less need for resizing

◎ 주의사항

- 너무 충돌이 많아지면 체인이 길어져 연결리스트와 다를 바가 없어진다.

- 최악의 경우 remove, getValue의 시간복잡도가 $O(n)$이 된다.

- 따라서 chaining을 사용하더라도 충돌은 가급적 피하는게 좋다.

 

Rehashing

◎ Open addressing의 경우, $\lambda$가 1에 가까워지면 resizing이 필수적이다.
◎ Chaining의 경우, $\lambda$가 1보다 커질 수도 있지만 $\lambda$가 되도록 작아야 연결 리스트가 짧게 유지되므로 $\lambda$가 어느 정도로 커지면 resizing을 해주는 것이 좋다. 
◎ Rehashing

- 배열에 있는 Linked List를 index by index로 옮기는 방법은 사용할 수 없다.

(old hash value) = (hashCode(key) & 0x7FFFFFFF) % tableSize

(new hash value) = (hashCode(key) & 0x7FFFFFFF) % newSize

Generally, (old hash value) $\neq$ (new hash value)

- Rehashing이 필요하다. 즉, 모든 원소에 대해 hv를 다시 계산해서 새로운 배열에 넣어줘야 한다.