[자바로 구현하고 배우는 자료구조] 3. 해시(Hash) (4)

3-15. add와 remove 메소드

public boolean add(K key, V value){
	if(loadFactor()>maxLoadFactor){
    	resize(tableSize * 2);
    }
    HashElement<K,V> he = new HashElement(key, value);
    int hashval = key.hashCode();
    hashval = hashval & 0x7FFFFFFF;
    hashval = hashval % tableSize;
    harray[hashval].add(he);
    numElement++;
    return true;
}
public boolean remove(K key, V value){
	int hashval = key.hashCode();
    hashval = hashval & 0x7FFFFFFF;
    hashval = hashval % tableSize;
    harray[hashval].remove(he);
    numElement--;
    return true;
}

 데이터를 추가할 때, 먼저 적재율(loadFactor)를 확인한다. maxFactor인 0.75를 넘으면 추가하기 전에 tableSize를 두 배로 늘린다. 그리고 HashElement 객체를 선언하고, hashval로 추가할 인덱스를 구해 그 자리에 데이터를 추가한 다음, 요소의 갯수(numElement)를 추가한다. 해시에서는 데이터의 순서가 중요하지 않기때문에 addFirst를 이용하든 addLast를 이용하든 관계 없지만 addFirst를 사용한다.

 데이터를 삭제할 때는 적재율을 확인할 필요가 없기때문 resize할 필요 없다. 인덱스를 찾아 요소를 제거하면 된다. 강의에는 numElement에는 'numElement++'로 되어있는데 제거하는 거니까 --로 바꿔줘야 할 것 같다. 

3-16. getValue 메소드

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

getValue 메소드는 Key값을 매개변수로 받아 Value값을 반환하는 메소드이다. key값으로 인덱스 값을 찾고, 반복문을 이용하여  해당 헤시체인의 연결리스트의 요소를 모두 비교한다. 찾으면 HashElement의 value를, 없으면 null을 반환한다.

3-17. resize

public void resize(int newSize){
	LinkedList<HashElement<K,V>>[] new_array = (LinkedList<HashElement<K,V>>[])LinkedList[numSize];  
	for(int i=0; i<newSize; i++){
    	new_array[i] = new LinkedList<HashElement<K,V>>();
	}
    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);
	}
    harray = new_array;
    tableSize = newSize;
}

 연결리스트에 데이터가 많아지면 반복문으로 데이터를 찾는데 오래 걸려 시간복잡도가 나빠진다. 배열의 크기를 수정하는 것은 불가능하므로, 크기를 늘린 배열을 새로 만들어줘야 한다. 새로운 배열을 만들면 해시 요소도 이동시켜야 하는데 기존 배열의 인덱스 값을 그대로 이용하면 인덱스 값을 구할 때, 기존 테이블의 크기를 이용하므로 새로운 테이블 크기에 맞춰 인덱스 값을 다시 구해 이동시켜줘야 한다. 

 

그렇다면 먼저 테이블의 크기를 변경해줘야 한다. 보통 기존 테이블의 두 배로 늘리므로 resize 메소드는 새로운 테이블의 크기(보통 기존의 두 배)를 매개변수로 전달받는다. 새로운 크기의 배열의 요소마다 연결리스트를 추가한다. 다음으로 클래스에서 키값으로 value값을 찾아 새로운 배열의 인덱스에 key와 value 값을 가진 HashElement를 추가해준다. for문의 this는 현재 클래스를 말한다. 이동하는 게 모두 끝나면 기존의 배열의 포인터를 새로운 배열로, 테이블 크기는 새로운 테이블의 크기로 바꿔준다.

3-18. Key반복자

class IteratorHelper<T> implements Iterator<T>{
	T[] keys;
    int position;
	public IteratorHelper{
    	keys = (T[])Object[numElement];
        int p = 0;
        for(int i=0; i<tableSize; i++){
        	LinkedList<HashElement<K,V>> list = hash_array[i];
            for(HahsElement<K,V> h: list)
            	keys[p++] = (T)h.keys;
        }
        position = 0;
    }
    public boolean hasNext(){
    	return position<key.length;
    }
    public T next(){
    	if(!hasNext())
        	return null;
		return keys[position];
    }
}

테이블 내 모든 key값을 살피는 Key Iterator 클래스가 있다. 시간복잡도는 O(n)이다. 해시에서 위치는 인덱스값으로 보장하지 않는다.

이 클래스의 존재에 대해서는 이해했지만 코드는 이해하지 못했다. position이라는 변수를 선언했지만 position은 0이고, keys[0]로만 다음 요소를 찾는건가? hasNext메소드는 무조건 false를 반환하게 되는데? 그렇다면 IteratorHelper 생성자 안에 변수 p는 왜 반복분 안에서 추가되는거지? 생성자 안에서 p를 선언하지 않고 position을 사용해도 되는거 아닌가? 모르겠다. 질문하고 싶지만 연관 토론으로 공개적으로 질문해야하다보니 질문하기 어렵다. 비밀글로 질문하게 해주세요...

 

---

https://www.boostcourse.org/cs204/joinLectures/145114

자바로 구현하고 배우는 자료구조

위 강의를 듣고 작성한 내용이지만 강의의 스크립트를 그대로 받아 적는 게 아니라 코드와 필기를 보고 정리하다보니 틀린 부분이 있을 수 있습니다. 잘못된 설명이 있다면 말씀해주세요.