![[자료구조] 해시테이블(HashTable)이란?](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbe5R22%2Fbtrcb9kAfxF%2F6TNgUpIv7zcheClbnU0hRk%2Fimg.png)
해시테이블(Hash Table)이란?
: 특정 키 값이 해시 함수를 통해 반환받은 해시코드(Hash Code)로 환산되어 배열의 인덱스로 사용되며, 이를 통해 데이터 값에 접근하는 방식의 자료구조.
해시테이블(Hash Table)의 장점
- 검색 속도가 매우 빠르다 : O(1) ~ O(n)
: 해시테이블의 키 값에는 숫자, 문자열, 파일데이터 등등 제한이 거의 없다. 키 값을 해시 함수를 통해 해시 코드를 정수로 생성해내 인덱스로 활용하기 때문에 키 값이 얼마나 큰지에 관계 없이 정수의 인덱스로 환산된다. 해시코드를 인덱스로 사용하기 때문에, 바로 데이터의 위치에 다이렉트로 접근할 수 있다. 즉, 다시 말하자면 배열의 경우 배열 안에 특정 값을 찾기 위해선 배열의 0번 인덱스부터 n번 인덱스까지 선형검색(Linear Search)를 통해 하나씩 직접 비교해가면서 특정 값을 찾는다[O(n)]. 하지만 해시 테이블을 이용하면, 키 값이 해시코드로 환산되어 이 해시코드 자체를 배열의 인덱스로 사용하기 때문에 검색 자체가 필요없고, 바로 데이터의 위치에 접근할 수 있다.[O(1)]
해시테이블(Hash Table)의 문제점과 해결방법 : 해시 충돌(Collison)
- 해시 함수를 통해 나온 해시 코드가 중복되는 경우
: 위에서 말했듯이 해시테이블에서 키 값에는 숫자나 문자열뿐만 아니라 파일 데이터 등등 가짓수가 무한하다. 하지만 해시함수를 통해서 결과값으로 나온 해시 코드는 정수이다. 즉, 무한대로 들어오는 입력에 비해 해시코드는 정수개로 한정지어지므로 당연하게도 중복된 해시코드를 가질 수 밖에 없다. 같은 이유로 해시 테이블의 배열의 갯수가 한정되어 있기 때문에 해시코드를 배열 크기 만큼 나머지 연산(%)을 통해 인덱스로 환산 할 경우에도 중복되는 경우가 발생한다. 해결 방법은 해당 배열방에 배열 또는 리스트를 삽입하여 여러개의 값을 저장하는 것이다. 이런 경우엔 특정 키의 값을 찾기 위해선 해시코드를 통해 데이터의 위치에 접근해 선형검색을 하여 해당 키의 값을 찾는다.
- 하나의 인덱스에 모든 키값이 저장되어 시간복잡도가 늘어나는 경우[O(n)]
: 키 값이 해시함수를 통해서 산출된 해시코드 or 인덱스 값이 하나 또는 소수인 경우를 말한다. 해당하는 배열방에 여러 개의 값을 저장하기 위해서 배열 또는 리스트를 추가해 문제점을 해결했지만, 만약 해시 함수를 통해 환산된 해시 코드가 하나 또는 소수일 경우엔 원하는 값을 찾기 위해선 해시코드가 가르키는 배열방에서 한번 더 선형 검색을 통해 하나씩 비교를 해야한다. 최악에 경우엔 일반 배열과 시간 복잡도가 같아질 수 있다. 이러한 문제점은 해시코드를 고르게 분배할 수 있도록 해시 알고리즘을 짜는 것이다. 하지만, 대부분 프로그래밍 언어에 이미 내장되어 있기 때문에, 직접 건드는 일은 거의 없다. 즉, 최악의 경우 O(n)의 시간복잡도를 갖을 수 있다는 것과 고르게 분배할 수 있는 알고리즘이 해시 테이블에서 매우 중요한 이슈라는 것을 기억하자.
해시테이블(Hash Table)의 간단 구현[JAVA]
class Node{
String key;
String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
}
위의 예시와는 다른 구현이다. 먼저 키(key)와 값(value)를 가진 Node 클래스로 링크드리스트를 만든다.
import java.util.LinkedList;
public class HashTable{
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 convertToIndex(int hashcode){
return hashcode % data.length;
}
void put(String key, String value){
int hashcode = getHashCode(key);
int index = converToIndex(hashcode);
LinkedList<Node> list = data[index];
if(data[node] == null){
data[node] = new LinkedList();
}
data[node].addLast(new Node(key, value));
}
void get(String key){
int hashcode = getHashcode(key);
int index = convertToIndex(hashcode);
LinkedList<Node> list = data[index];
for(Node n: list){
if(n.getKey().equals(key)){
return n.getValue();
}
}
}
}
값을 저장하는 put 함수와 값을 불러오는 get 함수의 진행 과정을 설명하자면, 우선 put() 함수는 key를 getHashCode() 함수를 통해 해시 코드로 환산한다. 해시코드를 링크드리스트의 크기만큼의 나머지 연산을 통해 해시코드를 배열 인덱스 범위 내로 환산해준다. 기존 배열방에 있는 데이터를 가져와 배열이 없는 경우엔 새로 생성하고, 해당 데이터 값을 연결해준다. get() 함수의 경우 key를 getHashCode() 함수를 통해 해시 코드로 환산한다. 해시코드를 링크드리스트의 크기만큼의 나머지 연산을 통해 해시코드를 배열 인덱스 범위 내로 환산해준다. 해당 인덱스에 위치한 링크드리스트를 가져와 링크드리스트안에 해당 키를 가진 노드가 있는지 확인해준다.