방앗간

※ Key 반복자 - 모든 키에 대해 반복해 해시 전체 내용을 살펴본다. 시간 복잡도는 O(n) 이다. // 키에 연결된 연결 리스트의 내용을 살펴보는 함수 class IteratorHelper implements Iterator { T[] keys; int position; // key 반복자 사용 public IteratorHelper() { keys = (T[]) Object[numElements]; int p = 0; for (int i = 0; i < tableSize; i++){

※ resize - 연결 리스트가 너무 길어질 경우 해시 크기를 조절해 주는 resize 함수이다. 크기가 너무 커진경우, 새로운 연결 리스트 배열을 만들고 해시의 모든 연결 리스트에 있는 요소의 키와 값을 각각 찾아야 한다. public void resize(int newSize){ // 새로운 체인 해시 생성

※ getValue 메소드 - 해시에서 키의 값을 찾는 메소드, 키의 index가 무엇인지 찾고 해시에서 해당 index를 찾을 때 까지 반복하며 key의 값이 동일한 경우 키의 값을 반환한다. public V getValue(K key){ // 해당하는 index 찾기 int hashval = key.hashCode(); hashval = hashval & 0x7FFFFFFF; hashval = hashval & tableSize; // 해당 index 찾을 때 까지 반복 for(HashElement he : harray[hashval]){ if(((Comparablekey).compareTo(he.key)==0){ return he.val; } } return null; }

※ add, remove 메소드 - 해시에 내용을 추가하는 add 메소드이다. 크기가 너무 커지거나 작아지는 경우, add 메소드에서 크기 조절을 해주어야만 한다. public boolean add(K key, V value){ // resize if(loadFactor() > maxLoadFactor) resize(tableSize*2); // 키와 값을 저장해 놓을 object he 정의 HashElement he = new HashElement(key, value); // he의 index 찾기 int hashval = key.hashCode(); hashval = hashval & 0x7FFFFFFF; hashval = hashval % tableSize; // add he harray[hashv..

※ 생성자 - 해시의 키와 값을 저장해 줄 내부 클래스 HashElement가 있다면 해시를 구현하는 생성자도 있는데 이는 다음과 같다. public class Hash implements Hashl{ LinkedList[] harray; // 해시 구현 public Hash(int tableSize){ this tableSize = tableSize; harray = (LinkedList[]) new LinkedList[tableSize]; // 형 변환 // 연결 리스트 체이닝 for (int i = 0; i < tableSize; i++) harray[i] = new LinkedList(); maxLoadFactor = 0.75; numElements = 0; } }

※ 내부 클래스 - 체인 해시는 해시 요소마다 키와 그에 해당하는 값이 들어있는데 키와 값을 저장하기 위한 내부 클래스는 다음 예시와 같다. public class Hash implements Hashl{ class HashElement implements Comparable { // 키와 값 정의 K key; V value; public HashElement(K key, V value){ this.key = key; this.value = value; } //compareTo 함수 public int compareTo(HashElement h) return (((Comparableh.key).compareTo(this.key)) } }

※ 재해싱 - 체인 해시에서 해시가 너무 많이 차는 경우 크기 조정을 해야 할 필요가 있다. 예를들어, 우선 크기가 2배인 배열을 만들고 다음 코드에 따라 data의 index를 다시 결정해 연결 리스트의 요소들을 옮긴다. // data의 index 결정 int idx = x.hashCode(s); idx = idx & ox7FFFFFFF; idx = idx % tableSize; 연결 리스트의 위치를 그대로 하고 옮기면 정보를 다시 찾거나 제거하려 할 때 문제가 발생하는데 그 이유는 바로 정보의 위치를 지정할 때 다른 정보는 그대로이지만 tableSize만 바뀌기 때문이다. 그래서 각 요소의 위치를 초기화 한 뒤에 처음부터 다시 위치 지정을 해주어야 한다.

※ 체이닝(Chaining) - 요소마다 연결 리스트를 생성해 수많은 데이터를 수용할 수 있게 하는 방법으로 체인 해시는 가장 안정적이면서 보편적으로 사용되는 자료 구조 중 하나이다. 체이닝을 하면 수용 가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없다. 적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값이고 체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있다. 하지만 hashCode가 같은 숫자만 반환해 하나의 체인이 지나치게 길어진 경우 연결 리스트와 시간 복잡도가 같아지는 문제가 발생한다.

※ 충돌 해결 방법 1. 선형 조사법(linear probing) - 채우려고자 하는 공간이 이미 차 있는 경우, 비어있는 칸을 발견할 때 까지 다음 칸을 확인하는 방법이다. 비어있는 칸을 찾아 해당 공간을 채운 후 위치가 바뀐 사실을 알려야 한다. 2. 2차식 조사법(quadratic probing) - 다음 칸 대신 1부터 순서대로 제곱해 더한 칸을 확인하는 방법이다. 테이블의 끝을 넘어가는 경우 % 연산을 이용하여 다시 테이블의 범위 안으로 들어올 수 있도록 한다. 3. 이중 해싱(double hashing) - hashCode 함수가 2개 있어 채우려는 공간이 이미 차 있는 경우 두 hashCode의 결과를 더한 값을 테이블 내의 위치가 되게 하는 방법이다. 여기서 이중 해싱은 아예 다른 함수를 ..

※ LoadFactor 메소드 - LoadFactor(적재율)은 해시(테이블)에 데이터가 얼마나 있는지 알려준다. 적재율은 λ로 표기하고 항목 수를 자료 구조의 크기만큼 나눈 값이다. 또한, λ의 크기에 따라 해시 충돌이 일어나지 않도록 해시의 크기를 조절해 준다.