배열과 배열의 요소가 리스트로 이루어진것을 체인해시라고 합니다.
이 해시는 키를 기반으로 저장이되어있습니다.
사용자는 키를 가지고 값을 찾아낼 수 있습니다.
다음은 키와 값을 저장하기위한 클래스입니다.
// 해시 클래스
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; // 요소의 개수
int tableSize; // 배열의 크기 (hashcode 값을 % 연산하기위해 필요함 )
double maxLoadfactor; // 최대적재율 (현재 적재율이 maxLoadfactor를 넘으면 크기조정을 해야하므로)
LinkedList<HashElement<K, V>> [] harray;
}키와 값이 무슨 타입이 될 지모르니 제네릭을 사용했습니다.
equals는 오버라이딩 하지 않았으모로 요소를 비교할때 메모리 위치를 비교하게 될 것입니다.
구현해야할 메소드는 HashElement와 해시요소를 찾을 때 비교를 위한 compareTo입니다.
생성자
위 코드에서 harry[]라는 연결리스트의 배열을 정의했습니다.
생성자를 이용해 사용할 변수들을 설정해줍니다.
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];
// 자바에서 제네릭으로 배열을 만드는 것은 어려우므로 객체로 만든 뒤 형변환
//tableSize 크기의 LinkedList배열 만듦.
// 연결 리스트 체이닝
for (int i=0; i<tableSize; i++)
harray[i] = new LinkedList<HashElement<K, V>>();
maxLoadFactor = 0.75;
numElements=0;
}
}키의 배열을 만들 땐 Object의 배열을 만들어주고 형 변환.
연결리스트를 미리 만드는 이유
요소를 추가할 때, 배열안의 위치로 가고 연결리스트가 있다면 추가할 때 까지 연결리스트를 탐색하고, 없으면 새로 만들어야합니다.
즉 hashCode를 구한 뒤, 양수로 바꿔주고 테이블 크기만큼 % 연산을 하고, 인덱스에가서 연결리스트가 없으면 null을 반환하고, 있으면 요소가 있는지 살펴보는 과정을 수행해야합니다.
어떤 작업을 하든 연결리스트가 있는지 확인을 해야합니다.
이 과정은 시간낭비이므로 위치마다 연결리스트를 함께 만들어주는 것입니다. 또한 이 연결리스트들은 힙을 가리키는 빈 공간이므로 메모리 문제도 할 필요가 없습니다.
크기
tableSize는 소수나 홀수여야 데이터가 더 골고루 지정될 수있습니다.
그렇지만 자바 API에서는 기본 테이블크기가 16으로 지정되어있습니다.
즉 maxLoadFactor = 0.75에서 Hash클래스는 12개가 추가되면 크기 조정이 될 것입니다.
maxLoadFactor는 개발자가 조정할 수 있습니다.
다만 크기 조정을 자주 하지 않기위해 초기테이블을 크게 만들면 위치를 찾아가는데 많은 시간이 사용됩니다.
그렇기때문에 일반적으로 최대 적재율은 0.75가 적절합니다.
이렇게 모두 구현이 되었습니다.
이제 new Hash()를 부르면 해시를 사용할 수 있습니다.
