비선형 데이터구조, 해시(Hash) #9 getValue & reSize 메서드

이전글

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

비선형 데이터구조, 해시(Hash) #8 add & remove 메서드

 

개요

이전글에서는 해시의 add, remove 메서드 구현을 알아보았습니다. 이번글에서는 add 메서드 중 해시의 데이터가 특정 최대적재율보다 초과하게 되면 reSize 메서드를 수행하여 테이블의 크기를 2배로 증가시키는 명령어가 존재하였습니다. 이번글에서는 Key 값을 이용하여 해시 테이블로부터 Value 값을 가져오는 getValue 메서드와 테이블의 사이즈를 증가시키는 reSize 메서드를 구현합니다.

 

1. getValue 메서드

public V getValue(K key) {
		
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
	
	for(HashElement<K, V> item : harray[hashval]) 
	{
		if(((Comparable<K>)key).compareTo(item.key)==0)
		{
			return item.value;
		}
	}
	return null; 
}

 

 

2. reSize 메서드

public void reSize(int newSize) {
		
	// 초기화
	LinkedList<HashElement<K, V>>[] newArray = new LinkedList[newSize];
		
	for(int i=0; i<newSize; i++)
	{
		newArray[i] = new LinkedList<HashElement<K, V>>();
	}
	
	// 이동
	for(LinkedList<HashElement<K, V>> list : harray)
	{
		for(HashElement<K, V> item : list)
		{
			V val = getValue(item.key);
			HashElement<K, V> he = new HashElement<K,V>(item.key, val);
			int hashVal = (item.key.hashCode() & 0x7FFFFFFF) % newSize;
			newArray[hashVal].add(he);
		}
	}
		
	// 테이블 정보 변경
	this.harray = newArray;
	this.tableSize = newSize;
}

 

3. getValue & reSize 테스트

public static void main(String[] args) {
	Hash<String, Integer> hash = new Hash<String, Integer>(7);
	hash.add("a", 1);
	hash.add("b", 2);
	hash.add("c", 3);
	hash.add("d", 4);
	hash.add("e", 5);
	hash.add("f", 6);
	hash.add("g", 7);
	hash.add("h", 8); // reSize 수행
	hash.add("i", 9);
	hash.add("j", 10);
		
	System.out.println("key : b , value : "+ hash.getValue("b"));	// Expected Output : 2
	System.out.println(hash);
}

key : b , value : 2
[HashElement [key=b, value=2]]
[HashElement [key=c, value=3]]
[HashElement [key=d, value=4]]
[HashElement [key=e, value=5]]
[HashElement [key=f, value=6]]
[HashElement [key=g, value=7]]
[HashElement [key=h, value=8]]
[HashElement [key=i, value=9]]
[HashElement [key=j, value=10]]
[]
[]
[]
[]
[HashElement [key=a, value=1]]

 

References

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