[Data Structure] Hash (해시)

해시

연결 리스트의 단점은 리스트에서 무언가를 찾고 싶을 때 무조건 모든 요소를 살펴봐야 한다는 것입니다. 이러한 단점을 해결하여, 데이터를 빠르게 추가하거나 제거하도록 한 데이터 구조가 해시입니다.

해시는 키, 그리고 그와 연관된 값을 가지고 있습니다. 모든 요소를 살펴본 후 동일한 노드를 찾는 연결 리스트와 달리, 해시에서는 키가 주어지면 바로 그와 연관된 값을 찾을 수 있습니다.

해시 함수

해시 함수를 작성할 때 아래와 같은 점들을 고려해야 합니다.

1. 데이터의 속성 예를 들어, CSSC 아이디가 있다면 CSSC 부분을 제거해야 합니다.

2. 연산이 빨라야 합니다.

3. 두 요소가 “같다면” 같은 값을 반환해야 합니다

4. 같은 실행 환경일 경우 같은 객체라면 같은 값이 나와야 합니다.

5. 코드를 새로 실행하면 객체가 같더라도 다른 값이 나올 수 있습니다.

6. 코드에서 최대한 충돌이 일어나지 않도록 해야 합니다.

해시 충돌

서로 다른 값을 가진 키가 일치하는 경우를 해시 충돌이라고 합니다. 예를 들어, 위 사진에서는 전화번호를 3분할한 것의 합을 키로 지정하였습니다. 그런데 키가 2386으로 같아 해시 충돌이 발생합니다.

해시 함수에서의 문자열

문자열 “this”를 해시로 나타내려면 어떻게 해야 할까요?

문자는 유니코드로 변환하여 숫자 형태로 나타낼 수 있습니다. 따라서 각 문자를 변환한 후 그 숫자들을 합한다면, 문자열을 숫자로 나타낼 수 있을 것입니다.

그런데 이렇게 변환할 경우, this뿐만 아니라 hits, tish 등 다른 문자열도 같은 숫자로 표현되는 해시 충돌이 발생합니다. 어떤 상수 g를 문자의 위치만큼 제곱한 뒤 그 수를 곱하면 문제가 해결됩니다.

문자열을 해시로 나타내는 함수는 다음과 같습니다.

public int hashCode(String s) {
	int g=31;
	int hash=0;
	// 문자열을 숫자로 나타내기
	// 상수 g를 문자의 위치만큼 제곱한 뒤 곱합니다.
	for (int i=0; i<s.length; i++)
		hash = g*hash + s.charAt(i);
	return hash;
}

양수로 변환

다음과 같이 연산하면 값을 해시(테이블)에 포함되는 양수로 나타낼 수 있습니다. (Java에서는 음수를 표현하기 위해 2의 보수를 활용합니다. 첫 숫자가 0이면 양수고 1이면 음수입니다.)

이 방법을 사용하여 data를 배열의 어느 위치에 넣을 것인지 결정합니다.

// data의 index 결정
int hashval = data.hashCode(s);
hashval = hashval & ox7FFFFFFF;
hashval = hashval % tableSize;

LoadFactor 메소드

LoadFactor(적재율)는 해시에 데이터가 얼마만큼 있는지 알려줍니다. 적재율은 λ로 표기하고 항목 수를 자료 구조의 크기만큼 나눈 값입니다. λ의 크기에 따라 해시 충돌이 일어나지 않도록 해시의 크기를 조절합니다.

해시 충돌을 해결하는 방법

1. 선형 조사법(linear probing) 채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법입니다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 합니다.

2. 2차식 조사법(quadratic probing) 다음 칸 대신 1부터 순서대로 제곱하여 더한 칸$(1^2, 2^2, …)$을 확인하는 방법입니다. 테이블의 끝을 넘어간다면 % 연산을 해서 다시 테이블의 범위 안에 들어오게 합니다.

3. 이중 해싱(double hashing) hashCode 함수가 2개 있어 채우려는 공간이 이미 차 있다면 두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법입니다.

