minimimi
[자료구조] 해쉬 테이블(Hash Table) with java 본문
해쉬 테이블은 key를 정수형의 code로 변환하여 해쉬 테이블에 저장하는 자료구조다. key 값의 코드화는 다양한 해쉬 함수 규칙을 통해서 이루진다. 코드화된 해쉬 코드는 해쉬 테이블의 사이즈로 나누어 해쉬 테이블에 연결 리스트(Linked List) 형태로 저장되게 된다.
해쉬 테이블에 저장된 데이터 탐색은 찾고자 하는 key 값을 code로 변환한 뒤 해쉬 테이블의 해당 index에 있는 연결 리스트를 탐색하여 이루어 진다. 따라서 해쉬를 이용할 경우 데이터 탐색에서 시간 복잡도가 O(1)까지 줄일 수 있다는 장점이 있다.
하지만 해쉬 함수가 비효율적으로 짜여진 경우 해쉬 테이블에 골고루 데이터가 연결되지 않고 하나의 index에 데이터가 몰리는 경우가 발생할 수 도 있다. 이러한 경우를 '충돌(Collision)'이라고 한다. 충돌이 발생하는 경우는 크게 2가지로 나눤다.
1. 서로 다른 key 값들이 같은 code를 가지는 경우
2. 서로 다른 code 들이 같은 index 를 가지는 경우
이러한 충돌이 발생하지 않게 해쉬 함수를 짜는 것이 해쉬 알고리즘에서 중요한 논제다.
Java로 작성한 해쉬 테이블 예제입니다.
import java.util.LinkedList;
class HashTable{
class Node{
String key;
String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
String value(){
return this.value;
}
void value(String value){
this.value = value;
}
}
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;
}
Node searchKey(LinkedList<Node> list, String 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);
int index = convertToIndex(hashcode);
LinkedList<Node> list = data[index];
if(list == null){
list = new LinkedList<Node>();
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 = convertToIndex(hashcode);
LinkedList<Node> list = data[index];
Node node = searchKey(list, key);
return node == null? "Not found" : node.value();
}
}
public class main {
public static void main(String[] args) {
HashTable h = new HashTable(3);
h.put("lee", "she is pretty");
h.put("jin", "she is a model");
h.put("kim", "he is a student");
h.put("mini", "he is cool");
System.out.println((h.get("lee")));
System.out.println((h.get("jin")));
System.out.println((h.get("kim")));
System.out.println((h.get("mini")));
}
}
먼저 해쉬 테이블을 연결 리스트로 구성하기 위해 Node를 선언해 준다.
class Node{
String key;
String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
String value(){
return this.value;
}
void value(String value){
this.value = value;
}
}
해쉬 테이블 생성자는 해쉬 테이블의 사이즈를 매개변수로 받는다.
LinkedList<Node>[] data;
HashTable(int size){
this.data = new LinkedList[size];
}
key 값을 코드화하고 index 에 할당하는 함수를 선언한다. 이 예제에서 해쉬 함수는 key 값의 각 문자의 아스키 코드를 더하여 코드화하였다.
int getHashCode(String key){
int hashcode = 0;
for(char c : key.toCharArray()){
hashcode += c;
}
return hashcode;
}
int convertToIndex(int hashcode){
return hashcode % data.length;
}
key 값을 리스트에서 탐색하는 함수를 선언한다. 연결 리스트가 null이면 null을 반환하고, 리스트에 존재하는 Node의 key 값이 탐색하고자 하는 key와 같다면 node를 반환한다. 만약 key값이 존재하지 않다면 null을 반환한다.
Node searchKey(LinkedList<Node> list, String key){
if(list == null) return null;
for(Node node : list){
if(node.key.equals(key)){
return node;
}
}
return null;
}
해쉬 테이블에 데이터를 넣는 put 함수와 해쉬 테이블에서 데이터를 반환하는 get 함수를 선언한다.
void put(String key, String value){
int hashcode = getHashCode(key);
int index = convertToIndex(hashcode);
LinkedList<Node> list = data[index];
if(list == null){
list = new LinkedList<Node>();
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 = convertToIndex(hashcode);
LinkedList<Node> list = data[index];
Node node = searchKey(list, key);
return node == null? "Not found" : node.value();
}
main함수에서 데이터를 입력하고 올바르게 탐색이 이루어지는 지 확인한다.
public class main {
public static void main(String[] args) {
HashTable h = new HashTable(3);
h.put("lee", "she is pretty");
h.put("jin", "she is a model");
h.put("kim", "he is a student");
h.put("mini", "he is cool");
System.out.println((h.get("lee")));
System.out.println((h.get("jin")));
System.out.println((h.get("kim")));
System.out.println((h.get("mini")));
}
}출력결과
