Hashing(해싱)

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다.

Hahsing(해싱)

- Hash Table(해쉬 테이블)

해쉬 테이블은 Dynamic set을 구현하는 효과적인 방법의 하나

적절한 가정하에서 평균, 삽입, 삭제 시간 -> O(n)

보통 최악의 경우 -> Θ(n)

- Hash Function(해쉬 함수)

해쉬 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

h를 사용하여 키 k를 T[h(k)]에 저장

h : U -> {0, 1, 2, ... , m-1}

여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합

키 k가 h(k)로 해싱되었다고 말함

Hash Function(해쉬 함수)의 예

- 모든 키들을 자연수라고 가정(어떤 데이터든지 자연수로 해석하는 것이 가능)

예 : 문자열

ASCII코드 : C = 67, L = 76, R = 82, S = 83

문자열 CLRS는 (67*128^3) + (76*128^2) + (82*128^1) + (83*128^0) = 141,764,947

해쉬 함수의 간단한 예

h(k) = k%m, 즉 key를 하나의 자연수로 해석한 후 테이블의 크기 m으로 나눈 나머지

항상 0 ~ m-1 사이의 정수가 됨

Collision(충돌)

- 두 개 이상의 키가 동일한 위치로 해싱되는 경우

- 즉, 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 상황

- 일반적으로 |U| >> m 이므로 항상 발생 가능(즉, 단사 함수가 아님)

- 만약 |k| > m라면 당연히 발생, 여기서 k는 실제로 저장된 키들의 집합

- 충돌이 발생한 경우 대처 방법이 필요

- 대표적인 두 가지 충돌 해결 방법 : Chaing과 Open Addressing

Chaining에 의한 충돌 해결

- 동일한 장소로 해싱된 모든 키들을 하나의 연결 리스트(Linked List)로 저장

- Insertion(키의 삽입)

키 k를 리스트 T[h(k)]의 맨 앞에 삽입 : 시간복잡도 O(1)

중복된 키가 들어올 수 있고 중복 저장이 허용되지 않는다면 삽입 시 리스트를 검색해야함

따라서, 시간복잡도는 리스트의 길이에 비례

- Search(키의 검색)

리스트 T[h(k)]에서 순차 검색

시간복잡도는 키가 저장된 리스트의 길이에 비례

- Deletion(키의 삭제)

리스트 T[h(k)]로 부터 키를 검색 후 삭제

일단 키를 검색해서 찾은 후에는 O(1) 시간에 삭제 가능

- 최악의 경우 모든 키가 하나의 슬롯으로 해싱되는 경우 길이가 n인 하나의 연결리스트가 만들어짐

  따라서, 최악의 경우 탐색시간은 Θ(n) + 해쉬 함수 계산 시간

- 평균 시간복잡도는 키들이 여러 슬롯에 얼마나 잘 분배되느냐에 의해서 결정

Open Addressing에 의한 충돌 해결

- 모든 키를 Hash Table(해쉬 테이블) 자체에 저장

- 테이블의 각 Slot(칸)에는 1개의 키만 저장

- 충돌 해결 기법

- Linear Probing

h(k), h(k+1), h(k+2), ... 순으로 검사하여 처음으로 빈 슬롯에 저장

테이블의 끝에 도달하면 다시 처음으로 Circular하게 돌아감

단점 : 

Primary Cluster : 키에 의해서 채워진 연속된 슬롯들을 의미

이런 Cluster가 생성되면 Cluster는 점점 더 커지는 경향이 생김

- Quadratic Probing

충돌 발생 시 h(k), h(k)+1^2, h(k)+2^2, h(k)+3^2, .... 순서로 시도

- Double Hashing

서로 다른 두 해쉬 함수 h1과 h2를 이용하여 해결

h(k, i) = (h1(k) + i*h2(k)) mod m

- 단순히 키를 삭제할 경우 문제가 발생

예로 A2, B2, C2가 순서대로 모두 동일한 해쉬 함수 값을 가져서 Linear Probing으로 충돌해결

B2를 삭제한 후 C2를 검색

좋은 해쉬 함수란?

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

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

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

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

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을 곱한 후 소수점 아래를 버린다.

예 : m=8, word size=w=5, k=21

A = 13/32를 선택

kA = 21*13/32 = 273/32 = 8+17/32

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

즉, 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하여 사용한다.

  예 : Integer 클래스는 정수값을 hashcode()로 사용

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

public final class String{
	private final class[] s;
	...
	public int hashcode() {
		int hash = 0;
		for(int i=0; i<length(); i++) {
			hash = s[i]+(31*hash);
		}
		return hash;
	}
}

h(s) = 31^L-1*S0 + ... + 31^1*S(L-2) + 31^0*S(L-1)

사용자 정의 클래스의 예

public class Record {
	private String name;
	private int id;
	private double value;
	public int hashcode() {
		int hash = 17;
		hash = 31*hash + name.hashCode();
		hash = 31*hash + Integer.valueOf(id).hashCode();
		hash = 31*hash + Double.valueOf(value).hashCode();
		return hash;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Record r = new Record();
		r.name = "my name is KKK";
		r.id = 5;
		r.value = 4.3;
		System.out.println(r.name);
		System.out.println(r.id);
		System.out.println(r.value);
	}

}

모든 멤버들을 사용하여 hashcode를 생성한다.

HashCode와 Hash Function(해쉬 코드와 해쉬 함수)

- HashCode : -2^31 ~ 2^31 사이의 정수

- Hash Function : 0에서 M-1 까지의 정수(배열 인덱스)

private int hash(Key key) {
	return (key.hashCode() & 0x7fffffff)%M;
}

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

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

Chaining으로 충돌 해결

load factor를 지정할 수 있음(0 ~ 1사이의 실수)

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

HashSet<Mykey> set = new HashSet<Mykey>();
	set.add(Mykey);
	if(set.contatins(thekey))
	...
	int k = set.size();
	set.remove(thekey);
	Iterator<Mykey> if = set.iterator();
	while(it.hasNext()) {
		Mykey key = it.Next();
		if(key.equals(akey))
			it.remove();
	}