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

이전글

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

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

 

개요

이전글에서는 테이블의 크기를 증가시킬때 데이터들을 옮기는 방법인 재해싱에 대해서 알아보았고 Hash 클래스의 생성자를 생성하였습니다. 이번글에서는 해시에 데이터를 추가하는 add메서드와 데이터를 제거하는 remove 메서드를 구현하도록 하겠습니다. 그리고 해시 데이터를 출력할 수 있도록 toString 메서드를 구현하겠습니다.

 

1. add 메서드

public boolean add(K key, V value) {
	// size
	if(loadFactor()>maxLoadFactor) 
	{
		reSize(tableSize*2);
	}
		
	// object
	HashElement<K, V> he = new HashElement(key, value);
		
	// index
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
		
	// linkedlist
	harray[hashval].add(he);
	numElements++;
		
	return true;
}

public double loadFactor() {
	return numElements / tableSize;
}

위의 코드에서 reSize 메서드는 현재 헤시 테이블의 적재율이 0.75보다 크게 되면 테이블의 크기를 2배로 증가시키는 메서드입니다. reSize 메서드의 내용은 다음글에서 소개됩니다.

 

2. remove 메서드

public boolean remove(K key) {
		
	HashElement<K, V> he = new HashElement(key, null);	
		
	// index
	int hashval = key.hashCode();		
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
		
	for(HashElement<K, V> item : harray[hashval])
	{
		if(item.compareTo(he)==0)
		{
			harray[hashval].remove(item);
			numElements--;
			return true;
		}
	}
	return false;
}

 

3. toString 메서드

@Override
public String toString() {
	StringBuilder sb = new StringBuilder();
	for(LinkedList<HashElement<K, V>> list : harray)
	{
		sb.append(list.toString()+"\n");
	}
	return sb.toString();
}

 

4. add & remove 메서드 테스트

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);
	hash.add("i", 9);
	hash.add("j", 10);
		
	System.out.println(hash);
	hash.remove("b");
	System.out.println(hash);
}

[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]]

[]
[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
[부스트코스] 자바로 구현하고 배우는 자료구조