[TIL] 자료구조 - 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;
}