![[선형자료구조] 해시테이블](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FqogWB%2FbtrHZC3TTTo%2FqMfdfSfEejWHWeAm8nOPwk%2Fimg.jpg)
| 요약
| 종류 | 구분 | 내용 | 언제 쓰는 게 좋을까 |
| HashTable | 특징 | - 해싱 함수를 통해 키 -> 해시로 변환한다 - key + value |
- 특정 키와 값을 연결할 때(알파벳-단어, 사전, 전화번호부) - 중복을 제거해야할 때(전체 명단 중 투표 여부 확인) |
| 장점 | - 해시 충돌이 없을 때 검색, 삽입, 삭제가 빠르다 (시간복잡도 : 평균 O(1), 최악 O(n)) - 보안성이 높다 (Key와 Hash간의 연관성X) - 데이터 캐싱에 자주 사용된다. - 중복 제거에 유리하다. |
||
| 단점 | - 해시 충돌 : key1과 key2가 해시함수를 거쳐 동일한 해시값(공간)을 가지는 상태 - 공간 복잡도가 커진다 - 순서가 있는 경우에는 맞지 않는다 - 해시 함수 의존도가 높다 |
- 해시 테이블은 키와 값을 대응시켜 저장하는 구조로, 키를 통해 빠르게 값을 찾을 수 있다는 장점을 가진다.
- 단순히 [ 키 : 값 ] 로 대응시키는 것이 아니라 "해싱"을 통해 키를 변환시킨다.
- 일상생활에서 해시 테이블은 구매내역이나 To-do 체크리스트, 그리고 영어사전에서도 볼 수 있다.
 물품 - 가격이 매칭 |
 체크박스 - 한 줄 문자열 매칭 |
 단어 - 뜻이 매칭 |
