자료구조 - Hash(해시)

해시

• 데이터를 빠르게 추가하거나 제거하도록 한 데이터 구조
• 해시는 키, 그리고 그와 연관된 값으로 이루어져있다

---

해시 함수

• 해시 함수를 작성할 때 고려해야할 점
  1. 데이터의 속성
  2. 연산이 빨라야한다
  3. 두 요소가 "같다면" 같은 값을 반환
  4. 같은 실행 환경일 경우 같은 객체라면 같은 값 반환
  5. 코드를 새로 실행하면 객체가 같더라도 다른 값이 반환돌 수 있다
  6. 코드에서 최대한 충돌이 일어나지 않도록한다
•  

---

해시 충돌

• 서로 다른 값을 가진 키가 일치하는 경우를 해시 충돌이라고 한다
• 위 사진에서는 전화번호 3분할한 것의 합을 키로 지정 -> 키의 값이 2386으로 같아 해시 충돌이 발생

---

해시 함수에서 문자열

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

• 문자는 유니코드로 변환하여 숫자 형태로 나타냄
• 각 문자를 변환한 후 그 숫자들을 합한다면, 문자열을 숫자로 변환 가능하다
• this,hits,tish 등 다른 문자열도 같은 숫자로 표현되는 해시충돌이 발생 -> 어떤 상수 g를 문자의 위치만큼 제곱한 뒤 그수를 곱해서 문제를 해결

---

해시 크기 최적화

• 해시 충돌을 방지하기 위해 해시의 크기를 최적화
  • 예시 1) 해시의 크기를 홀수로 설정하여 % 연사자를 사용했을 때 다양한 결과 출력
  • 예시 2) 해시의 크기를 소수로 설정하여 다양한 숫자가 나오게함

---

양수로  변환

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

• 위 코드와 같이 연산하면 값을 해시(테이블)에 포함되는 양수로 나타낼 수 있다
• Java에서는 음수를 표현하기 위해 2의 보수를 활용(첫 숫자가 0이면 양수, 1이면 음수)
•  

---

LoadFactor 메소드

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

---

충돌 해결

1. 선형 조사법(linear probing)
   • 채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을때까지 다음 칸을 확인하는 방법
   • 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야함
2. 2차식 조사법(quadratic probing)
   • 다음 칸 대신 1부터 순서대로 제곱하여 더한 칸( 1^2​​,  2^2​​, ... )을 확인하는 방법
   • 테이블의 끝을 넘어간다면 % 연산을 해서 다시 테이블의 범위 안에 들어오게 함
3.  이중 해싱(double hashing)
   • hashCode 함수가 2개 있어 채우려는 공간이 이미 차 있다면 두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법
   • 이중 해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 더 골고루 넣을 수 있다.
   • 하지만 해시 함수가 2개 필요하다는 단점

---

체이닝(chaining)

• 체이닝(Chaining)은 요소마다 연결 리스트를 만들어 수많은 데이터를 수용할 수 있게 하는 방법
• 체인 해시는 가장 안정적이고 보편적으로 사용되는 자료 구조 중 하나
• 체이닝을 하면 수용 가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없어진다
• 적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값
• 체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있다.
•  hashCode가 같은 숫자만 반환하여 하나의 체인이 너무 길어지면 결국 연결 리스트와 시간 복잡도가 같아지는 문제가 발생

---

재해싱

• 체인 해시에서 해시가 너무 많이 차면 크기 조정을 해야 한다.
• 연결 리스트의 위치를 그대로 하여 옮기면 정보를 다시 찾거나 제거하려 할 때 문제가 발생
• 정보의 위치를 지정할 때 다른 정보는 그대로인데, tableSize만 바뀌기 때문
• 그래서 각 요소의 위치를 초기화한 후, 처음부터 다시 위치를 지정
• 재해싱 방법 
  1. 크기가 2배인 배열을 만든다.
  2. data의 index를 다시 결정하여 연결 리스트의 요소들을 옮긴다

// data의 index 결정
int idx = x.hashCode(s);
idx = idx & ox7FFFFFFF;
idx = idx % 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;
}

---

생성자

• 해시를 구현하는 생성자
• 최대 적재율을 줄이면
  • 해시 테이블에서 연결 리스트가 더 골고루 분포,
  • 크기 조정을 더 자주 하게 되어서 시간이 많이 든다.
• 최대 적재율을 늘리면
  • 연결 리스트의 분포가 퍼지지 못한다는 단점
  • 크기 조정 작업은 비교적 덜 하게 된다.
• 일반적으로 해시 테이블이 어디에 사용될지 모르는 상황에서는 0.75가 적절한 최대 적재율

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의 값이 동일하면 그 때 키의 값을 반환
• 간복잡도는 Best Case: O(1), Worst Case: O(n) 

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

• 연결 리스트가 너무 길어질 경우 해시의 크기를 조절
• 크기가 너무 커진다면, 새로운 연결 리스트 배열을 만들고 해시의 모든 연결 리스트에 있는 요소의 키와 값을 각각 찾아내야 한다.
• 모든 데이터를 복사하고 복사본을 만들기 때문에 복잡도가 높다.

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

 

참고 https://www.boostcourse.org/cs204

자바로 구현하고 배우는 자료구조