임의의 데이터를 받아서 특정 해시값을 반환하는 함수
출처 : https://www.varonis.com/blog/the-definitive-guide-to-cryptographic-hash-functions-part-1/
Key 값을 입력 받아 해시 함수로부터 반환된 Hash Code를 배열의 Index로 환산해서 데이터에 접근하는 방식
상품(key)의 가격(value)을 저장하고 싶다!
해시테이블에 해시 함수 반환값을 Index로 잡고, 각 항목의 가격을 추가한다.
"APPLE"의 가격을 알고 싶다면
→ "APPLE"을 해시 함수에 넣으면 Index: 5를 반환하고 해당 인덱스의 값이 가격이다.
→ 시간복잡도 : O(1)
해시 함수는 서로 다른 데이터일 때, 서로 다른 해시값을 반환한다고 하였으나,
사실 정확하게 이렇게 할 수 있는 해시 함수를 만드는 것은 거의 불가능(비둘기집 원리)하다.
비둘기집 원리 : 5마리 비둘기가 있고 비둘기 집이 4개라면 아무리 균등하게 비둘기를 집에 넣더라도
최소한 한 집에는 비둘기가 2마리 이상 들어감.
→ 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우
충돌 (collsion)
충돌
을 해결하기 위해 여러 방법이 있는데 가장 간단한 방법은 같은 버킷
에 여러 개의 키를 리스트로 만든다.
극단적인 예를 들어보자.
가지고 있는 상품이 모두 "A"로 시작한다고 가정하면 아래와 같은 문제가 발생한다.
결론
해시함수를 잘못 만들면 충돌
현상이 발생한다.
충돌현상을 방지하기 위해 좋은 해시함수를 만들어야 한다.
→ 각 버킷에 고르게 분포할 수 있도록
낮은 사용률
해시 테이블에 있는 항목의 수 / 해시 테이블에 있는 공간의 수
충돌 해결은 크게 세 가지 방법이 존재한다.
Separate Chaining
Open Addressing
비어있는 해시테이블의 공간을 활용
지정한 메모리 외 추가적인 저장공간이 필요없음.
삽입, 삭제 시 오버헤드가 적다.
비어있는 해시를 찾는 규칙에 따라 아래의 방법으로 세분화됨.
Linear Probing(선형 탐색)
: 고정폭 만큼 이동하여 차례대로 빈 버킷을 검색
Quadratic Probing(제곱 탐색)
: 고정폭이 아니고 폭이 제곱수로 늘어나는 방식
Double Hasing(이중 해시)
: 다른 해시함수를 한번 더 적용해서 나온 해시를 통해 데이터를 저장.
Resizing
충돌
을 피해야 한다.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)
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
==========
3000