들어가기 전에

해시의 크기를 조정하는 resize에 대해 살펴보도록 하겠습니다.

학습 목표

resize가 필요한 이유를 이해하고 활용할 수 있습니다.

핵심 단어

• 해시
• resize
  

강의 듣기

resize

연결 리스트가 너무 길어질 경우 해시의 크기를 조절하는 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;
}

생각해보기

1) resize 함수의 시간 복잡도는 무엇인가요?