비선형 데이터구조, 해시(Hash) #7 재해싱 및 해시 클래스 구현

이전글

https://yonghwankim-dev.tistory.com/176

비선형 데이터구조, 해시(Hash) #6 체이닝(Chaining)

 

개요

이전글에서는 해시 충돌을 해결하는 방법으로 체인 해시를 알아보았습니다. 하지만 체인 해시에서도 데이터가 차면 크기 조정을 수행해야 합니다. 따라서 이번 글에서는 체인 해시에서 크기 조정하는 방법을 소개하겠습니다.

 

1. 재해싱이란 무엇인가?

재해싱이란 추가된 데이터들이 많아져서 테이블의 크기를 변경하고 기존 데이터들을 변경한 테이블로 옮기는 작업을 재해싱이라고 합니다.

 

재해싱할때 주의할점은 크기를 늘린 테이블로 요소들을 옮길때 위치까지 그대로 옮기면 안됩니다. 이는 해시함수값을 계산할 때 동일한 키값이라 하더라도 크기를 늘린 테이블의 크기 값으로 %연산을 수행시 해시 함수 값이 동일하다고 보장할 수 없기 때문입니다.

 

따라서 체인해시에서 데이터들이 많아져서 크기 조정 시 다음과 같은 단계를 수행합니다.

1. 테이블의 크기를 두배로 늘림
2. 아래 코드의 따라 data의 index를 다시 계산하여 연결리스트의 요소들을 옮김

// data의 index 결정
int idx = x.hashCode(s);
idx = idx & 0x7FFFFFFF;
idx = idx % newTableSize;

 

2. Hash 클래스

체인 해시 구조를 구현합니다.

public class Hash<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;
		}

		@Override
		public int compareTo(HashElement<K, V> o) {
			return ((Comparable<K>) this.key).compareTo(o.key);
		}
        
		@Override
		public String toString() {
			return "HashElement [key=" + key + ", value=" + value + "]";
		}
	}
	
	int numElements, tableSize;	// 요소 개수, 테이블 크기
	double maxLoadFactor;		// 최대 적재율
	LinkedList<HashElement<K, V>>[] harray;
}

 

3. Hash 클래스의 생성자

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

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Hash/Implements
[부스트코스] 자바로 구현하고 배우는 자료구조