이중 해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 더 골고루 넣을 수 있습니다. 하지만 해시 함수가 2개 필요하다는 단점이 있습니다.

선형 조사법과 2차식 조사법은 더하는 값(1, 2, 3, … 또는 1^2, 2^2, 3^2, …)에 규칙성이 있는 반면에, 이중 해싱은 두번째 해시 함수가 리턴하는 값이 임의적이기 때문에 배열의 더 다양한 위치에 값을 저장할 수 있다.

체이닝(Chaining)

체이닝(Chaining)은 요소마다 연결 리스트를 만들어 수많은 데이터를 수용할 수 있게 하는 방법입니다. 체인 해시는 가장 안정적이고 보편적으로 사용되는 자료 구조 중 하나입니다.

체이닝을 하면 수용 가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없어집니다. 적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값입니다. 체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있습니다.

하지만 hashCode가 같은 숫자만 반환하여 하나의 체인이 너무 길어지면 결국 연결 리스트와 시간 복잡도가 같아지는 문제가 발생합니다.

재해싱

체인 해시에서 해시가 너무 많이 차면 크기 조정을 해야 합니다.

1. 크기가 2배인 배열을 만듭니다.

2. 아래 코드에 따라 data의 index를 다시 결정하여 연결 리스트의 요소들을 옮깁니다.

// data의 index 결정
int idx = x.hashCode(s);
idx = idx & ox7FFFFFFF;
idx = idx % tableSize;

연결 리스트의 위치를 그대로 하여 옮기면 정보를 다시 찾거나 제거하려 할 때 문제가 발생합니다. 정보의 위치를 지정할 때 다른 정보는 그대로인데, tableSize만 바뀌기 때문입니다. 그래서 각 요소의 위치를 초기화한 후, 처음부터 다시 위치를 지정해주어야 합니다.

해시 클래스

체인 해시는 해시 요소마다 키와 값이 들어있습니다. 키와 값을 저장하기 위한 내부 클래스는 다음과 같습니다.

// 해시 클래스
public class Hash<K, V> implements HashI<K, V> {
	class HashElement <K, V> implements Comparable <HashElement<K, V>>{
		// 키와 값 정의
		K key;
		V value;
		public HashElement (K key, V value) {
			this.key = key;
			this.value = value;
		}
		// compareTo 함수
		public int compareTo (HashElement<K, V> o)
			return (((Comparable<K>)this.key).compareTo(o.key))
	}
	// 변수
	int numElements, tableSize;
	double maxLoadfactor;
	LinkedList<HashElement<K, V>> [] harray;
}

내부 클래스

체인 해시는 해시 요소마다 키와 값이 들어있습니다. 키와 값을 저장하기 위한 내부 클래스는 다음과 같습니다.

public class Hash<K, V> implements HashI<K, V> {
	class HashElement <K, V> implements Comparable <HashElement<K, V>>{
		// 키와 값 정의
		K key;
		V value;
		public HashElement (K key, V value) {
			this.key = key;
			this.value = value;
		}
		// compareTo 함수
		public int compareTo (HashElement<K, V> h)
			return (((Comparable<K>)h.key).compareTo(this.key))
	}
}

생성자

지금까지 해시의 키와 값을 저장해줄 내부 클래스 HashElement를 살펴보았습니다. 이번에는 해시를 구현하는 생성자를 만들겠습니다.

public class Hash<K, V> implements HashI<K, V> {
	LinkedList<HashElement<K, V>>[] harray;
	// 해시 구현
	public Hash (int tableSize){
		this tableSize = tableSize;
		harray = (LinkedList<HashElement<K, V>>[]) new LinkedList[tableSize]; // 형 변환
		// 연결 리스트 체이닝
		for (int i=0; i<tableSize; i++)
			harray[i] = new LinkedList<HashElement<K, V>>();
		maxLoadFactor = 0.75;
		numElements=0;
	}
}

생성자

