4주차 해시2
3-10. 재해싱(Rehashing)
-의미: chain hash에서 해시가(배열이) 너무 많이 차면 위 사진처럼 배열의 크기를 조정해야 한다
- Chain hash에서 적재율이 1 이상이 될 수 있지만 그렇다고 해서 너무 커지면 안된다
이유: 연결리스트 내에 무언가를 찾을 경우, 시간복잡도 상승
ex) 하는 방법
1) 크기가 2배인 배열 만들기
2) 아래 코드에 따라 data의 index를 다시 결정하여 연결 리스트의 요소들을 옮긴다
// data의 index 결정
int idx = x.hashCode(s);
idx = idx & ox7FFFFFFF;
idx = idx % tableSize;
- 그렇다면 위 사진같이 chain hash에서 배열의 크기를 재조정하는 경우, 연결리스트는 그대로 옮겨야 할까?
===> 답: No!
이유: 만약 연결리스트의 위치를 그대로 하여 옮기면 다시 정보를 찾거나 제거하는 경우, 문제 발생!(배열의 크기가 조정되면서 테이블의 크기인 tableSize가 바뀌어 우리가 index를 구할 때 테이블의 크기만큼 '%'연산하여 값을 얻어 값이 달라지기 때문에 원래 index의 위치에 연결리스트를 넣으면 오류가 발생한다)
So!!
Chain Hash에 재해시 하는 방법
1. 각 요소의 위치를 초기화
2. 처음부터 다시 위치를 지정해주어야 한다
3. 아까와 다르게 지정된 위치에 연결리스트가 옮겨진다
올바른 결과물
-코드는 위와 같은 코드를 적용하여 크기 재조정
생각해보기)-정리했던 물건들이 쌓여 다시 정리하신 적이 있으신가요? 어떻게 정리하셨었나요?
3-11. 해시 클래스
-
Chain Hash는 해시 요소마다 key와 value가 들어있다. 여기서 key와 value를 저장하기 위한 내부클래스를 우리가 만들 수 있다
-
내부클래스는 key를 기반으로 hash에 넣는 모습이며, key의 hashCode에서 반환된 값에 따라 value가 저장할 위치를 고르게 된다
==> key 재설정 및 value 변경 등 모든 게 가능해진다
// 해시 클래스
public class Hash<K, V> implements HashI<K, V> {
class HashElement <K, V> implements Comparable <HashElement<K, V>>{
// 키와 값 정의
K key;
V value;
public HashElement (K key, V value) {
this.key = key;
this.value = value;
}
// compareTo 함수 - 다른 해시와 값이 같은지 비교를 위해 사용
public int compareTo (HashElement<K, V> o)
return (((Comparable<K>)this.key).compareTo(o.key))
}
// 해시에 사용할 전역 변수
int numElements, tableSize;
double maxLoadfactor;
LinkedList<HashElement<K, V>> [] harray;
// 연결리스트의 배열로 위에 생성한 해시 내부 클래스로 이루어진 해시 배열이며
// 형태는 결정해두지 않아 []라고 작성한다
}+)위 코드 내 사용처
HashI 인터페이스 -> 메소드 정의
Comparable -> 형변환
compareTo메소드 -> 값호출
tableSize -> 해시함수 생성시 %연산할 때 사용
maxLoadfactor -> 적재율을 통해 크기 조정해야 할 크기인가 확인
제네릭 클래스
생각해보기)-해시 클래스에서 사용할만한 함수에는 어떤 것이 있을까요?
3-12. 내부 클래스
-위 코드에서 hash의 key와 value를 생성하여 저장하는 내부 클래스에 대해 더욱 자세하게 파해쳐보자
- 목표: key와 value를 어떻게 담는가
<내부 클래스>
public class Hash<K, V> implements HashI<K, V> {
class HashElement <K, V> implements Comparable <HashElement<K, V>>{
// 키와 값 정의
K key;
V value;
public HashElement (K key, V value) { // 생성자
this.key = key;
this.value = value;
}
// 정수 반환& 다른 Hash와 비교 용 - compareTo 함수
public int compareTo (HashElement<K, V> h)
return (((Comparable<K>)h.key).compareTo(this.key))
}
}Comparable 인터페이스로 구현한 클래스는 compareTo()메소드를 통해 값을 비교한다.
-이를 통해 같은 key가 이미 해시 내에 존재하는지 비교 가능
===> 위 과정을 거쳐 해시요소들이 만들어지면 해시로 이루어진 배열에 넣는다
+)
제네릭 타입에 알아두기! ex) K,V,E...
