이번에는 위 영상을 보고 Hash에 대해 다시한번 복습하고자 글을 써본다.
- Hashing이란?
- Hashing 구조
- Hash 간단 구현
1. Hashing란?
선요약
1.해싱은 자료를 저장하는 자료구조중 위치의 개념을 사용하지 않는 방법
2.자료를 Key,Value쌍으로 저장하고 Key만 있으면 자료를 찾는데 O(1)의 시간복잡도로 찾을 수 있다.
3.Key를 만들기 위해 해시함수가 존재 하며 해시함수의 성능에 따라 해싱의 효율이 달라진다.
4.Key를 만드는 해시함수를 잘만들어도 Key의 중복(충돌)이 일어날 수 있으니 대비를 잘해야한다.(체이닝)
우선 Hash는 컴퓨터에서 자료를 저장하는 컨테이너중 하나이다. 그런데 이 Hash는 여러 컨테이너들중(List,Queue,Stack...) 가장 컴퓨터를 이용한 컨테이너이다. 컴퓨터는 모든것을 숫자(이진수)로 표현한다. 지금보고있는 이 글도, 그림들도 결국에는 컴퓨터가 숫자로 바꿔서 표현한다. 이런 컴퓨터의 특성을 이용해서 만든게 Hash다.
해싱은 자료를 저장하고 탐색하는데 사용하는것에 있어서 굉장히 빠른편인데 그 이유는 다른 자료구조들과는 다르게 자료가 저장된 위치를 사용하지 않는다는 것이다.
무슨말인가하면 예를들어 LinkedList를 생각해보자. 우리가 LinkedList에 10가지 자료를 저장하고 그중 1가지를 찾는 경우 우리는 찾고자하는것의 위치가 나올때까지 시작 노드부터 다음노드까지 순차적으로 넘어갈 것이다.
반면에 해싱은 내가 찾고자하는 자료의 위치라는 개념이 없다. 그저 자료의 Key만 있으면 된다. 이 Key만 있으면 O(1)의 시간복잡도로 자료를 찾을 수 있다.
해싱은 자료를 Key,Value 쌍(사전 구조,Dictionary)으로 저장하기 때문에 자료를 빠르게 찾을 수 있다. 여기서 Key는 저장한 자료를 찾기위한 인덱스가 되고 Value는 저장할 자료가 된다.
위와 같은 구조를 해시테이블이라고 한다. 저기서 알파벳 D를 찾기위해서는 Key에 해당하는 68만 알고 있으면 되는 것이다.
아마 눈치를 챘겠지만 위 해시테이블은 알파벳을 저장하기위한 Key로 아스키코드를 사용했다. 그런데 여기서 한가지 궁금한 점이 생길 수 있다. 위처럼 Key로 쓸 수 있는 값을 어떻게 정하는가이다.
Key를 정하는 방법을 설명하자면 Key는 정수로 정해야 하는데 그이유는 Key값을 배열로 저장해야 하기 때문이다. 그이유는 배열에 인텍스를 넣기만 하면 값을 바로 찾을 수 있기때문이다. 그러면 배열로 했을때는 문제가 없을까? 문제가 있다. 배열은 크리를 가변적으로 늘릴 수 없다. 그리고 저장할 데이터의 범위를 모른다면 배열의 크기를 어떻게 초기화 할지 모른다는 것이다.
하지만 이런 배열의 문제를 해결하기 위해 해시함수라는 것이 있다. 해시함수는 저장할 자료를 넣으면 적당한 정수형 Key값을 반환하는 함수이다. 해싱에서도 이 해시함수가 가장 중요한 역할을 한다. 해시함수를 잘못 만든다면 해싱의 효율성이 떨어지기 때문이다.
해시함수의 조건은 다음과 같다
1. Key값의 중복이 적어야한다
2. 테이블의 범위내에서 Key값의 범위가 골고루 분포되어야 한다.
3. Key를 반환하는 계산이 빨라야한다.
위 같은 조건을 만족시키는 것외에도 해시함수를 만들때 생각할 것이 몇가지 더 있다. 해시테이블의 크기, 저장할 자료의 자료형등 이 있다.
이런 복잡한 해시함수를 직접 구현할 수도 있지만 요즈음의 최신언어들은 각 객체마다 해시코드를 만들어주는 함수들이 있어서 직접 구현할 필요는 없다. (해시테이블도 다 구현이 되어있다.)
그럼 해시함수만 구현하면 끝일까? 아니다 아무래도 해시테이블의 크기에비해 입력될 자료의 크기가 훨신큰 경우가 많기 때문에 Key들간의 중복이 생길 수 밖에 없다. 이런 Key의 중복을 충돌(collision)이라고 한다.
이런 충돌의 해결하기 위해서 2가지 방법이 있다.
1. 선형조사볍
2. 체이닝
우선 선형조사법은 구현이 간단할 수도 있지만 탐색 효율이 떨어질 수도 있다는 단점이 있어서 체이닝으로 구현하는 것이 보다 바람직하다.
그럼 체이닝을 설명해보겠다. 체이닝은 키값에 저장된 Value들을 연결 리스트로 저장하는 것이다.
Key값이 중복된다면 Value에 리스트에 추가로 저장하는 방식이다.
장점은 연결리스트이기 때문에 메모리 낭비도 수행시간이 빠른편이다.
단점은 Key값의 쏠림을 해결할 수 없다는 것이다.
2. Hashing 구조
위에서 설명한 Hashing의 구조를 도식화 하면 아래와 같다.
Bucket은 테이블의 크기로 생각하면 되고, Slot은 체이닝의 연결리스트라고 생각하면 된다.
3. 구현
그럼 해시테이블을 간단하게 구현해보자.
public interface HashInterface<K,V> {
void add(K key,V value); // 자료를 추가
V delete(K key); // 자료를 삭제, 성공하면 Value 반환, 없으면 null 반환
V search(K key); // 탐색, 없으면 null 반환
}우선 인터페이스를 정의했다.
그럼 위 인터페이스를 토대로 구현하기 위해서 필요한 것들을 정리해보자.
1. 테이블의 크기 -> 기본으로 10을 잡고 생성자를 통해 정할 수 있도록한다.
2. 입력받은 Key를 해시함수로 해시코드로 변환하는 함수
3. key가 있는 slot에서 key에 해당 노드를 찾는 함수
public class MyHash<K,V> implements HashInterface<K,V> {
private LinkedList<Node>[] table;
private final int defaultTableSize=10; // 테이블의 기본 크기
private int size; // 테이블의 크기
private int length=0; //현재 해시테이블에 저장되어있는 자료들의 크기
public int length(){
return length;
}
public MyHash(int size){
table=new LinkedList[size];
this.size=size;
}
public MyHash(){
table=new LinkedList[defaultTableSize];
this.size=defaultTableSize;
}
// key 가 있는 node를 가져온다
private Node findNode(LinkedList<Node> slot,K key){
Node node=null;
for(int i=0;i<slot.size();i++){
Node now=slot.get(i);
if(now.hash==key.hashCode()){
node=now;
slot.remove(i);
break;
}
}
return node;
}
@Override
public void add(K key,V value) {
if(search(key)!=null) return; //입력된 값이 중복이면 추가 X
int hash=key.hashCode()%size;
Node node=new Node(key,value,key.hashCode());
if(table[hash]==null){
table[hash]=new LinkedList<>();
}
table[hash].add(node);
length++;
}
@Override
public V delete(K key) {
int hash=key.hashCode()%size;
LinkedList<Node> slot=table[hash];
Node node=findNode(slot,key);
if(node!=null) {
slot.remove(node);
length--;
return node.v;
}
return null;
}
@Override
public V search(K key) {
int hash=key.hashCode()%size;
LinkedList<Node> slot=table[hash];
if(slot==null) return null;
Node node=findNode(slot,key);
if(node!=null)
return node.v;
return null;
}
private class Node{
private K k;
private V v;
private int hash;
private Node(K k,V v,int hash){
this.k=k;
this.v=v;
this.hash=hash;
}
}
}
실행 코드
public class Main {
public static void main(String[] args) {
//MyHash
Person person1=new Person("철수",12);
Person person2=new Person("짱구",13);
Person person3=new Person("맹구",14);
Person person4=new Person("훈이",15);
Person person5=new Person("유리",16);
MyHash<String,Person> hash=new MyHash<>();
hash.add(person1.name,person1);
hash.add(person2.name,person2);
hash.add(person3.name,person3);
hash.add(person4.name,person4);
hash.add(person5.name,person5);
Person jjangu=hash.search("짱구");
System.out.println(jjangu.name+" "+jjangu.age);
System.out.println(hash.length());
System.out.println();
Person hooni=hash.delete("훈이");
System.out.println(hooni.name+" "+hooni.age);
System.out.println(hash.length());
}
}
실행 결과