해시를 구현하는 생성자를 만드는 과정에 대한 복습입니다.

public class Hash<K, V> implements HashI<K, V> {
	LinkedList<HashElement<K, V>>[] harray;
	// 해시 구현
	public Hash (int tableSize){
		this tableSize = tableSize;
		harray = (LinkedList<HashElement<K, V>>[]) new LinkedList[tableSize]; // 형 변환
		// 연결 리스트 체이닝
		for (int i=0; i<tableSize; i++)
			harray[i] = new LinkedList<HashElement<K, V>>();
		maxLoadFactor = 0.75;
		numElements=0;
	}
}

add()

해시에 내용을 추가하는 add 메소드입니다. 크기가 너무 커지거나 작아질 경우, add 메소드에서 크기를 조절해주어야 합니다.

public boolean add(K key, V value){
	// resize
	if (loadFactor() > maxLoadFactor)
		resize(tableSize*2);
	// 키와 값을 저장해 놓을 object he 정의
	HashElement<K,V> he = new HashElement(key, value);
	// he의 index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
	// add he
	harray[hashval].add(he);

	numElements++;
	return true;
}

remove()

remove 메소드에서는 크기 조정을 걱정할 필요도 없고 객체를 생성할 일도 없습니다.

public boolean remove(K key, V value){
	// index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
	// 해당하는 index의 키와 값 제거
	harray[hashval].remove(he);

	numElements++;
	return true;
}

getValue

키의 값을 찾는 getValue 메소드입니다. 키의 index가 무엇인지 찾고 해시에서 그 index를 찾을 때까지 반복합니다. 그리고 key의 값이 동일하면 그 때 키의 값을 반환합니다.

public V getValue(K key){
	// 해당하는 index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
	// 그 index를 찾을 때까지 반복
	for (HashElement<K, V> he : harray[hashval]){
		if (((Comparable<K>)key).compareTo(he.key) == 0){
			return he.val;
                }
        }
	return null;
}

resize()

연결 리스트가 너무 길어질 경우 해시의 크기를 조절하는 resize 함수입니다. 크기가 너무 커진다면, 새로운 연결 리스트 배열을 만들고 해시의 모든 연결 리스트에 있는 요소의 키와 값을 각각 찾아내야 합니다.

모든 데이터를 복사하고 복사본을 만들기 때문에 복잡도가 높습니다.

public void resize(int newSize){
	// 새로운 체인 해시 생성
	<LinkedList<HashElement<K, V>>[] new_array = ...;
	(<LinkedList<HashElement<K, V>>[]) LinkedList[newSize];
	for (int i=0; i<newSize; i++)
		new_array[i] = new <LinkedList<HashElement<K, V>>[];
	// index에 맞게 값 채워넣기
	for (k key : this) {
		V val = getValue(key);
		HashElement<K,V> he = new HashElement<K, V>(key, val);
		int hashVal = (key.hashCode() & 0x7FFFFFFF) % newSize;
		new_array[hashVal].add(he);
	}
	// 덮어쓰기
	hash_array=new_array;
	tableSize=newSize;
}

Key반복자

모든 키에 대해 반복하여 해시의 전체 내용을 살펴봅니다. 시간 복잡도는 $O(n)$ 입니다.

// 키에 연결된 연결 리스트의 내용을 살펴보는 함수
class IteratorHelper<T> implements Iterator<T>{
	T[] keys;
	int position;
	// key반복자 사용
	public IteratorHelper(){
		keys = (T[]) Object[numElements];
		int p=0;
		for (int i=0; i<tableSize; i++) {
			<LinkedList<HashElement<K, V>> list = hash.array[i];
			for (HashElement<K, V> h : list)
				keys[p++] = (T) h.key();
		}
	position=0;
	}
	// 끝을 확인할 때 사용
	public boolean hasNext()
		return position < keys.length;
}
// 해시의 전체 내용을 살펴보는 함수
public T next(){
	if (!hasNext())
		return null;
	return keys[position++];
}

Reference

• BoostCourse