본 내용은 http://www.algolist.net/Data_structures/Hash_table의 내용을 편역한 것이다.
해시 테이블
해시 테이블(혹은 해시 맵)은 사전 ADT(추상 자료 구조)의 가능한 구현 중 하나이다. 그렇기 때문에, 기본적으로 그것은 유일한 키를 연관된 값에 사상한다. 구현 관점에서, 해시 테이블은 배열 기반의 자료 구조이고, 해시 함수를 이용해서 키를 연관된 값이 검색되어지는 배열 요소의 색인 값으로 변경하는데 해시 함수를 이용한다.
해시 함수
해시 함수는 해시 테이블 설계의 매우 중요한 함수이다. 해시 함수는 해시 값들이 균등하게 분포될 때 좋다고 여겨진다. 해싱의 품질을 위해 요구되는 다른 해시 함수의 특성은 차후에 살펴보겠다. 우리가 해시 함수에 주요한 관심을 가지는 이유는 나쁜 해시 함수는 충돌을 일으키고, 해시 테이블의 전반적인 성능에 나쁜 영향을 미치는 것과 같은 원치 않은 효과를 야기하기 때문이다.
해시 테이블과 로드 팩터
해시 테이블을 저장하기 위해서 그 기반에 이용되는 자료 구조는 배열이다. 로드 팩터는 저장된 아이템의 수와 배열 크기 사이의 비율이다. 해시 테이블은 상수 크기이거나 특정 경계 값을 로드 팩터가 넘었을 때 동적으로 크기가 조절될 수 있다. 테이블이 꽉 차기 전에 충돌의 횟수를 특정 값 이하로 유지하고 성능 하락을 방지하기 위해서 크기 조절이 일어난다.
충돌
다른 키에 대해서 같은 해시 값을 해시 함수에서 반환하면 무슨 일이 일어날까? 그것은 충돌이라고 불리는 효과를 만든다. 충돌은 실제적으로 회피가 불가능하고, 해시 테이블을 구현하는 사람은 이것을 고려해야 한다. 키 역시 테이블에 저장되기 때문에, 충돌이 일어났을 때, 우리는 키-값 쌍들이 같은 값을 가졌는 지 판별할 수 있다. 여기에는 다양한 방법의 충돌 해결책이 있다. 기본적으로, 두개의 다른 전략이 있다.
- 닫힌 주소(열린 해싱): 해시 테이블의 각 슬롯은 다른 자료 구조로의 연결(가령, 연결 리스트)을 가지고 있고, 이 자료 구조는 같은 해시값을 가진 키-값 쌍을 저장한다. 충돌이 발생할 때, 이 자료구조에 대해서 같은 키 값을 가진 키-값 쌍이 검색되어 진다.
- 열린 주소(닫힌 해싱): 각 슬롯이 실제로 키-값 쌍을 저장한다. 충돌이 일어날 때, 열린 주소 알고리즘은 빈 슬롯을 찾기 위해서 다른 위치(가령, 다음 슬롯)를 계산한다. 열린 주소 전략을 가진 해시 테이블은 테이블이 빽빽하게 차 있을 때(로드 팩터가 0.7 이상) 급격한 성능 하락을 경험할 수 있게 된다.
다음은 http://www.algolist.net/Data_structures/Hash_table/Simple_example의 내용을 편역한 것이다.
매우 단순한 해시 테이블 예제
이 글에서, 우리는 매우 단순한 해시 테이블 에제를 보인다. 그것은 단순한 해시 함수를 이용하고, 충돌은 선형 검색(열린 주소 전략)을 이용해서 해결되고 해시 테이블은 상수 크기를 가진다. 이 예제는 기본 해싱 기술을 보인다.
해시 테이블
기반 배열은 128개의 요소를 저장하기 위해 상수 크기를 가지고 각 슬롯은 키-값 쌍을 가지고 있다. 키는 같은 해시 값을 가진 키-값 쌍을 구분하기 위해 저장된다.
해시 함수
테이블은 오직 정수를 값으로 가지는 것을 허용한다. 해시 함수는 128에 의해 나눠진 나머지 값을 취한다. 구현 관점에서, 이 해시 함수는 나머지 연산자 혹은 127과의 AND 비트 연산으로 구현될 수 있다.
주의. 2의 제곱수 크기의 테이블이 실제적으로 자주 이용된다(가령 자바에서). 사용되어질 때, 주 해시 함수에 추가적으로 적용된 특별한 해시 함수가 있다. 이 방식은 하위 비트에서 차이가 없는 해시 값이 발생했을 때 충돌을 방지한다.
충돌 해결 전략
선형 검색은 충돌 해결을 위해서 적용된다. 해시 함수에 의해서 나타내어진 슬롯이 이미 차 있는 경우, 알고리즘은 배열에서 바로 다음 순서에 있는 슬롯을 검색함으로써 비어있는 슬롯을 찾으려고 시도한다.
주의. 선형 검색은 상수 크기 테이블에 대해 사용될 때 최선의 기술이 아니다. 로드 팩터가 특정한 값(대략 0.7)을 넘어갈 때, 해시 테이블의 성능은 비 선형적으로 감소할 것이다. 또한, 저장된 키-값 쌍들은 테이블의 크기(128)에 의해 제한된다.
코드 조각
이 구현은 한 가지 버그를 가진다. 테이블에 더 이상 공간이 없을 때, 비어있는 슬롯을 찾기 위한 코드에서 무한 루프를 돌게 된다. 이것은 열린 주소 방식의 실제 해시 테이블 구현에서는 나타나지 않는 현상일 것인데, 이는 대부분의 경우 동적 크기 조절이 가능한 테이블로 구현되기 때문이다. 또한, 삭제 구현이 단순함을 유지하기 위해서 생략 되었다. 열린 주소 전략에 대한 전체 구현은 다음 다음 절에 나온다.
자바 구현
public class HashEntry {
private int key;
private int value;
HashEntry(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
}
public class HashMap {
private final static int TABLE_SIZE = 128;
HashEntry[] table;
HashMap() {
table = new HashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int get(int key) {
int hash = (key % TABLE_SIZE);
while (table[hash] != null && table[hash].getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
if (table[hash] == null)
return -1;
else
return table[hash].getValue();
}
public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
while (table[hash] != null && table[hash].getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
table[hash] = new HashEntry(key, value);
}
}
C++ 구현
class HashEntry {
private:
int key;
int value;
public:
HashEntry(int key, int value) {
this->key = key;
this->value = value;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
};
const int TABLE_SIZE = 128;
class HashMap {
private:
HashEntry **table;
public:
HashMap() {
table = new HashEntry*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
}
int get(int key) {
int hash = (key % TABLE_SIZE);
while (table[hash] != NULL && table[hash]->getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
if (table[hash] == NULL)
return -1;
else
return table[hash]->getValue();
}
void put(int key, int value) {
int hash = (key % TABLE_SIZE);
while (table[hash] != NULL && table[hash]->getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
if (table[hash] != NULL)
delete table[hash];
table[hash] = new HashEntry(key, value);
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; i++)
if (table[i] != NULL)
delete table[i];
delete[] table;
}
};
다음은 http://www.algolist.net/Data_structures/Hash_table/Chaining의 내용을 편역한 것이다.
체이닝
체이닝은 충돌을 해결하는 가능한 방법이다. 배열의 각 슬롯은 같은 해시 값을 가지는 키-값 쌍을 포함하는 단일 연결 리스트로의 연결을 가진다. 새로운 키-값 쌍들은 리스트의 끝으로 추가된다. 검색 알고리즘은 일치하는 키를 찾기 위해서 리스트에 대해서 검색을 수행한다. 초기에 테이블 슬롯들은 널 값을 포함한다. 리스트가 생성되고, 특정 해시 값을 가진 값이 나타났을 때 처음으로 값이 추가된다.
체이닝 그림
복잡도 분석
해시 함수가 해시 코드를 균등하게 분할하고 테이블이 동적 크기 조절을 허용한다고 가정하면, 삽입, 삭제, 검색 연산의 대략적인 시간은 상수이다. 그들 연산을 선형으로 수행하는데 실제로 소요되는 시간은 테이블의 로드 팩터에 의존한다.
주의. 체이닝에 기반한 해시테이블은 아무리 과도하게 값이 추가되어도, 좋은 성능을 보인다. 100 개의 슬롯을 가지고 100000 개의 요소들(로드 팩터는 100)을 저장한다고 가정하다. 이것은 단일 연결 리스트 보다 약간의 메모리(테이블의 크기)를 더 사용하지만, 기본 연산들은 평균적으로 1000배 이상 빠르게 동작할 것이다. 주목할 것은 단일 연결 리스트와 상수-크기 해시 테이블의 연산 복잡도가 O(n)이라는 점이다.
체이닝 대 열린 주소
이것은 다음에 나오는 열린 주소 대 체이닝 절을 참고하기 바란다.
코드 조각
자바 구현
public class LinkedHashEntry {
private int key;
private int value;
private LinkedHashEntry next;
LinkedHashEntry(int key, int value) {
this.key = key;
this.value = value;
this.next = null;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getKey() {
return key;
}
public LinkedHashEntry getNext() {
return next;
}
public void setNext(LinkedHashEntry next) {
this.next = next;
}
}
public class HashMap {
private final static int TABLE_SIZE = 128;
LinkedHashEntry[] table;
HashMap() {
table = new LinkedHashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int get(int key) {
int hash = (key % TABLE_SIZE);
if (table[hash] == null)
return -1;
else {
LinkedHashEntry entry = table[hash];
while (entry != null && entry.getKey() != key)
entry = entry.getNext();
if (entry == null)
return -1;
else
return entry.getValue();
}
}
public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
if (table[hash] == null)
table[hash] = new LinkedHashEntry(key, value);
else {
LinkedHashEntry entry = table[hash];
while (entry.getNext() != null && entry.getKey() != key)
entry = entry.getNext();
if (entry.getKey() == key)
entry.setValue(value);
else
entry.setNext(new LinkedHashEntry(key, value));
}
}
public void remove(int key) {
int hash = (key % TABLE_SIZE);
if (table[hash] != null) {
LinkedHashEntry prevEntry = null;
LinkedHashEntry entry = table[hash];
while (entry.getNext() != null && entry.getKey() != key) {
prevEntry = entry;
entry = entry.getNext();
}
if (entry.getKey() == key) {
if (prevEntry == null)
table[hash] = entry.getNext();
else
prevEntry.setNext(entry.getNext());
}
}
}
}
C++ 구현
class LinkedHashEntry {
private:
int key;
int value;
LinkedHashEntry *next;
public:
LinkedHashEntry(int key, int value) {
this->key = key;
this->value = value;
this->next = NULL;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
void setValue(int value) {
this->value = value;
}
LinkedHashEntry *getNext() {
return next;
}
void setNext(LinkedHashEntry *next) {
this->next = next;
}
};
const int TABLE_SIZE = 128;
class HashMap {
private:
LinkedHashEntry **table;
public:
HashMap() {
table = new LinkedHashEntry*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
}
int get(int key) {
int hash = (key % TABLE_SIZE);
if (table[hash] == NULL)
return -1;
else {
LinkedHashEntry *entry = table[hash];
while (entry != NULL && entry->getKey() != key)
entry = entry->getNext();
if (entry == NULL)
return -1;
else
return entry->getValue();
}
}
void put(int key, int value) {
int hash = (key % TABLE_SIZE);
if (table[hash] == NULL)
table[hash] = new LinkedHashEntry(key, value);
else {
LinkedHashEntry *entry = table[hash];
while (entry->getNext() != NULL)
entry = entry->getNext();
if (entry->getKey() == key)
entry->setValue(value);
elseentry->setNext(new LinkedHashEntry(key, value));
}
}
void remove(int key) {
int hash = (key % TABLE_SIZE);
if (table[hash] != NULL) {
LinkedHashEntry *prevEntry = NULL;
LinkedHashEntry *entry = table[hash];
while (entry->getNext() != NULL && entry->getKey() != key) {
prevEntry = entry;
entry = entry->getNext();
}
if (entry->getKey() == key) {
if (prevEntry == NULL) {
LinkedHashEntry *nextEntry = entry->getNext();
delete entry;
table[hash] = nextEntry;
} else {
LinkedHashEntry *next = entry->getNext();
delete entry;
prevEntry->setNext(next);
}
}
}
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; i++)
if (table[i] != NULL) {
LinkedHashEntry *prevEntry = NULL;
LinkedHashEntry *entry = table[i];
while (entry != NULL) {
prevEntry = entry;
entry = entry->getNext();
delete prevEntry;
}
}
delete[] table;
}
};
다음은 http://www.algolist.net/Data_structures/Hash_table/Open_addressing의 내용을 편역한 것이다.
해시 테이블. 열린 주소 전략
해시 테이블에서 같은 값의 키들로 인해 생기는 충돌을 해결하는 방식으로 해시값의 체이닝(chaining)은 좋은 방법이다. 하지만, 그것은 연결 리스트의 구조를 저장하기 위한 추가적인 메모리를 소비한다. 만약 해시에 저장되는 값들(entries)이 작거나(예를 들어, 정수들), 혹은 아예 값이 없다면(ADT의 설정과 같은), 메모리의 허비는 데이터 자체의 크기에 비해 상당할 것이다. 해시 테이블이 열린 주소 방식의 전략에 기반을 두면, 모든 키 값 쌍들은 해시 테이블 자체에 저장되게 되고, 추가적인 자료 구조가 필요 없어진다.
충돌 해결
삽입 연산을 고려해보자. 한 슬롯에서는 키와 값이 저장되는데, 알고리즘이 비어있는 버킷을 찾기 시작하면서 키가 해싱되어져 저장되는 슬롯이 바빠지게 된다. 알고리즘은 해시가 되어진 슬롯에서 시작해서 비어있는 버킷을 찾을 때까지 프로브 순서(probe sequence)대로 진행해 간다. 이미 여럿의 잘 알려진 프로브 순서들이 존재한다:
- 선형 검색(linear probing): 프로브 사이의 거리가 상수이다.(가령, 1일 때 프로브는 연결된 슬롯을 하나씩 검사한다.
- 이차 프로빙(quadratic probing): 각 단계마다 특정 상수 값만큼 프로브 사이의 거리가 증가한다.(이 경우에 첫번째 슬롯까지의 거리는 단계 번호에 2차항적으로 계산된다.)
- 더블 해싱(double hashing): 프로브들 사이의 거리는 다른 해시 함수를 이용해서 계산된다.
열린 주소 전략은 해시 함수가 추가적인 특성을 가지도록 요구한다. 해시 함수는 균일 분포를 생성해야할 뿐만 아니라, 해시 값들의 클러스터링을 피해야 한다. 여기에서 클러스터링은 프로브 순서에서 해시 값이 순차적인 것을 말한다.
선형 프로빙
삭제 연산
열린 주소를 가진 해시 테이블에서 키를 제거하는 것은 여러 의미를 가진다. 다음 상황을 고려해보자.
만약 알고리즘이 단순히 "Sandra Miller" 버킷을 제거하면, 테이블 자료 구조는 망가질 것이다. 알고리즘은 "Andrew Wilson" 키를 성공적으로 찾을 수 없게 된다. 사실, "Andrew Wilson" 키는 "빨간 슬롯"에 해시가 되었다. 이 빨간 슬롯은 다른 키를 가지고 있고, 선형 검색 알고리즘은 "Andrew Wilson"을 다음의 버킷에서 찾으려고 하겠지만, 그것은 해당 버킷이 제거된 후에는 다음의 그림처럼 비어있다.
해결책은 다음과 같다. 키를 단순히 삭제하는 대신, 알고리즘은 특별한 "삭제됨"의 값을 슬롯에 적는 것이다.
이제 검색 알고리즘은 올바르게 작동할 것이다. 삽입 알고리즘은 가능할 때, 삭제된 슬롯을 재활용 해야 한다.
주의. 이 알고리즘은 문제를 해결하지만, 이 "삭제된" 값들을 통과해서 진행하는데 시간이 더 걸리게 되고, 이는 성능에 나쁜 영향을 미친다. 만약 해시 테이블이 값들의 삭제를 허용해야 한다면, 체이닝이 충돌을 해결하기 위해 더 좋은 방식이다.
복잡도 분석
열린 주소에 기반을 둔 해시테이블은, 해시 함수의 올바른 선택에 더욱 민감하다. 해시 함수가 좋고, 해시 테이블이 잘 형성되었다고 가정하면, 대략적으로 삽입, 삭제, 검색의 연산은 상수에 가깝다.
열린 주소에 기븐을 둔 해시 테이블의 성능은 테이블의 로드 팩터에 매우 민감하다. 만약 로드 팩터가 0.7 경계값을 넘어서면, 테이블의 속도가 급격하게 감소한다. 사실, 프로브 순서의 길이는
에 비례한다. 최악의 경우, 즉, 로드 팩터가 1에 가까워질 때, 프로브 순서의 길이는 무한에 가까워진다. 실제에서 그것이 의미하는 바는, 테이블에 더 이상의 빈 슬롯이 없고 알고리즘은 새로운 요소를 삽입할 장소를 결코 찾지 못할 것이라는 뜻이다. 그러므로, 이 형태의 해시 테이블은 효율적이기 위해서는 동적 크기 조절을 지원해야 한다.
열린 주소 대 체이닝
|
체이닝 |
열린 주소 |
충돌 해결 |
외부 자료 구조 이용 | 해시 테이블 자체를 이용 |
메모리 소비 | 엔트리당 포인터 크기의 오버해드(테이블에 리스트 헤드를 저장) | 오버헤드 없음 |
테이블의 로드 팩터에의 성능 의존도 | 직접적으로 비례 | 위의 수식에 비례 |
해시 테이블 크기 보다 더 많은 아이템 저장을 허용 | 그렇다 | 그렇지 않다. 게다가, 테이블의 로드 팩터를 0.7 이하로 유지하는 것이 추천됨 |
해시 함수 요구 사항 | 해시 값의 균등 분포 |
해시 값의 균등 분포, 클러스터링 회피 |
삭제 처리 |
처리 가능 |
"삭제된" 값들에 의해 해시 테이블이 막힘 |
구현 |
단순 | 정확한 열린 주소 기반 해시 테이블은 복잡함 |
체이닝을 이용한 해시 테이블은 로드 팩터 1 이상에서도 효율적으로 동작할 수 있다. 동시에, 열린 주소 방식의 테이블은 효율적이기 위해서 로드 팩터 0.7을 넘지 않아야 하며, 이 말은 30%의 슬롯이 비어있도록 하기 때문에, 명백히 메모리를 허비한다.
코드 조각
아래의 코드는 선형 검색을 구현한다. 현재 구현은 무한 루프에 들어가는 것을 방지한다.
자바 구현
public class HashEntry {
private int key;
private int value;
HashEntry(int key, int value) {
this.key = key;
this.value = value;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getKey() {
return key;
}
}
public class DeletedEntry extends HashEntry {
private static DeletedEntry entry = null;
private DeletedEntry() {
super(-1, -1);
}
public static DeletedEntry getUniqueDeletedEntry() {
if (entry == null)
entry = new DeletedEntry();
return entry;
}
}
public class HashMap {
private final static int TABLE_SIZE = 128;
HashEntry[] table;
HashMap() {
table = new HashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int get(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry() ||table[hash] != null && table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (table[hash] == null || hash == initialHash)
return -1;
else
return table[hash].getValue();
}
public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
int indexOfDeletedEntry = -1;
while (hash != initialHash && (table[hash] == DeletedEntry.getUniqueDeletedEntry() ||table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
if (table[hash] == DeletedEntry.getUniqueDeletedEntry())
indexOfDeletedEntry = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if ((table[hash] == null || hash == initialHash)
&& indexOfDeletedEntry != -1)
table[indexOfDeletedEntry] = new HashEntry(key, value);
else if (initialHash != hash)
if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
&& table[hash] != null && table[hash].getKey() == key)
table[hash].setValue(value);
else
table[hash] = new HashEntry(key, value);
}
public void remove(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry() ||table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (hash != initialHash && table[hash] != null)
table[hash] = DeletedEntry.getUniqueDeletedEntry();
}
}
C++ 구현
class HashEntry {
private:
int key;
int value;
public:
HashEntry(int key, int value) {
this->key = key;
this->value = value;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
void setValue(int value) {
this->value = value;
}
};
class DeletedEntry: public HashEntry {
private:
static DeletedEntry *entry;
DeletedEntry() :
HashEntry(-1, -1) {
}
public:
static DeletedEntry *getUniqueDeletedEntry() {
if (entry == NULL)
entry = new DeletedEntry();
return entry;
}
};
DeletedEntry *DeletedEntry::entry = NULL;
const int TABLE_SIZE = 128;
class HashMap {
private:
HashEntry **table;
public:
HashMap() {
table = new HashEntry*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
}
int get(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash && (table[hash]
== DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
&& table[hash]->getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (table[hash] == NULL || hash == initialHash)
return -1;
else
return table[hash]->getValue();
}
void put(int key, int value) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
int indexOfDeletedEntry = -1;
while (hash != initialHash && (table[hash]
== DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
&& table[hash]->getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
if (table[hash] == DeletedEntry::getUniqueDeletedEntry())
indexOfDeletedEntry = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if ((table[hash] == NULL || hash == initialHash) && indexOfDeletedEntry
!= -1)
table[indexOfDeletedEntry] = new HashEntry(key, value);
else if (initialHash != hash)
if (table[hash] != DeletedEntry::getUniqueDeletedEntry()
&& table[hash] != NULL && table[hash]->getKey() == key)
table[hash]->setValue(value);
else
table[hash] = new HashEntry(key, value);
}
void remove(int key) {
int hash = (key % TABLE_SIZE);
int initialHash = -1;
while (hash != initialHash && (table[hash]
== DeletedEntry::getUniqueDeletedEntry() || table[hash] != NULL
&& table[hash]->getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % TABLE_SIZE;
}
if (hash != initialHash && table[hash] != NULL) {
delete table[hash];
table[hash] = DeletedEntry::getUniqueDeletedEntry();
}
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; i++)
if (table[i] != NULL && table[i]
!= DeletedEntry::getUniqueDeletedEntry())
delete table[i];
delete[] table;
}
};
다음은 http://www.algolist.net/Data_structures/Hash_table/Dynamic_resizing의 내용을 편역한 것이다.
해시 테이블. 동적 크기 조절
해시 테이블의 로드 팩터의 증가와 함께, 충돌의 횟수가 증가하고, 이는 전반적인 테이블의 성능을 하락 시킨다. 체이닝 방식을 가진 해시 테이블에서 이것은 가능한 이야기이지만, 열린 주소 방식의 해시 테이블에 대해서는 근본적인 성능 하락 때문에 허용되지 않는다. 해결책은 주어진 경계 값을 로드 팩터가 넘었을 때, 테이브의 크기를 재조정하는 것이다.
마찬가지로, 테이블의 값이 드문 드문 해졌을 때, 공간을 절약하기 위해서 배열을 압축하는 것이 효율적이다.
크기 조절 알고리즘
해시 값이 테이블의 크기에 의존한다는 것을 기억하자. 그렇기 때문에, 해시 요소들은 크기가 조절될 때 변경되며 알고리즘은 단순히 이전 저장소에서 새 저장소로 데이터를 복사할 수 만은 없다. 일반적인 해시 함수에서 오로지 해야하는 일은 과거 해시테이블을 순회하면서 새로운 테이블에 각 요소들을 추가하는 것이다. (역주: 암시적으로 해시 함수를 다시 호출해야 한다.)
복잡도 분석
동적 크기 조절은 해시 함수의 상수 근접 복잡도에 영향을 미치지는 않는다. 하지만, 크기 조절은 한 번 일어날 때, 크기 조절에 의해 시작되는 연산들은 완료되기 위해서 O(n) 시간이 걸린다. 여기에서 n은 테이블에 있는 값들의 수이다. 이 사실이 동적 크기 변화가 가능한 해시 테이블이 실시간 응용에 부적합하게 만들 것이다.
코드 조각들
위에 언급했듯이, 테이블은 두 가지 경우에 크기 조절이 필요하다: 너무 빡빡하게 값들이 차 있거나(로드 팩터가 > 경계 최대값인 경우), 너무 드문 드문 차있을 경우이다(로드 팩터 < 경계 최저값인 경우). 우리는 단순함을 유지하기 위해서 첫 번째 경우만 고려한다. 자바 구현은 열린 주소 기반의 해싱으로 구현되었고, C++은 체이닝을 이용한 해시 테이블로 구현되었다. 옅은 노랑색으로 표시된 코드 문잗열들은 크기 조절에 이용되는 부분들을 나타낸다.
자바 구현
public class HashMap {
private final int DEFAULT_TABLE_SIZE = 128;
private float threshold = 0.75f;
private int maxSize = 96;
private int size = 0;
HashEntry[] table;
HashMap() {
table = new HashEntry[DEFAULT_TABLE_SIZE];
for (int i = 0; i < DEFAULT_TABLE_SIZE; i++)
table[i] = null;
}
void setThreshold(float threshold) {
this.threshold = threshold;
maxSize = (int) (table.length * threshold);
}
public int get(int key) {
int hash = (key % table.length);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry()
|| table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % table.length;
}
if (table[hash] == null || hash == initialHash)
return -1;
else
return table[hash].getValue();
}
public void put(int key, int value) {
int hash = (key % table.length);
int initialHash = -1;
int indexOfDeletedEntry = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry()
|| table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
if (table[hash] == DeletedEntry.getUniqueDeletedEntry())
indexOfDeletedEntry = hash;
hash = (hash + 1) % table.length;
}
if ((table[hash] == null || hash == initialHash)
&& indexOfDeletedEntry != -1) {
table[indexOfDeletedEntry] = new HashEntry(key, value);
size++;
} else if (initialHash != hash)
if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
&& table[hash] != null && table[hash].getKey() == key)
table[hash].setValue(value);
else {
table[hash] = new HashEntry(key, value);
size++;
}
if (size >= maxSize)
resize();
}
private void resize() {
int tableSize = 2 * table.length;
maxSize = (int) (tableSize * threshold);
HashEntry[] oldTable = table;
table = new HashEntry[tableSize];
size = 0;
for (int i = 0; i < oldTable.length; i++)
if (oldTable[i] != null
&& oldTable[i] != DeletedEntry.getUniqueDeletedEntry())
put(oldTable[i].getKey(), oldTable[i].getValue());
}
public void remove(int key) {
int hash = (key % table.length);
int initialHash = -1;
while (hash != initialHash
&& (table[hash] == DeletedEntry.getUniqueDeletedEntry()
|| table[hash] != null
&& table[hash].getKey() != key)) {
if (initialHash == -1)
initialHash = hash;
hash = (hash + 1) % table.length;
}
if (hash != initialHash && table[hash] != null) {
table[hash] = DeletedEntry.getUniqueDeletedEntry();
size--;
}
}
}
C++ 구현
const int DEFAULT_TABLE_SIZE = 128;
class HashMap {
private:
float threshold;
int maxSize;
int tableSize;
int size;
LinkedHashEntry **table;
void resize() {
int oldTableSize = tableSize;
tableSize *= 2;
maxSize = (int) (tableSize * threshold);
LinkedHashEntry **oldTable = table;
table = new LinkedHashEntry*[tableSize];
for (int i = 0; i < tableSize; i++)
table[i] = NULL;
size = 0;
for (int hash = 0; hash < oldTableSize; hash++)
if (oldTable[hash] != NULL) {
LinkedHashEntry *oldEntry;
LinkedHashEntry *entry = oldTable[hash];
while (entry != NULL) {
put(entry->getKey(), entry->getValue());
oldEntry = entry;
entry = entry->getNext();
delete oldEntry;
}
}
delete[] oldTable;
}
public:
HashMap() {
threshold = 0.75f;
maxSize = 96;
tableSize = DEFAULT_TABLE_SIZE;
size = 0;
table = new LinkedHashEntry*[tableSize];
for (int i = 0; i < tableSize; i++)
table[i] = NULL;
}
void setThreshold(float threshold) {
this->threshold = threshold;
maxSize = (int) (tableSize * threshold);
}
int get(int key) {
int hash = (key % tableSize);
if (table[hash] == NULL)
return -1;
else {
LinkedHashEntry *entry = table[hash];
while (entry != NULL && entry->getKey() != key)
entry = entry->getNext();
if (entry == NULL)
return -1;
else
return entry->getValue();
}
}
void put(int key, int value) {
int hash = (key % tableSize);
if (table[hash] == NULL) {
table[hash] = new LinkedHashEntry(key, value);
size++;
} else {
LinkedHashEntry *entry = table[hash];
while (entry->getNext() != NULL)
entry = entry->getNext();
if (entry->getKey() == key)
entry->setValue(value);
else {
entry->setNext(new LinkedHashEntry(key, value));
size++;
}
}
if (size >= maxSize)
resize();
}
void remove(int key) {
int hash = (key % tableSize);
if (table[hash] != NULL) {
LinkedHashEntry *prevEntry = NULL;
LinkedHashEntry *entry = table[hash];
while (entry->getNext() != NULL && entry->getKey() != key) {
prevEntry = entry;
entry = entry->getNext();
}
if (entry->getKey() == key) {
if (prevEntry == NULL) {
LinkedHashEntry *nextEntry = entry->getNext();
delete entry;
table[hash] = nextEntry;
} else {
LinkedHashEntry *next = entry->getNext();
delete entry;
prevEntry->setNext(next);
}
size--;
}
}
}
~HashMap() {
for (int hash = 0; hash < tableSize; hash++)
if (table[hash] != NULL) {
LinkedHashEntry *prevEntry = NULL;
LinkedHashEntry *entry = table[hash];
while (entry != NULL) {
prevEntry = entry;
entry = entry->getNext();
delete prevEntry;
}
}
delete[] table;
}
};
댓글