TIL 정리_79

재해싱
충돌을 피하기 위한 대표적인 방법으로는 해시 체인이 있다
-> 배열의 칸마다 리스트를 배정하는 방식

자료구조가 할당될수록 크기를 조정해야 한다 
체인해시에서 해시가 너무 많이 할당되면 마찬가지로 크기 조정을 해야 한다 
-> 새로운 해시로 모든 요소를 옮겨야 한다

 

객체를 해시에 추가하려면 우선적으로 hashCode 메서드를 호출해야 한다 
int hv = x.hashCode();
hv = hv & 0x7FFFFFFF;
hv = hv % tableSize;

 

다시 찾거나 제거하고자 할 때 위치 0의 연결리스트를 위치 0으로 옮기면 안된다
배열을 크기를 조정하면서 테이블의 크기가 바뀌었기 때문이다
->각 요소의 위치를 초기화 한 후, 처음부터 다시 위치를 지정해야 한다 

새로운 테이블에 빈 연결리스트를 만든 뒤 
연결리스트의 첫 요소 a의 a.hashCode를 구하고 양수로 변환한 뒤

새로운 테이블의 크기만큼 % 연산을 해야 한다 
int h=  = a.hashCode();
h = h & 0x7FFFFFFF;
h = h % newtableSize;


정리
테이블의 크기를 조정하기 위한 유일한 방법은
1 연결리스트가 들어있는 새로운 배열을 만들고
2 요소마다 hashCode를 다시 구한 뒤
3 양수로 바꿔주고 새로운 테이블의 크기만큼 % 연산을 한다
-> 이후 그 위치에 있는 연결리스트에 추가한다

이렇게 hashCode 기반으로 위치를 찾아야야 요소를 다시 찾을 수 있다 


해시 클래스 
체인 해시 : 위치마다 연결리스트가 들어있는 배열 
해시 요소가 들어가 있고 해시 요소에는 키와 값이 들어가 있다
-> 자바에서는 제네릭을 이용하여 키와 값을 구한다

 

Hash 클래스는 HashI 인터페이스를 구현한다
HashI 인터페이스는 여기서 구현해야 할 메서드들을 정의한다
Comparable : 두 개의 해시 요소를 비교하기위해 필요하다 

public class Hash<K, V> 
//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;
}
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;
}
int numElements, tableSize //요소의 개수와 테이블의 크기

두 개의 해시 요소를 비교 할 때 Object 클래스의 equals 메서드를 사용한다
-> 메모리 위치 비교 
toString hashCode를 오버라이딩 하지 않아도 
내부 클래스에서 구현하였기 때문에 comparable만 구현해도 된다.

 

hashCode의 값을 양수로 만든 뒤 %연산을 해야하기 때문에 이들의 값을 알아야 한다

double maxLoadFactor //최대 적재율 
최대 적재율 : 현재 적재율이 이 변수값을 넘게 되면 크기 조정을 해야한다
이 값은 생성자 안에서 설정할 수 있다 

**LinkedList<HashElement<K, V>>[ ] harray; 
제네릭 안에 제네릭이 있는 구조이다

 

생성자
사용할 변수들을 설정하는 생성자 public Hash
생성자를 통해 사용자가 테이블의 크기를 설정할 수 있다 
key의 배열
K[] keys = (K[]) new Object[0];

 

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;  //자료구조에 아무것도 없다
}

-> 해시를 사용하고 싶을 때 new Hash()를 부르면 위의 데이터를 생성할 수 있다 

배열을 선언할 때 테이블의 크기가 홀수면 다양한 수가 생성된다

 

연결리스트가 골고루 생기게 하기 위해서는 크기 조정을 자주 해야 한다
-> 적재율과 테이블의 크기를 낮게해야한다

 

자바 API에서 기본 테이블의 크기는 16이다
기본 maxLoadFactor는 0.75이다
기본 Hash 클래스에 12번째 요소를 추가 할때 테이블의 크기를 조정한다 
많은 데이터를 넣기위한 자료구조를 만들려면 초기 테이블 크기를 큰 숫자로 설정해야 한다
적재율이 1.2 혹은 1.5처럼 높으면 연결리스트의 크기는 커지지만 크기 조정을 덜 할 수 있다