| 출처 : https://witchform.com/ | 출처 : https://www.yesform.com/ | 출처 : https://gonggam.korea.kr/ |
| 해시함수와 해시값 그리고 해시 충돌
1. 해싱이란?
키를 해시 함수(어떤 계산식)를 통해서 바꾸어 값에 접근하도록 하는 과정
- 키 : 입력값 -> 해시 함수 : 키를 해시 값으로 매핑 -> 해시 값 : 해시 테이블의 인덱스 -> 해시 테이블 : 키-값 저장하는 구조
| 키(keys) | 해시 함수(Hash Function) | 해시 값(Hash Value) | 해시 테이블(Hash Table) |
| int key1 = 0 | key % table.length(3) | 0 | 100 |
| int key2 = 10 | 1 | 200 | |
| int key3 = 20 | 2 | 300 |
2. 해시 충돌이란?
서로 다른 키에 대한 해시 값이 동일한 경우, 같은 공간에 값을 저장하게되는 충돌이 발생하는 것.
* 위의 표에 키를 하나 더 넣어서 해시 충돌을 임의로 일으켜 보자.
| 키(keys) | 해시 함수(Hash Function) | 해시 값(Hash Value) | 해시 테이블(Hash Table) |
| int key1 = 0 | key % table.length(3) | 0 | 100 |
| int key2 = 10 | 1 | 200 | |
| int key3 = 20 | 2 | 300 | |
| int key4 = 30 | 0 | 400 |
서로 다른 키 값 0과 30의 해시 값, 곧 인덱스가 0으로 동일하다. 이렇게 될 경우, 새로 들어간 400이 0자리에 덮어써진다.
| 해시 충돌을 해결하는 방법
- 해시 충돌을 해결하는 방법은 구글을 검색했을 때 정말 많이 나왔는데, 그 중에서도 대표적으로 크게 두 가지,
[1] 개방 주소법 [2] 분리연결법 를 이야기하려고 한다.
| 개방주소법(Open Address) | 비어 있는 공간을 찾아서 데이터를 저장하는 방법 - 하나씩 찾는다면? 선형 탐사법 - +n^2씩 찾는다면? 제곱 탐사법 - 해시 함수를 하다 더 쓴다면? 이중 해싱 |
||||||||||||||||||||||||||||||
| 분리연결법(Separate Chaining) | 해시 테이블을 연결 리스트로 구성하는 방식 - 배열 + 연결리스트의 느낌 - 키의 해시 값(인덱스) - 연결리스트
|
||||||||||||||||||||||||||||||
1. 개방주소법
- 해시테이블을 구현한 클래스 MyHashtable이 있다고 하자.
- 나머지는 다 생략하고 해시 함수만 놓고 보았을 때 클래스 내 코드는 아래와 같은 상태일 것이다.
- 이 상태에서 개방주소법의 여러가지 종류, 선형탐사법, 제곱탐사법, 이중해싱을 다뤄보려 한다.
class MyHashTable{
Integer table[];
// 해시 함수
public int getHash(int key) {
return key % this.table.length;
}
}
[1] 선형 탐사법 (Linear Probing)
: 충돌이 난 지점부터 +1를 하여 값이 없는 곳에 값을 넣는다.
- 코드를 보면 좀 더 이해하기 쉬울 것 같다.
- 아래 코드에서 보면 else 부문 안에 충돌 지점부터 배열의 인덱스를 하나씩 올리는 걸 볼 수 있다. 이처럼 선형탐사법은 사실상 배열의 인덱스값을 하나씩 올려주면서 배열의 빈 공간을 찾아 순회하는 걸 말한다.
class MyHashTable{
Integer table[];
// 해시 함수
public int getHash(int key) {
return key % this.table.length;
}
// 선형 탐사법 : 충돌난 지점부터 +1을 해서 비어있는 곳을 찾는다.
public void put(int key, int value) {
int idx = getHash(key);
if (this.isFull()){
System.out.println("it is full!");
return;
} else if (this.table[idx] == null){
this.table[idx] = value; // 키의 해시값(인덱스)에 값이 없으면 넣기
} else {
int newIdx = idx;
while (true) { // 충돌지점부터 +1하여 값이 없는 곳 찾기
newIdx = (newIdx + 1) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
}
this.table[newIdx] = value;
}
}
}- 단점 : 일차 군집화 문제가 발생할 수 있다.
- 일차 군집화는 뭘까?
충돌이 발생했던 지점에서 +1을 해서 비어있는 곳을 찾다보면, 충돌된 지점의 주위로 어느새 데이터들이 몰리는 현상이 발생한다. 이런 상황을 일차 군집화라고 한다.
[2] 제곱 탐사법 (Quadratic Probing)
: 충돌이 난 지점부터 n^2만큼의 간격을 두고 탐사하는 방법이다.
- 단점 : 이차 군집화 문제
- 이차 군집화란, 특정 구간에 데이터가 몰리는 현상이 이차적으로 발생한다는 의미이다. 일차 군집화와 의미는 거의 비슷한데 발생 시점이 두번째라는 게 차이라 보인다.
* 위의 코드에서 else {} 지점만 빼서 수정한다면 아래와 같다.
class MyHashTable{
/* 생략 */
// 제곱 탐사법 : 충돌이 난 지점부터 n^2로 탐사
public void put(int key, int value) {
/* 생략 */
} else {
int newIdx = idx;
int n = 1;
while (true) {
newIdx = (newIdx + (int)Math.pow(n, 2)) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
n++;
}
this.table[newIdx] = value;
}
}
}
[3] 이중 해싱 (Double Hashing)
- 말이 참 어려운데 풀이하면 해싱을 한 번 더 하겠다는 의미이다.
- 첫번째 해시함수로는 최초의 해시(인덱스)를 구하고, 충돌이나면 두번째 해시함수로 이동 간격을 잡고 빈 곳을 찾는다.
- 마찬가지로 아래 코드를 보면, 해싱을 두번 하는 코드가 나오는 걸 볼 수 있는데, 두번째의 해싱에서는 해시테이블의 크기보다 조금 작은 소수를 통해 해시값을 %해주고, 거기에 다시 *1, *2, *3..을 하는 방식으로 이중해싱을 하는 걸 볼 수 있다. 이러한 방식으로 하다보면, 선형 탐사나 제곱 탐사보다는 데이터가 골고루 분포된다.
class MyHashTable{
char p; // Hashtable의 size 보다 조금 작은 소수
/* p를 구하는 함수 생략 */
// 해시 함수1 - 최초 해싱
public int getHash(int key) {
return key % this.table.length;
}
// 해시 함수2 - 충돌 시 2차 해싱
public int getHash2(int key) {
int hash = 1 + key % this.p;
return hash % this.table.length;
}
// 이중 해싱 : 충돌이 난 지점에서 2차 해싱
public void put(int key, int value) {
/* 생략 */
} else {
int newIdx = idx;
int cnt = 1;
while (true) {
newIdx = (newIdx + getHash2(newIdx) * cnt) % this.table.length;
if (this.table[newIdx] == null) {
break;
}
cnt++;
}
this.table[newIdx] = value;
}
}
}
2. 분리 연결법
- 충돌이 발생했을 때, 동일한 버킷(Bucket - 지점)에서 연결리스트 형태로 데이터를 연결하는 방식
- 위에서도 표로 잠깐 보여주었던 것처럼 충돌지점에 데이터를 이어 붙이는 걸 볼 수 있다.
- 이번에는 구현 코드보다 자바 라이브러리로 분리 연결법을 사용할 때를 예를 들어보려고 한다.
// 분리연결법을 사용한 경우1 : 이름을 연결할때
// ex. a - amanda, avril, aeron...
Hashtable<String, LinkedList<String>> nameTable = new Hashtable();
// 분리연결법을 사용한 경우2 : (이름, 전화번호)를 담는 2차 배열을 연결할 때
// es. a - (amanda, 123-234-2342), (avril, 123-234-2213)...
Hashtable<String, LinkedList<ArrayList<String>>> phoneTable = new Hashtable();
| Java 해시맵과 해시테이블의 차이점
| HashTable | HashMap | |
| 공통점 | 두 클래스 모두 Map인터페이스를 구현했다. | |
| 차이점 | key에 null 사용하지 않음 | key에 null 사용 |
| Thread-Safe (멀티 스레드 환경에서 우수) | Thread-Safe X (싱글 스레드 환경에서 우수) | |
* 참조 : 멀티스레드용 HashMap이 별도로 있다 -- synchronizedMap, ConcurrentHashMap
++ 유용하게 쓸만한 HashMap 메소드 - putIfAbsent(), getOrDefault()
// HashMap의 getOrDefault()
int[] nums = {3, 2, 1, 1, 2, 3, 5};
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
// getOrDefault(key, defaultValue) - val가 있으면 val가져오고, 아니면 default로 세팅
map.put(num, map.getOrDefault(num, 0) + 1);
}
HashMap<Character, Node> map2 = new HashMap<>();
String word = "apple";
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
// putIfAbsent(key, val) : key가 없으면 val생성하고, 있으면 넘어간다.
map2.putIfAbsent(c, new Node());
}
| 해시 관련 문제집
https://school.programmers.co.kr/learn/courses/30/parts/12077
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[ 참고 ]
위키백과 https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
'Computer Science > Data Structure' 카테고리의 다른 글
| [비선형 자료구조] 트리와 그래프 (0) | 2022.08.03 |
|---|---|
| 비선형 자료구조 총정리 (0) | 2022.08.03 |
| [선형자료구조] 스택, 큐, 데크 (0) | 2022.07.22 |
| [선형자료구조] 연결리스트 (0) | 2022.07.22 |
| [선형자료구조] 배열과 ArrayList (0) | 2022.07.18 |