Java-자료구조 3주차 Hash 3 - 13 ~ 15

4주차 해시
3-13. 생성자
-내부 클래스인 HashElement에 알았으면, 이제 Hash 생성자를 만들어보자!
(내부 클래스-data 넣는 공간, 생성자-연결리스트를 연결할 해시 배열)

public class Hash<K, V> implements HashI<K, V> {
	LinkedList<HashElement<K, V>>[] harray;
	// 해시 구현
	public Hash (int tableSize){ 
		this tableSize = tableSize; // 나중에 찾을 수 있도록 크기 저장
        // 해시 배열 생성
		harray = (LinkedList<HashElement<K, V>>[]) new LinkedList[tableSize]; // 배열 생성 후 형 변환
        
		// 연결 리스트 체이닝 - 필요한 부분이 비어있는지, 존재하는지 등 확인
		for (int i=0; i<tableSize; i++)
			harray[i] = new LinkedList<HashElement<K, V>>();
		maxLoadFactor = 0.75; // 일반적으로 해시 내 가장 적절한 적재율
		numElements=0; 요소 갯수는 0
	}
}

생성자를 통해 사용자가 테이블의 크기를 설정한다
연결리스트가 골고루 퍼지게 만들려면 테이블의 크기 조정이 빈번해야 한다
=> 최대 적재율과 테이블의 크기는 테이블 크기 조정 횟수에 영향을 끼침

생각해보기)-maxLoadFactor를 줄이거나 늘리면 어떻게 달라지나요? 어떤 상황에서 maxLoadFactor를 조절해야 할까요?

3-14. 생성자 복습

• 해시 == '연결리스트의 배열'

위 생성자 코드를 정리하여 작성하면,

public class Hash<K, V> implements HashI<K, V> {
	LinkedList<HashElement<K, V>>[] harray;
    int tableSize; int numElements;
    double maxLoadFactor;
    
    // Hash 생성자
    public Hash (int tableSize){ 
    	this tableSize = tableSize;
        maxLoadFactor = 0.75;
        numElements=0;
    	
        harray = (LinkedList<HashElement<K, V>>[]) new LinkedList[tableSize]; // hashElement로 만든 LinkedList들이 모인tableSize 크기의 배열
        // 자바의 배열은 사전에 타입을 결정해야 하므로 형변환하여 제작
        
        // 연결리스트 내부 확인용으로 배열을 만든 뒤 비교
        for (int i=0; i<tableSize; i++){ 
			harray[i] = new LinkedList<HashElement<K, V>>();
            // 위 반복문을 통해  빈 연결리스트들의 배열이 생성
    }
}

+)
-'현 적재율 > 최대 적재율'시, resize메소드 호출

생각해보기)-형 변환 과정이 필요한 이유는 무엇인가요?
답: 자바의 특성상 필요하다 이유는 제네릭 클래스에 존재

해설)
우선 자바는 제네릭의 특성으로 인해 제네릭으로 이루어진 배열을 바로 만들지 못한다(왜냐하면 자바의 배열은 타입을 정해주어야 하기 때문)
==> 이로 인해 위 코드에서 해시 배열을 만들 때, tableSize 크기인 연결리스트의 배열을 만든 뒤, 이를 제네릭 배열로 형변환하여 HashElement로 이루어진 배열을 얻는 방법을 사용한 것

3-15. add와 remove 메소드

• add 메소드
  -해시에 내용을 추가하는 메소드
  -배열의 크기에 따라 add 메소드에서 배열의 크기를 조절해야 한다
  이유: 추가하면서 크기 증가 및 메모리를 더 할당해야 하므로

<코드>

public boolean add(K key, V value){
	// resize - 크기 조정
	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;
    
	// 만들어둔 연결리스트에 추가할 데이터를 새로 add 
	harray[hashval].add(he); 

	numElements++;
	return true; 
}

-크기를 조정하는 순서는 본인 마음! 전에 하든, 후에 하든 상관x
-생성자는 타입 필요X
-추가할 때, 위치는 상관없음(addFirst메소드이든 addLast메소드이든 다 가능하나 구현도는 addFirst가 더 간편)

+) add메소드를 사용하여 값을 넣을 때,
-기존에 존재하는 key이면 에러가 발생
-기존에 존재하는 index이면 수정 발생
-존재하지 않은 index이면 추가

• remove 메소드
  -해시에 내용을 삭제하는 메소드
  -크기를 조정X ====> 이유: 차라리 makeEmpty같은 함수를 부르는 게 좋음
  -객체를 생성X

<코드>

public boolean remove(K key, V value){
	// index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
    
	// 해당하는 index의 키와 값 제거
	harray[hashval].remove(he);

	numElements--;
	return true;
}

생각해보기)-크기가 작아질 경우, add 메소드에서는 어떻게 크기를 조절하나요?