[HashTable(해쉬테이블) 이란?]
해쉬 테이블은 (key,value)로 데이터를 저장하는 자료구조
빠르게 데이터를 검색할 수 있는 자료구조다
해시 테이블은 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고 이 인덱스를 활용해 값을 저장하거나 검색한다.
여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다
해싱 구조로 데이터를 저장하면 key값으로 데이터를 찾을 때 해시함수를 1번만 수행하면 되므로
빠르데 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다
[ Hash 함수(해시 함수) ]
해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 해시 테이블에 사용되는 대표적인 해시 함수로는 아래의 3가지가 있다.
Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.
[ 해시테이블(HashTable) 시간복잡도 ]
각각의 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다. 하지만 데이터의 충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야 하므로 O(N)까지 시간복잡도가 증가할 수 있다.
충돌을 방지하는 방법들은 데이터의 규칙성(클러스터링)을 방지하기 위한 방식이지만 공간을 많이 사용한다는 치명적인 단점이 있다.
만약 테이블이 꽉 차있는 경우라면 테이블을 확장해주어야 하는데, 이는 매우 심각한 성능의 저하를 불러오기 때문에 가급적이면 확정을 하지 않도록 테이블을 설계해주어야 한다.
(통계적으로 해시 테이블의 공간 사용률이 70% ~ 80%정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.)
또한 해시 테이블에서 자주 사용하게 되는 데이터를 Cache에 적용하면 효율을 높일 수 있다. 자주 hit하게 되는 데이터를 캐시에서 바로 찾음으로써 해시 테이블의 성능을 향상시킬 수 있다.
병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블(HashTable)을 사용해야 하며, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵(HashMap)을 사용하면 된다.
출처 : 망나니개발자
해쉬의 장단점
- 장점
데이터 저장/읽기 속도가 빠르다(검색속도가 빠르다)
해쉬는 키에 대한 데이터 값이 있는지 확인이 쉬움 - 단점
일반적으로 저장공간을 많이 차지한다 (충돌을 피하기 위해 저장공간을 충분하게 세팅)
키의 해당주소가 동일한 경우 충돌을 해결하기 위한 자료구조가 필요하다.
(오버라이딩 될 수 있기 때문)
위 단점의 해결방안중 하나가 바로 체이닝(chaning)으로 Linked List를 활용하여 해시 충돌시 연결리스트로 데이터를 이어놓는 방식이 있다.
해쉬의 주요 용도
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번하게 일어나는 경우
- 캐쉬 구현할시 (중복 확인이 쉽기 때문)
(프론트에서 메모이제이션으로 성능리팩토링을 하게 될때 사용되는 캐시가 바로 해쉬)
캐쉬는 해쉬를 사용해 데이터가 있는지 없는지 빠르게 확인할 수 있게 된다
출처
class HashTable {
class Node { // 해시테이블에 저장할 데이터를 노드에 담는다
String key; // 검색
String value; // 검색 결과
public Node(String key, String value) {
this.key = key;
this.value = value; // key,value를 받아서 객체에 할당
}
String value() {
return value;
}
void value(String value) {
this.value = value;
} // value를 가져오는 get,set
}
LinkedList<Node>[] data; // 데이터를 저장할 링크드리스트를 배열로 선언
HashTable(int size) {
this.data = new LinkedList[size]; // 크기를 정해서 배열 방으로 만들었다
}
int getHashCode(String key) {
int hashcode = 0;
for (char c : key.toCharArray()) {
hashcode += c; // 아스키값을 가져와서 해시코드에 더해준
}
return hashcode; // 해시코드 반환
}
int covertToIndex(int hashcode) { // 배열에 인덱스로 정의
return hashcode % data.length; // 해시코드를 배열방의 크기로 나눈 나머지가 배열방의 인덱스가 된다
}
Node searchKey(LinkedList<Node> list, String key) {
// 노드가 여러개 존재하는 경우 key를 가지고 해당 노드 찾아노는 함수
if (list == null) return null;
for (Node node : list) {
if (node.key.equals(key)) {
return node; // 같으면 노드 반환
}
}
return null;
}
void put(String key, String value) {
int hashcode = getHashCode(key); // key를 가지고 해시코드를 받아옴
int index = covertToIndex(hashcode); // 받아온 해시코드로 저장할 배열방 번호를 받아옴
LinkedList<Node> list = data[index]; // 배열 방 번호를 이용해서 기존 배열 방에 있는 데이터를 가져옴
if (list == null) {
list = new LinkedList<Node>(); // null이면 배열방 생성
// 해당 리스트를 배열방에 넣어줌
data[index] = list;
}
// 배열방에 기존 해당키로 데이터를 가지고 있는지 노드를 받아옴
Node node = searchKey(list, key);
if (node == null) {
// 데이터가 없다는 뜻이기 때문에 노드객체 생성
list.addLast(new Node(key, value));
} else {
node.value(value); // 해당 노드 대체. 중복키 처리
}
}
String get(String key) {
int hashcode = getHashCode(key);
int index = covertToIndex(hashcode); // 받아온 해시코드로 인덱스를 받아옴
LinkedList<Node> list = data[index];
Node node = searchKey(list, key);
return node == null ? "Not found" : node.value();
}
}
public class Test{
public static void main(String[] args){
HashTable h = new HashTable(3);
h.put("sung","She is pretty");
h.put("jin","She is Good");
h.put("hee","She is cute");
h.put("min","She is model");
System.out.println(h.get("sung"));
System.out.println(h.get("jin"));
System.out.println(h.get("hee"));
System.out.println(h.get("min"));
}
}