[자료구조/알고리즘] - 해시 테이블
해시 함수
임의의 데이터를 받아서 특정 해시값을 반환하는 함수
출처 : https://www.varonis.com/blog/the-definitive-guide-to-cryptographic-hash-functions-part-1/
해시 함수 특징
- 일관성이 있어야 한다.
- "dog"을 넣었을 때 반환되는 값은 항상 "06d80eb0..." 이어야 한다.
- 다른 데이터가 들어오면 다른 해시값이 나와야 한다.
- 어떤 데이터가 들어와도 동일한 값이 반환된다면 좋은 해시 함수가 아니다.
해시 테이블
Key 값을 입력 받아 해시 함수로부터 반환된 Hash Code를 배열의 Index로 환산해서 데이터에 접근하는 방식
특징
- 어떤 것과 다른 것 사이의 관계를 모형화 할 수 있다.
- 키(key)와 값(value)를 가진다.
- 해시 맵(hash maps), 맵(maps), 딕셔너리(dictionaries), 연관 배열(associative arrays)이라는
이름으로도 알려져 있다. - 해시 함수와 배열을 결합.
예시
-
상품(key)의 가격(value)을 저장하고 싶다!
-
해시테이블에 해시 함수 반환값을 Index로 잡고, 각 항목의 가격을 추가한다.
-
"APPLE"의 가격을 알고 싶다면
→ "APPLE"을 해시 함수에 넣으면 Index: 5를 반환하고 해당 인덱스의 값이 가격이다.
→ 시간복잡도 : O(1)
충돌
해시 함수는 서로 다른 데이터일 때, 서로 다른 해시값을 반환한다고 하였으나,
사실 정확하게 이렇게 할 수 있는 해시 함수를 만드는 것은 거의 불가능(비둘기집 원리)하다.
비둘기집 원리 : 5마리 비둘기가 있고 비둘기 집이 4개라면 아무리 균등하게 비둘기를 집에 넣더라도
최소한 한 집에는 비둘기가 2마리 이상 들어감.
→ 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우
- 첫 글자에 따라 해시값을 반환하는 해시 함수를 만들었다.
- ex) "A"로 시작하면 0, "B"로 시작하면 1, "C"로 시작하면 2 를 반환
- "APPLE"과 "BANANA"의 가격을 각각 0과 1 Index에 잘 저장했다.
- 그리고 "AVOCADO"를 넣으려고 한다. "A"로 시작해서 0 Index에 넣어야 하는데
이미 "APPLE"이 공간을 차지하고 있다!?→충돌 (collsion)
충돌을 해결하기 위해 여러 방법이 있는데 가장 간단한 방법은 같은 버킷에 여러 개의 키를 리스트로 만든다.
- "APPLE"과 "AVOCADO"가 같은 버킷에 리스트로 할당되었다.
극단적인 예를 들어보자.
가지고 있는 상품이 모두 "A"로 시작한다고 가정하면 아래와 같은 문제가 발생한다.
- 해시 테이블이 한 버킷만 빼고 모두 비어있다. 그 한 버킷에는 거대한 연결 리스트가 존재.
- 결국 해시 테이블이 느려지게 된다. → O(n)
결론
-
해시함수를 잘못 만들면
충돌현상이 발생한다. -
충돌현상을 방지하기 위해 좋은 해시함수를 만들어야 한다.
→ 각 버킷에 고르게 분포할 수 있도록
-
낮은 사용률
- 사용률(load factor) →
해시 테이블에 있는 항목의 수 / 해시 테이블에 있는 공간의 수- (항목의 수: 2 / 배열의 크기: 5) → 사용률: 0.4
- 사용률이 1보다 크다는 것은 배열 공간의 수 보다 항목의 수가 더 많다는 것
- 보통 사용률이 0.7 보다 커지면 리사이징한다.
- 사용률(load factor) →
충돌 해결
충돌 해결은 크게 세 가지 방법이 존재한다.
-
Separate Chaining
- 동일한 버킷의 데이터에 대해 추가 메모리를 사용하여 다음 데이터의 주소를 저장
- 해시테이블의 확장이 필요없고 간단하게 구현 가능
- 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져서 효율성 떨어짐.
-
Open Addressing
-
비어있는 해시테이블의 공간을 활용
-
지정한 메모리 외 추가적인 저장공간이 필요없음.
-
삽입, 삭제 시 오버헤드가 적다.
-
비어있는 해시를 찾는 규칙에 따라 아래의 방법으로 세분화됨.
-
Linear Probing(선형 탐색): 고정폭 만큼 이동하여 차례대로 빈 버킷을 검색
- 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustering(특정 영역에 원소가 몰리는 현상) 문제에 취약
- 52~56 해시값에 데이터가 모두 저장되어 있기 때문에 삽입하려는 임의의 키 최초 해시값이 52와 같다면 탐색을 적어도 5번 해야한다.
-
Quadratic Probing(제곱 탐색): 고정폭이 아니고 폭이 제곱수로 늘어나는 방식
- 처음 충돌이 발생한 경우에는 1^2만큼 그 다음 충돌이 발생하면 2^2, 3^2, ... 씩 옮긴다.
- 여러 개의 서로 다른 키들이 동일한 초기 해시값(Initial Probe)을 갖는 문
secondary clustering에 여전히 취약. - 초기 해시값이 같으면 다음 탐색 위치 또한 동일하게 때문이다.
- 초기 해시값이 7인 데이터를 넣으려면 선형 탐색 기법보다 더 큰 폭으로
이동을 한다해도 탐색을 4번이나 수행해야 함.
- 초기 해시값이 7인 데이터를 넣으려면 선형 탐색 기법보다 더 큰 폭으로
-
Double Hasing(이중 해시): 다른 해시함수를 한번 더 적용해서 나온 해시를 통해 데이터를 저장.- 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이
일어났을 때 탐색 이동폭을 얻기 위해 사용. - 최초 해시값이 같더라도 탐색 이동폭이 달라지고, 탐색 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화
- 위의 두 방법들 보다 연산 수행이 더 많음.
- 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이
-
-
-
Resizing
- 위의 두 방법으로도 효율성이 좋아지지 않으면, 버킷의 개수를 확장해야 한다.
- 더 큰 버킷을 가지는 배열을 새로 생성 후, 새로운 배열에 기존 데이터의 해시값을 다시 계산해서
복사(재배치)한다.
해시 테이블 vs 배열 vs 연결리스트
- 평균적인 경우, 해시 테이블의 탐색, 삽입, 삭제는 배열과 연결리스트 장점을 모두 갖춘만큼 빠르다.
- 최악의 경우에는 해시 테이블이 가장 느림.
- 해시 테이블에서 최악의 상황을 발생하지 않게 하려면
충돌을 피해야 한다.
해시 테이블 구현 - Java 코드
Separate Chaining
public class ChainHash {
/** 해시를 구성하는 노드*/
class Node {
private String key;
private int value;
private Node next;
public Node(String key, int value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
String getKey() {
return key;
}
int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
}
private int size; // 해시 테이블 사이즈
private Node[] table; // 해시 테이블
public ChainHash(int size) {
table = new Node[size];
this.size = size;
}
/** 해시 값 구하기 */
public int hashValue(String key) {
int hashcode = 0;
for (char c : key.toCharArray()) {
hashcode += c;
}
return hashcode % size;
}
/** key를 이용하여 value 검색*/
public int search(String key) {
int hash = hashValue(key);
Node p = table[hash];
while (p != null) {
if (p.getKey().equals(key))
return p.getValue();
p = p.next;
}
return -1;
}
/** 요소 추가 */
public void add(String key, int value) {
int hash = hashValue(key);
Node p = table[hash];
while (p != null) {
if (p.getKey().equals(key)) {
p.setValue(value);
return;
}
p = p.next;
}
Node tmp = new Node(key, value, table[hash]);
table[hash] = tmp;
}
/** 요소 삭제 */
public void remove(String key) {
int hash = hashValue(key);
Node p = table[hash];
Node pp = null; // 바로 앞 노드
while (p != null) {
if (p.getKey().equals(key)) {
if (pp == null)
table[hash] = p.next;
else
pp.next = p.next;
return;
}
pp = p;
p = p.next;
}
}
/** 전체 해시 테이블 출력 */
public void dump() {
for (int i = 0; i < size; i++) {
Node p = table[i];
System.out.printf("%02d ", i);
while (p != null) {
System.out.printf("-> %s (%s) ", p.getKey(), p.getValue());
p = p.next;
}
System.out.println();
}
}
public static void main(String[] args) {
ChainHash ch = new ChainHash(7);
ch.add("APPLE", 1500);
ch.add("AVOCADO", 2000);
ch.add("ALMOND", 800);
ch.add("BANANA", 1000);
ch.add("MANGO", 3000);
ch.add("KIWI", 900);
ch.add("POTATO", 2000);
ch.add("TOMATO", 1300);
ch.add("CUCUMBER", 1100);
ch.add("MELON", 3500);
ch.add("CHERRY", 2000);
ch.add("PLUM", 1700);
ch.add("PEAR", 1500);
ch.add("GARLIC", 500);
ch.dump();
ch.remove("POTATO");
ch.add("MANGO", 5000);
System.out.println("======");
ch.dump();
}
}결과
00 -> GARLIC (500) -> KIWI (900)
01 -> MELON (3500)
02 -> PEAR (1500) -> POTATO (2000) -> ALMOND (800)
03 -> PLUM (1700) -> CUCUMBER (1100)
04 -> BANANA (1000)
05 -> AVOCADO (2000)
06 -> CHERRY (2000) -> TOMATO (1300) -> MANGO (3000) -> APPLE (1500)
======
00 -> GARLIC (500) -> KIWI (900)
01 -> MELON (3500)
02 -> PEAR (1500) -> ALMOND (800)
03 -> PLUM (1700) -> CUCUMBER (1100)
04 -> BANANA (1000)
05 -> AVOCADO (2000)
06 -> CHERRY (2000) -> TOMATO (1300) -> MANGO (5000) -> APPLE (1500)Open Addressing - Linear Probing
public class OpenHash {
/** 버킷 상태 */
enum Status {
OCCUPIED, EMPTY, DELETED
}
/** 버킷 */
class Bucket {
private String key;
private int value;
private Status stat;
public Bucket() {
stat = Status.EMPTY;
}
void set(String key, int value, Status stat) {
this.key = key;
this.value = value;
this.stat = stat;
}
void setStat(Status stat) {
this.stat = stat;
}
String getKey() {
return key;
}
public void setValue(int value) {
this.value = value;
}
int getValue() {
return value;
}
}
private int size; // 해시 테이블 사이즈
private Bucket[] table; // 해시 테이블
public OpenHash(int size) {
table = new Bucket[size];
for (int i = 0; i < size; i++)
table[i] = new Bucket();
this.size = size;
}
/** 해시 값 구하기 */
public int hashValue(String key) {
int hashcode = 0;
for (char c : key.toCharArray()) {
hashcode += c;
}
return hashcode % size;
}
/** 재해시 값 구하기 */
public int rehashValue(int hash) {
return (hash + 1) % size;
}
/** key를 이용하여 Bucket 검색 */
private Bucket searchBucket(String key) {
int hash = hashValue(key);
Bucket p = table[hash];
for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
if (p.stat == Status.OCCUPIED && p.getKey().equals(key))
return p;
hash = rehashValue(hash); // 재해시
p = table[hash];
}
return null;
}
/** key를 이용하여 value 검색*/
public int search(String key) {
Bucket p = searchBucket(key);
if (p != null)
return p.getValue();
return -1;
}
/** 요소 추가 */
public Bucket add(String key, int value){
Bucket s = searchBucket(key);
if (s != null) {
s.setValue(value);
return s;
}
int hash = hashValue(key);
Bucket p = table[hash];
for (int i = 0; i < size; i++) {
**if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {**
p.set(key, value, Status.OCCUPIED);
return p;
}
**hash = rehashValue(hash);
p = table[hash];**
}
return null;
}
/** 요소 삭제 */
public Bucket **remove**(String key) {
Bucket p = searchBucket(key);
if (p == null)
return null;
**p.setStat(Status.DELETED);**
return p;
}
/** 전체 해시 테이블 출력 */
public void dump() {
for (int i = 0; i < size; i++) {
System.out.printf("%02d ", i);
switch (table[i].stat) {
case OCCUPIED -> System.out.printf("%s (%s) - init hash: %s \n",
table[i].getKey(), table[i].getValue(), hashValue(table[i].getKey()));
case EMPTY -> System.out.println("-- EMPTY --");
case DELETED -> System.out.println("-- DELETED --");
}
}
}
public static void main(String[] args) {
OpenHash oh = new OpenHash(15);
oh.add("APPLE", 1500);
oh.add("AVOCADO", 2000);
oh.add("ALMOND", 800);
oh.add("BANANA", 1000);
oh.add("MANGO", 3000);
oh.add("KIWI", 900);
oh.add("POTATO", 2000);
oh.add("TOMATO", 1300);
oh.add("CUCUMBER", 1100);
oh.add("MELON", 3500);
oh.add("CHERRY", 2000);
oh.add("PLUM", 1700);
oh.add("PEAR", 1500);
oh.add("GARLIC", 500);
oh.dump();
System.out.println("==========");
oh.remove("APPLE");
oh.dump();
System.out.println("==========");
System.out.println(oh.search("MANGO"));
}
}결과
00 CHERRY (2000) - init hash: 11
01 PEAR (1500) - init hash: 11
02 GARLIC (500) - init hash: 14
03 TOMATO (1300) - init hash: 3
04 MELON (3500) - init hash: 4
05 PLUM (1700) - init hash: 3
06 POTATO (2000) - init hash: 6
07 -- EMPTY --
08 ALMOND (800) - init hash: 8
09 KIWI (900) - init hash: 8
10 APPLE (1500) - init hash: 10
11 MANGO (3000) - init hash: 10
12 BANANA (1000) - init hash: 12
13 CUCUMBER (1100) - init hash: 13
14 AVOCADO (2000) - init hash: 14
==========
00 CHERRY (2000) - init hash: 11
01 PEAR (1500) - init hash: 11
02 GARLIC (500) - init hash: 14
03 TOMATO (1300) - init hash: 3
04 MELON (3500) - init hash: 4
05 PLUM (1700) - init hash: 3
06 POTATO (2000) - init hash: 6
07 -- EMPTY --
08 ALMOND (800) - init hash: 8
09 KIWI (900) - init hash: 8
10 -- DELETED --
11 MANGO (3000) - init hash: 10
12 BANANA (1000) - init hash: 12
13 CUCUMBER (1100) - init hash: 13
14 AVOCADO (2000) - init hash: 14
==========
3000References
- 출처가 없는 이미지는 직접 그림
- 아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 한빛미디어(2018)
- 보요 시바타, 『자료구조와 함께 배우는 알고리즘 입문』, 이지스퍼블리싱(2018)
- https://stackoverflow.com/questions/27742285/what-is-primary-and-secondary-clustering-in-hash/36526945
- https://ratsgo.github.io/data structure&algorithm/2017/10/25/hash/
- https://bcho.tistory.com/1072
- https://mangkyu.tistory.com/102
- https://www.youtube.com/watch?v=Vi0hauJemxA
- https://www.youtube.com/watch?v=xls6jEZNA7Y
얍얍 개발 펀치