3-5) 해시 - add, remove, getValue

 

아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.

 

add, remove

해시에 요소를 추가하고 삭제하는 코드. 연결 리스트의 addFirst로 add한다. 

public boolean add(K key, V value){
	if (loadFactor() > maxLoadFactor)	// 적재율 확인
		resize(tableSize*2);	// resize 메소드 - 테이블 크기 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
	hashArray[hashval].add(he);

	numElements++;
	return true;
}

public boolean remove(K key, V value){
	// index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;	// 양수만들기	
	hashval = hashval % tableSize;	// 크기최적화
	// 해당하는 index의 키와 값 제거
	hashArray[hashval].remove(he);

	numElements--;
	return true;
}

 

getValue

해시에서 index값을 찾는 코드. 

public V getValue(K key){
	// 해당하는 index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
	// 그 index를 찾을 때까지 반복
	for (HashElement<K, V> he : harray[hashval]){		// Iterator
		if (((Comparable<K>)key).compareTo(he.key) == 0){
			return he.val;
                }
        }
	return null;
}

 

Q. getValue의 시간 복잡도는?

A. 해시 충돌이 많이 발생한 경우 더 걸릴 수 있으나 그렇지 않을 경우 대체로 O(1)이 된다.