11. 해시 클래스
package 해시;
import java.util.Iterator;
import java.util.LinkedList;
/**
* 해시에서 필요한 메서드를 정의
* 추가, 삭제, 탐색, 크기 조정 메서드
*/
interface HashI<K, V> {
boolean add(K key, V value);
boolean remove(K key, V value);
V getValue(K key);
void resize(int newSize);
}
public class Hash<K, V> implements HashI<K, V> {
/**
* 해시 체인의 데이터를 담당하는 내부 클래스
* @param <K>
* @param <V>
*/
static 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;
}
/**
* 값이 동일하다고 같다고 판단하지 않고 키의 동일성을 비교
* @param h, the object to be compared.
* @return 키 값의 비교 결과
*/
@Override
public int compareTo(HashElement<K, V> h) {
return (((Comparable<K>)h.key).compareTo(this.key));
}
}
int numElements, tableSize; // 요소의 개수, 배열의 크기
double maxLoadFactor; // 최대 적재율, 이 변수값을 넘게 되면 크기 조정이 필요
LinkedList<HashElement<K, V>>[] hashArray; // 체인 해시, 연결 리스트 배열
IteratorHelper<K> iteratorHelper;
public Hash(int tableSize) {
this.tableSize = tableSize;
// 객체로 배열을 만든 뒤 형변환 필요
hashArray = (LinkedList<HashElement<K, V>>[])new LinkedList[tableSize];
for (int i = 0; i < tableSize; i++) {
hashArray[i] = new LinkedList<HashElement<K, V>>();
}
iteratorHelper = new IteratorHelper<>();
maxLoadFactor = 0.75; // 0.75 이상이 되면 tableSize 를 늘린다
numElements = 0; // 생성 시 자료구조에 아무것도 없기 때문에 0
}
public double getLoadFactor() {
return numElements / tableSize;
}
@Override
public boolean add(K key, V value) {
// resize
if (getLoadFactor() > maxLoadFactor) {
resize(tableSize * 2);
}
// 키와 값들을 저장할 요소
HashElement<K, V> hashElement = new HashElement(key, value);
int hashValue = key.hashCode(); // 저장할 위치
hashValue = hashValue & 0x7FFFFFFF;
hashValue = hashValue % tableSize;
hashArray[hashValue].add(hashElement); // 해당 위치에 요소 추가
numElements++; // 요소 개수 값을 증가
return true;
}
@Override
public boolean remove(K key, V value) {
int hashValue = key.hashCode(); // 제거할 위치 찾기
hashValue = hashValue & 0x7FFFFFFF;
hashValue = hashValue % tableSize;
hashArray[hashValue].remove(); // 해당 위치의 요소 삭제
numElements--; // 요소 개수 값을 감소
return true;
}
/**
* Best Case: O(1), Worst Case: O(N)
* @param key, 찾고자 하는 값의 키
* @return Value
*/
@Override
public V getValue(K key) {
int hashValue = key.hashCode(); // Key 인덱스 찾기
hashValue = hashValue & 0x7FFFFFFF;
hashValue = hashValue % tableSize;
for (HashElement<K, V> he : hashArray[hashValue]) {
if (((Comparable<K>)key).compareTo(he.key) == 0) { // 키를 비교해 동일성 확인
return he.value;
}
}
return null;
}
@Override
public void resize(int newSize) {
// 크기 조정을 한 새로운 배열
LinkedList<HashElement<K, V>>[] temp
= (LinkedList<HashElement<K, V>>[])new LinkedList[newSize];
for (int i = 0; i < newSize; i++) {
temp[i] = new LinkedList<HashElement<K, V>>();
}
// 새로운 크기에 맞게 기존 값들을 가져오기
for (K key : this.iteratorHelper.keys) {
V value = getValue(key);
HashElement<K, V> hashElement = new HashElement<>(key, value);
int hashValue = (key.hashCode() & 0x7FFFFFFF) % newSize;
temp[hashValue].add(hashElement);
}
hashArray = temp; // 복사
tableSize = newSize; // 크기 갱신
}
class IteratorHelper<T> implements Iterator<T> {
T[] keys;
int position;
public IteratorHelper() {
keys = (T[]) Object[numElements];
int p = 0;
for (int i = 0; i < tableSize; i++) {
LinkedList<HashElement<K, V>> list = hashArray[i];
for (HashElement<K, V> he : list) {
keys[p++] = (T)he.key;
}
}
position = 0;
}
@Override
public boolean hasNext() {
return position < keys.length;
}
@Override
public T next() {
if (!hasNext()) {
return null;
}
return keys[position++];
}
}
}
- Java API 에서도 maxLoadFactor 는 0.75로 설정 (크기를 모를 때 제일 적절한 값)
- 최대 적재율을 줄이면 연결 리스트에 더 골고루 분포될 수 있지만 크기 조정이 자주 일어나 시간적으로 비효율
- 최대 적재율을 늘리면 비교적 크기 조정이 가끔 일어나 시간적으로 효율적이지만 데이터가 골고루 분포되지 않을 수 있음
- 지네릭은 왜 형변환이 필요하나
- 타입소거로 인해 자바에서 지네릭으로 배열을 만들지 못한다. 자바의 배열은 타입 지정이 필수
- 타입소거: 컴파일 시 검사를 하고 런타임에는 검사를 하지 않는 것. 즉, 컴파일 시에만 타입에 대한 제약 조건을 적용하고, 런타임에는 타입에 대한 정보를 소거하는 프로세스
- 생성자 복습
public class Hash<K, V> implements HashI<K, V> {
LinkedList<HashElement<K, V>>[] hashArray;
int tableSize, numElements;
double maxLoadFactor;
public Hash(int tableSize) {
this.tableSize = tableSize;
// 객체로 배열을 만든 뒤 형변환 필요
hashArray = (LinkedList<HashElement<K,V>>[]) new LinkedList[tableSize];
for (int i = 0; i < tableSize; i++) {
hashArray[i] = new LinkedList<HashElement<K, V>>();
}
maxLoadFactor = 0.75; // 0.75 이상이 되면 tableSize 를 늘린다
numElements = 0; // 생성 시 자료구조에 아무것도 없기 때문에 0
}
12. add(), remove()
add(): 요소 추가 메서드
- 요소를 추가하다 적재율이 높아지면 resize 필요
@Override
public boolean add(K key, V value) {
// resize
if (getLoadFactor() > maxLoadFactor) {
resize(tableSize * 2);
}
// 키와 값들을 저장할 요소
HashElement<K, V> hashElement = new HashElement(key, value);
int hashValue = key.hashCode(); // 저장할 위치
hashValue = hashValue & 0x7FFFFFFF;
hashValue = hashValue % tableSize;
hashArray[hashValue].add(hashElement); // 해당 위치에 요소 추가
numElements++; // 요소 개수 값을 증가
return true;
}
@Override
public boolean remove(K key, V value) {
int hashValue = key.hashCode(); // 제거할 위치 찾기
hashValue = hashValue & 0x7FFFFFFF;
hashValue = hashValue % tableSize;
hashArray[hashValue].remove(); // 해당 위치의 요소 삭제
numElements--; // 요소 개수 값을 감소
return true;
}
13. getValue()
getValue(): 해당 키의 값을 탐색하는 메서드
- 키의 index를 계산해 해당 위치의 값을 반환하는 메서드
- 연결 리스트의 요소가 1~2개일 경우에는 key에 대응되는 value를 O(1)의 시간복잡도로 찾을 수 있음. (Best Case)
- hashCode의 리턴값 또는 나머지 연산의 결과값이 중복되어 해시 충돌이 빈번하게 발생하는 경우 연결 리스트의 길이가 늘어나면서 key값 비교에 걸리는 시간이 O(N)로 증가할 수 있음. (Worst Case)
@Override
public V getValue(K key) {
int hashValue = key.hashCode(); // Key 인덱스 찾기
hashValue = hashValue & 0x7FFFFFFF;
hashValue = hashValue % tableSize;
for (HashElement<K, V> he : hashArray[hashValue]) {
if (((Comparable<K>)key).compareTo(he.key) == 0) {
return he.value;
}
}
return null;
}
14. resize()
- resize(): 연결 리스트가 너무 길어질 경우 탐색의 시간 복잡도가 매우 올라감, 이를 해결하기 위해 크기를 조절하는 메서드가 필요
- 모든 데이터를 복사, 복사본을 만들기 때문에 복잡도가 높음: 시간 복잡도 O(N)
@Override
public void resize(int newSize) {
// 크기 조정을 한 새로운 배열
LinkedList<HashElement<K, V>>[] temp
= (LinkedList<HashElement<K, V>>[])new LinkedList[newSize];
for (int i = 0; i < newSize; i++) {
temp[i] = new LinkedList<HashElement<K, V>>();
}
// 새로운 크기에 맞게 기존 값들을 가져오기
for (K key : this) {
V value = getValue(key);
HashElement<K, V> hashElement = new HashElement<>(key, value);
int hashValue = (key.hashCode() & 0x7FFFFFFF) % newSize;
temp[hashValue].add(hashElement);
}
hashArray = temp; // 복사
tableSize = newSize; // 크기 갱신
}