3. 해시(Hash)

 

해시

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

 

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

 

해시 함수를 작성할 때 경계사항은 무엇일까요?

 

1. 데이터의 속성 (ex : CSSC 아이디가 있다면 CSSC 부분을 제거 )

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

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

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

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

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

 

* 코드를 새로 실행한다는 것이 어떤 의미일까요? 왜 다른 값이 나올 수 있을까요?

: Object 클래스의 toString, equals, hashCode와 같은 메소드들은 오버라이딩을 하지 않으면, 기본적으로 메모리 위치를 기반으로 코드가 실행된다. 객체는 코드가 새로 실행될 때마다 메모리 상의 다른 위치에 할당되기 때문에, 입력으로 들어온 객체가 같더라도 다른 값을 리턴하게 된다.

 

// 해시 클래스
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;
}

 

해시충돌이란?

 

- 서로 다른 값을 가진 키가 일치하는 경우를 해시 충돌이라고 합니다.

- 예를 들어, 위 사진에서는 전화번호를 3분할한 것의 합을 키로 지정하였습니다.

- 하지만 키가 2386으로 같아 해시 충돌이 발생합니다.

 

- 문자열 "this"를 해시로 나타내려면 문자는 유니코드로 변환하여 숫자 형태로 나타낼 수 있습니다.

- 각 문자를 변환한 후 그 숫자들을 합한다면, 문자열을 숫자로 나타낼 수 있을 것입니다.

- 하지만 다른 문자열도 같은 숫자로 표현되는 해시 충돌이 발생합니다.

- 어떤 상수 g를 문자의 위치만큼 제곱한 뒤 그 수를 곱하면 문제가 해결됩니다.

 

해시크기 최적화란?

- 해시 충돌을 방지하기 위해 해시의 크기를 최적화하는 방법들이 존재합니다!

- 해시의 크기를 홀수로 설정하여 % 연산자를 사용했을 때 다양한 결과가 나오게 합니다.
- 해시의 크기를 소수로 설정하여 나머지가 다양한 숫자가 나오게 합니다.

 

그렇다면 해시코드는 어떻게 만드는 것이 좋을까요?

 

1. 양수로 전환 (배열의 index에 넣기 위해)

2. 테이블크기로 % 하기

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

// data의 index 결정
int hashval = data.hashCode(s);
hashval = hashval & ox7FFFFFFF; //양수로 전환
hashval = hashval % tableSize; //테이블 사이즈 고려

 

loadFactor 메소드란?

 

LoadFactor(적재율): 해시에 데이터가 얼마만큼 있는지 알려줍니다.

 

- 적재율은 λ로 표기하고 항목 수를 자료 구조의 크기만큼 나눈 값입니다.

- λ의 크기에 따라 해시 충돌이 일어나지 않도록 해시의 크기를 조절합니다.

 

재해싱

 

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

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

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

- 연결 리스트의 위치를 그대로 하여 옮기면 정보를 다시 찾거나 제거하려 할 때 문제가 발생합니다.

- 정보의 위치를 지정할 때 다른 정보는 그대로인데, tableSize만 바뀌기 때문입니다.

- 그래서 각 요소의 위치를 초기화한 후, 처음부터 다시 위치를 지정해주어야 합니다.

 

 

 

해시 충돌을 해결하는 방법은? 

 

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

 

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

 

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

 

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

 

 

해시 체이닝

체이닝(Chaining) : 요소마다 연결 리스트를 만들어 수많은 데이터를 수용할 수 있게 하는 방법입니다.

 => 체인 해시는 가장 안정적이고 보편적으로 사용되는 자료 구조 중 하나입니다.

 

- 체이닝을 하면 수용 가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없어집니다.

- 적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값입니다.

- 체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있습니다.

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

 

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;
	}
}

 

* 형변환을 해줘야 하는 이유는 뭘까요?

: 타입소거로 인해 자바에서 제네릭으로 배열을 만들지 못함. 자바의 배열에는 타입을 지정해줘야함.

제네릭 타입을 사용하기 위해서 형변환을 해줘야합니다. LinkedList는 HashElement를, HashElement는 K, V라는 제네릭 타입을 필요로 합니다.

 

remove 와 add 메소드

 

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++];
}

 

* 해시에는 순서가 있나요?

:  데이터들은 해시 코드에 의해 위치가 결정되기 때문에, 해시는 데이터들의 순서를 보장하지 않습니다. 그래서 배열 크기를 변경할 때도 모든 데이터들의 순서가 바뀌며, 키를 반환하는 반복자에서도 키의 순서는 보장되지 않습니다.