해시 테이블(Hash Table)

@키(key), 값(Value)을 대응시켜 저장하는 데이터 구조

- 키를 통해 해당 데이터에 빠르게 접근 가능

@해싱 

- 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정

해시 테이블 구조

키: 해시 테이블 접근을 위한 입력 값

해시 함수 : 키를 해시 값으로 매핑하는 연산

해시 값: 해시 테이블의 인덱스

해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조

해시 충돌

해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 

-서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우

해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음

 

 

---

해시 충돌 해결 방법 (1)

개방 주소법(Open Address)

- 충돌 시 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장

- hash와 value가 1:1 관계 유지

- 비어 있는 공간 탐색 방법에 따라 분류

            -  선형 탐사법, 제곱 탐사법, 이중 해싱

선형 탐사법
1. Linear probing
2. 빈 공간을 순차적으로 탐사하는 방법
-충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사 
3. 일차 군집화 문제 발생
- 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생 

key값이 들어갈 빈공간을 찾을 때까지 반복문 구성

제곱 탐사법 
1. Quadratic Probing
2. 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
- 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
2. 일차 군집화 문제 일부 보완
3. 이차 군집화 문제 발생

충돌이 났을 때마다 2의 n승만큼 이동하면서 값을 대입

개방 주소법 - 이중 해싱

1. Double Hashing

2. 해싱 함수를 이중으로 사용

- 해시 함수 1 : 최초 해시를 구할 때 사용 

- 해시 함수 2 : 충돌 발생 시 탐사 이동 간격을 구할 때 사용

3. 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨

 

값 설정

newidx 값이 만족하지 않을 경우 1씩 증가

---

해시 충돌 해결 방법 (2)

분리 연결 법(Separate Chaining)

- 해시 테이블을 연결 리스트로 구성 

- 충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를 연결

---

 

//해시 함수 기본 해시테이블 사용 방법
Hashtable<String,Integer> ht = new Hashtable();
ht. put("key1", 10);
ht. put("key2", 20);
ht. put("key3", 30);

for (Map.Entry<String,Integer> item : ht.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue()); //순서는 상관없이 key값이 잘 들어가 있는지 확인해보기

결과 

key3 - 30
key2 - 20
key1 - 10

---

전체

public class Main {
//해시 함수
public static int getHash(int key) {
return key % 5; //키값을 5로 나눈 나머지값 구하기
}

public static void main(String[] args) {
//해시 함수 기본 해시테이블 사용 방법
Hashtable<String,Integer> ht = new Hashtable();
ht. put("key1", 10);
ht. put("key2", 20);
ht. put("key3", 30);

for (Map.Entry<String,Integer> item : ht.entrySet()){
System.out.println(item.getKey() + " - " + item.getValue()); //순서는 상관없이 key값이 잘 들어가 있는지 확인
}

//해시 충돌 케이스 (해시 함수 사용)
Hashtable<Integer,Integer> ht2 = new Hashtable();
ht2.put(getHash(1),10);
ht2.put(getHash(2),20);
ht2.put(getHash(3),30);
ht2.put(getHash(4),40);
ht2.put(getHash(5),50); //key%5이기 때문에 키의 값이 0이 됨.
// key가 60이 들어갈 경우 6%5의 나머지 값은 1이니까 key는 1이 됨. (즉, 1-60이 나옴)

for(Map.Entry<Integer,Integer>item : ht2.entrySet()){
System.out.println(item.getKey() + "-"+item.getValue());
}
}
}

결과 

key3 - 30
key2 - 20
key1 - 10
4-40
3-30
2-20
1-10
0-50

---

HashTable과 HashMap의 차이

 

공통 : 둘 다 Map 인터페이스를 구현한 것 

차이 : Key에 Null 사용 여부

HashTable : X

HashMap : O

 

Tread-safe

HashTable : O //멀티스레드에서 사용 

HashMap : X //싱글스레드에서 사용 우수

참고) synchronizedMap, ConcurrentHashMap