Java-자료구조 3주차 Hash 3 - 16 ~ 18

4주차 해시
3-16. getValue 메소드
-Key의 값인 value를 얻는 메소드
-key의 index를 찾고서 해시에서 그 index를 찾은 뒤, 동일하면 그 때 key에 해당하는 value를 return한다
-getValue의 메소드에서 해당하는 key는 입력값

<코드>

public V getValue(K key){ 
	// 해당하는 index 찾기
	int hashval = key.hashCode();
	hashval = hashval & 0x7FFFFFFF;
	hashval = hashval % tableSize;
    
	// 연결리스트에서 index에 해당하는 부분를 찾을 때까지 반복
	for (HashElement<K, V> he : harray[hashval]){
		if (((Comparable<K>)key).compareTo(he.key) == 0){
			return he.val; // 해당하는 key의 value 반환
                }
        }
    
    // 해당 부분을 찾지 못하면 null 반환
	return null;
}

-index는 'key의 위치'
-위치를 파악하는 방법을 통해 시간복잡도가 O(1)에 해당하는 속도로 찾게 만든다

생각해보기)-getValue 메소드의 시간 복잡도는 무엇인가요?

3-17. resize 메소드
-연결리스트가 어느 위치에서 너무 길어지는 경우(크기가 커진다면) 호출하는 함수
이유: 연결리스트가 길어지면 데이터 찾기에 Bad

resize 메소드 과정
1. 새 연결리스트 array 생성
2. 현재 존재하는 모든 연결리스트의 요소와 key, value를 각각 찾아낸다

<코드>

public void resize(int newSize){
	// 새로운 체인 해시 생성
	<LinkedList<HashElement<K, V>>[] new_array = ...;
	(<LinkedList<HashElement<K, V>>[]) LinkedList[newSize]; // 배열 형성
    
    // 넣을 적절한 index 찾기
	for (int i=0; i<newSize; i++)
		new_array[i] = new <LinkedList<HashElement<K, V>>[]; // 비어있는 새 연결리스트 생성
        
	// index에 맞게 연결리스트에 값 채워넣기
	for (k key : this) {
		V val = getValue(key); // 해당하는 key의 value 찾기
		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;
}

-해시: '연결리스트의 배열'
-영상 반복 시청 필수!
-모든 데이터를 복사하고 반복하여 시간복잡도는 높은 편(시간복잡도와 배열의 크기는 서로 비례)

생각해보기)-resize 함수의 시간 복잡도는 무엇인가요?

3-18. Key 반복자
-모든 key에 대해 반복하여 해시 전체를 살피는 메소드에 사용
-이 메소드의 경우, 시간복잡도: O(n)
-data는 자신의 순서를 보장X(이유: key에 의해 순서가 나옴)
-key도 순서를 보장X
---> So, 보통 먼저 key를 정렬하면서 key 반환 및 반복문을 사용하는 편이지만 현재 강의에서는 모든 key를 구하고서 정렬은 필수가 아닌 선택사항이라고 하는 편!(이는 Key 반복자에만 해당되는 부분)

<코드>

• 포인트!
  모든 키를 어떤 순서로 반환할 지 결정한다

// 키에 연결된 연결 리스트의 내용을 살펴보는 함수
class IteratorHelper<T> implements Iterator<T>{
	T[] keys;
	int position; // 각각의 key를 탐색할 때 탐색한 위치
    
	// key반복자 사용
	public IteratorHelper(){
		keys = (T[]) Object[numElements];
		int p=0; // 현재 위치
		for (int i=0; i<tableSize; i++) {
			<LinkedList<HashElement<K, V>> list = hash.array[i]; // 연결리스트는 해시 배열의 i 위치에 존재하는 연결리스트
			for (HashElement<K, V> h : list)
            // h - list 내 해시 요소 안의 data
				keys[p++] = (T) h.key(); // 형 변환은 T로 받았기에 필수
		}
        
		position=0;
	}
	// 끝을 확인할 때 사용
	public boolean hasNext(){
		return position < keys.length;
        // position == 0이면 마지막이고,
        // position != 0이면 마지막이 아님
	}
}
// 해시의 전체 내용을 살펴보는 함수
	public T next(){
		if (!hasNext())
			return null;
		return keys[position++]; // 다음 데이터로 옮긴다 
	}

-위 코드 내 Iterator를 상속받으며, hasNext 함수나 next 함수가 필요해진다

역할)
hasNext():읽어올 요소가 남아있는지 판별하는 메소드로 요소가 남아있다면 True, 없으면 False
next(): 그 다음 데이터가 있는 곳으로 이동

-키를 반환하면 반환되는 키에 정해진 순서도 없으며, key의 순서도 당연히 정해지지 않는다

생각해보기)-해시에는 순서가 있나요?