사실 자료구조 카테고리에 맞는 게시글이지만 아직 자료구조 카테고리가 없고 앞으로 딱히 만들 계획이 없기에, 그리고 구현을 자바로 했기에 자바 카테고리에 넣었다! 그냥 그런걸로 하자 ㅎㅎ
해시란?
해쉬브라운
해시란 임의의 크기를 가진 데이터를 고정된 크기의 데이터로 변화시켜 저장하는것이다. 이 과정은 해시함수를 통해 진행되며 해시값 자체를 index로 사용하기에 평균 시간복잡도가 O(1)으로 매우 빠르다
키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.
이 그럼처럼 John Smith라는 이름과 전화번호가 매핑이 되어있고 전화번호를 찾기위해선 John Smith라는 이름을 해시함수를 통해 변환한 해시코드를 통해 찾을 수 있다.
해시함수와 충돌
key를 해시함수를 통해서 해시코드로 변환시키고 이 해시코드를 인덱스로 사용하여 value를 저장하는데, 이때 충돌(Collision)이 발생할 수 있다. 다음의 예시를 보자
John Smith와 Sandra Dee라는 key가 해시함수를 통해 해시코드로 변환되었는데 우연히 같은 코드로 변환된 것이다.
즉, 무한한 값(KEY)을 유한한 값(HashCode)으로 표현하면서
서로 다른 두 개 이상의 유한한 값이 동일한 출력 값을 가지게 된다는 것이다.
key가 될 수 있는 경우는 무한하고 해시테이블은 유한하니 소위 비둘기집 원리라고 부르는 문제가 발생한다. 이런 문제로 인해 우리는 해시함수의 중요성을 느낄 수 있다. 최대한 겹치지 않고 다양한 값을 보장하는 해시 함수라면 이런 문제를 조금 개선할 수 있지만 그래도 근본적으로는 불가능하다. 따라서 우리는 다른 개선방법을 사용한다. 크게 두가지의 해결 방법이 있는데 Separate Chaining기법과 Open Addressing(개방 주소법)이 있다.
충돌 해결1. Separate Chaining(Chaining) 기법
John Smith가 들어가 있는데 그 공간에 또 Sandra Dee가 들어갈때 Collision이 발생한다. 이때 Sandra의 value를 기존 John의 뒤에 체인처럼 이어 붙혀준다. 152번지에 John과 Sandra의 정보가 함께 존재하도록 한것이다.
장점
한정된 저장 공간을 효율적으로 사용할 수 있다.
해시 함수에 대한 의존성이 상대적으로 적다.
메모리 공간을 미리 잡아 놓을 필요가 없다.(그때그때 이어 붙이기 때문)
단점
한 hash에만 자료가 계속 들어간다면(쏠린다면) 검색 효율이 떨어진다(.최악의 경우 O(n))
외부 저장공간을 사용한다.
충돌 해결2. Open Addressing(개방주소법)
개방주소법은 데이터의 해시(hash)가 변경되지 않았던 chaining과는 달리 비어있는 해시(hash)를 찾아 데이터를 저장하는 기법이다. 따라서 개방주소법에서의 해시테이블은 1개의 해시와 1개의 값(value)가 매칭되어 있는 형태로 유지된다.
장점
추가 저장공간이 필요없다
단점
해시 함수의 성능에 전체 해시테이블의 성능이 좌지우지 된다.
데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야한다.
Chaining 기법을 사용한 해시테이블 구현
HashTable 클래스
import java.util.LinkedList;
public class HashTable {
class Node{
String key;
String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
String getValue() {
return value;
}
void setValue(String value) {
this.value = value;
}
}
//각 배열 칸에 링크드리스트를 넣음으로서 collision이 발생할 시 뒤에 이어나간다.
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 convertHashCodeToIndex(int hashcode) {
return hashcode % data.length;
}
//배열의 인덱스에 노드가 여러개 있다면 key를 통해 알맞은 value를 찾는 메소드
Node searchKey(LinkedList<Node> list , String key) {
//리스트에 아무것도 없으면 null 반환
if(list == null) {
return null;
}
//리스트에 있는 노드중에 찾는 key를 가진 노드가 있다면 반환
for(Node node : list) {
if(node.key.equals(key)) {
return node;
}
}
//리스트에 노드가 없다면 null 반환
return null;
}
//key-value를 저장하는 메소드
void put(String key, String value) {
int hashcode = getHashCode(key);
int index = convertHashCodeToIndex(hashcode);
//배열의 해당 인덱스에 들어가있던 리스트 가져온다
LinkedList<Node> list = data[index];
//배열의 해당 인덱스 번지에 아직 리스트가 없다면
if(list == null) {
//리스트 만들고 해당 인덱스에 넣는다
list = new LinkedList<Node>();
data[index] = list;
}
//가져온 리스트에 지금 넣고자하는 key가 먼저 들어가있는지 확인
Node node = searchKey(list, key);
//노드가 없다면 처음 들어가는 key라는 의미
if(node == null) {
list.addLast(new Node(key, value));
}
else {
//이미 해당 key로 들어가있는 노드가 있다면 지금 넣는 key로 덮어쓰기
node.value = value;
}
}
//key를 통해 value 가져오는 메소드
String get(String key) {
int hashcode = getHashCode(key);
int index = convertHashCodeToIndex(hashcode);
LinkedList<Node> list = data[index];
//해당 인덱스에 있는 list에서 key를 통해 value를 찾는다
Node node = searchKey(list, key);
//해당 key값의 node가 없으면 Not Found반환, 있으면 value 반환
return node == null ? "Not Found" : node.value;
}
}
HashTest 클래스
public class HashTest {
public static void main(String[] args) {
//크기 3의 해쉬테이블 생성
HashTable ht = new HashTable(3);
ht.put("Lee", "lee is pretty");
ht.put("Kim", "kim is smart");
ht.put("Hee", "hee is an angel");
ht.put("Choi", "choi is cute");
//존재하는 데이터 검색
System.out.println(ht.get("Lee"));
System.out.println(ht.get("Kim"));
System.out.println(ht.get("Hee"));
System.out.println(ht.get("Choi"));
//존재하지 않는 데이터 검색
System.out.println(ht.get("Kang"));
//기존 데이터 덮어쓰기
ht.put("Choi", "choi is sexy");
System.out.println(ht.get("Choi"));
}
}
데이터는 Node라는 클래스 형태로 저장된다. Node는 key와 value를 가지고 있고 Value의 getter와 setter가 있다.
해시테이블은 배열로 선언하였고 각 칸마다 LinkedList<Node>형으로 선언하여 chaining 기법을 통한 Collision 회피 기법을 선택하였다.
//각 배열 칸에 링크드리스트를 넣음으로서 collision이 발생할 시 뒤에 이어나간다.
LinkedList<Node>[] data;
해시함수는 key의 각 문자들을 유니코드로 반환하여 모두 더하는 방식으로 구성했다.
인덱스는 해시코드를 해시테이블의 사이즈로 나눈 나머지 값을 사용했다.
//키를 해쉬코드로 변환하는 메소드
int getHashCode(String key) {
int hashcode = 0;
for(char c : key.toCharArray()) {
hashcode += c;
}
return hashcode;
}
//해쉬코드를 배열의 인덱스로 변환하는 메소드
int convertHashCodeToIndex(int hashcode) {
return hashcode % data.length;
}
조회를 희망하는 key를 받아서 value를 찾는 메소드이다. key를 받아서 해시함수로 변환 후 인덱스로 변환하여 해당 인덱스에 존재하는 list를 가져온다. 그 리스트에서 우리가 입력한 key를 가진 Node를 찾는 searchKey 메소드를 통해 목적 Node를 찾아낸다.
//key를 통해 value 가져오는 메소드
String get(String key) {
int hashcode = getHashCode(key);
int index = convertHashCodeToIndex(hashcode);
LinkedList<Node> list = data[index];
//해당 인덱스에 있는 list에서 key를 통해 value를 찾는다
Node node = searchKey(list, key);
//해당 key값의 node가 없으면 Not Found반환, 있으면 value 반환
return node == null ? "Not Found" : node.value;
}
searchKey 메소드에서는 우리가 입력한 key를 가진 Node가 존재하는지 확인한다.
//배열의 인덱스에 노드가 여러개 있다면 key를 통해 알맞은 value를 찾는 메소드
Node searchKey(LinkedList<Node> list , String key) {
//리스트에 아무것도 없으면 null 반환
if(list == null) {
return null;
}
//리스트에 있는 노드중에 찾는 key를 가진 노드가 있다면 반환
for(Node node : list) {
if(node.key.equals(key)) {
return node;
}
}
//리스트에 노드가 없다면 null 반환
return null;
}
해시테이블에 데이터를 넣는 메소드로 chaining 기법을 구현했다. 중복되는 key가 이미 존재할 경우 해당 key에대한 value를 덮어쓰는 것으로 구현했다.
//key-value를 저장하는 메소드
void put(String key, String value) {
int hashcode = getHashCode(key);
int index = convertHashCodeToIndex(hashcode);
//배열의 해당 인덱스에 들어가있던 리스트 가져온다
LinkedList<Node> list = data[index];
//배열의 해당 인덱스 번지에 아직 리스트가 없다면
if(list == null) {
//리스트 만들고 해당 인덱스에 넣는다
list = new LinkedList<Node>();
data[index] = list;
}
//가져온 리스트에 지금 넣고자하는 key가 먼저 들어가있는지 확인
Node node = searchKey(list, key);
//노드가 없다면 처음 들어가는 key라는 의미
if(node == null) {
list.addLast(new Node(key, value));
}
else {
//이미 해당 key로 들어가있는 노드가 있다면 지금 넣는 key로 덮어쓰기
node.value = value;
}
}
