TIL 정리_80

 

 

add와 remove 메서드

해시를 추가하는 add 메서드 (boolean 반환)

 

public boolean add(K key, V value) { //제네릭 타입 지정 x
if(loadFactor() > maxLoadFactor) 
resize(tableSize * 2); //새로운 테이블의 크기를 계산
HashElement<K, V> he = new HashElement(key, value); //새로 추가할 요소 생성
int hashval = key.hashCode(); //추가할 인덱스 탐색 
hashval = hashval & 0x7FFFFFFF;
hashval = hashval % tableSize;

harray[hashval].add(he); //요소추가, 추가하는 방식은 상관 없다 
numElements++;
return true;
}

resize 메서드 : 
새로운 테이블의 크기를 계산하고 이 크기가 더 작더라도 해시를 조정할 수 있다 
-> 크기조정 메서드

resize 함수
하나의 값 배열의 새로운 크기인 int newSize를 인자로 받는다 

 

public void resize(int newSize) {
LinkedList<HashElement<K, V>>[] new_array = (LinkedList<HashElement<K, V>>[]) LinkedList[newSize];
for(int i = 0; i< newSize; i++) 
new_array[i] = new LinkedList<HashElement<K, V>>();
for(K key : this) { //모든 키에 대한 반복문
V val = getValue(key);
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;
}

해시크기를 바꾸는 법 정리 

1. 해시에 무언가를 추가할 때 적재율을 확인해야 한다
2. 최대 적재율을 확인하고, 만약 넘는경우에 크기가 얼마로 늘어나야하는지 확인해야 한다
   -> 크기를 늘리는 경우 보통은 원래 크기의 두 배로 설정한다 
3. resize 함수를 실행해서 새로운 배열을 생성하고, 데이터를 옮긴 후,  
   기존의 데이터를 모두 담은 new_array를 반환한다

-> 모든 데이터를 복사하고 복사본을 만들기 때문에 
해시에 무언가를 많이 추가하는 경우의 복잡도는 높다 

 

getValue 메서드 
해시 딕셔너리를 자주 이용하게 되는 경우 중 하나인 
키를 가지고 어떤 값을 찾고자 하는 경우에 getValue 메서드를 사용한다 

 

키의 위치를 찾는 코드 
public V getValue(K key) {
int hashval = key.hashCode() & 0x7FFFFFFF % tableSize;
for(HashElement<K, V> he : harray[hashval])
 //요소마다 돌아가며 찾고자 하는 키와 같은지 확인
if(((Comparable<K>)key).compareTo(he.key) == 0);
return he.val;
return null;
}
**이 코드는 이전에 정리한 hash를 이용하는 방법에 대한 개념들을 총합한 코드이다 


연결리스트 : 데이터를 맨 앞이나 뒤에 추가
해시 : 데이터의 순서를 보장할 수 없다
-> 해시코드(키)에 의해서 순서가 정해지기 때문이다
전체 크기를 바꾸어서 순서를 바꿀 수도 있다 (배열의 크기가 변경되면 모든 데이터의 순서가 변경된다)
대부분의 언어에서의 해시는 상수 시간을 복잡도로 갖지만 키와 값의 순서가 보장되지 않는다

 

 

해시에서의 반복자(Iterator) 
정렬을 하고 키를 반환하거나 반복문을 사용하기를 권장하기도 하지만 
반복자에서 키를 반환하기 전에 필수적으로 정렬을 할 필요는 없다 //주관적인 의견 중 하나이다 

-> 모든 키를 어떤 순서로든지 반환하는 것이다

 

 

반복자 helper class 생성

 

//해시를 만들고 해시를 탐색하면서 키를 찾아내서 값을 할당하는 배열을 생성한다

class IteratorHelper<T> implements Iterator<T> { //Iterator를 상속받는다
T[] keys;
int position; //각각의 키를 탐색할때 현재의 위치를 알기위한 변수
public IteratorHelper() {
keys = (T[]) Object[numElements]; //전역변수 numElements를 배열의 값으로 할당
int p = 0;
for(int i = 0; i<tableSize; i++) {
LinkedList<HashElement<K, V>> list = hash.array[i];
//연결리스트를 탐색하여 키 반환
for(HashELement<K, V> h : list) 
keys[p++] = (T)h.key(); 
}
position = 0; //position 변수 설정
}

public boolean hasNext() {
//위치가 keys의 길이보다 큰지 여부를 반환 작다면 반환할 수 있는 다른 객체가 존재해야 함
public T next() {
if(!hasNext()) return null;
return keys[position++]
}

 

 

코드 설명 
- 해시에서 모든 키를 꺼내서 keys라는 배열에 할당한다
- 카운터 변수로 p0라는 변수를 사용 -> 다음 요소가 있는지 확인한다 
- 요소가 있으면 이를 반환하고 카운터 변수를 증가시킨다 [p++] 
- i라는 변수를 이용하여 배열을 탐색한다
이때, 두 가지 키와 값의 움직임이 있음을 알아야 한다
- 반복자가 사용되기 전까지는 배열을 채우지 않는다 
-> 해시에 무언가를 추가하면 배열도 변하기 때문이다 
->> 해시에서 반복자를 사용하려고 할 때만 배열을 채우게 된다

 

해시에서는 순서는 보장할 수 없다 
시간 복잡도는 모든 키를 반환받아야 하기 때문에 O(n)이 된다 
해시 함수는 작은 값이 반환되지 않아도 된다.(== 작은값의 반환이 필수가 아니다) 

 

해시 함수가 가져야 할 특징 

• 빨라야 한다
• 같은 객체에 대해 같은 값을 반환해야 한다
• 데이터의 충돌을 피해야 한다
• 해시 테이블이 가득차서 새로운 배열을 만들 경우 기존 요소들을 재해시(Rehash)해야한다