Java - 해시(hash)(1/2)

◎해시(hash)란 

임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다.

해시값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)으로 검색과 저장이 매우 빠르다.

(검색할 때 사용하는 값(key)이 해시함수에 의해서 배열의 인덱스로 바로 변환되기 때문에 그 인덱스의 값(value)을 아주 빠르게 찾을 수 있다.)

 

---

 

◎해싱(hashing), 해시함수(hash function), 해시 알고리즘, 해시 코드(hashcode), 해시 테이블(hashtable)

키에 대한 hashcode값을 구하는 과정을 hashing이라고 하며 이때 사용하는 함수(알고리즘)를 hashfunction라고 한다.

구한 hashcode값을 hashtable이라는 배열에 저장한다.

 

ex. 길이가 11인 배열(hashtable)에 17(key:17, value:17),23(key:23, value:23)를 나눗셈 법(hashfunction의 일종)으로 hashing 해서 저장 및 22(key:22) 탐색하기

1. 17%11 = 6이므로, hashable의 인덱스 6에 17을 저장한다. (시간 복잡도:O(1))

2. 21%11 = 10이므로, hashtable의 인덱스 10에 21을 저장한다. (시간 복잡도:O(1))

3. 22%11 = 0이므로, hashtable의 인덱스 0을 탐색한다. (시간 복잡도:O(1))

4. 인덱스 0에 아무것도 없으므로, 22은 hashtable에 존재치 않는다.

=> 매우 빠르게 검색과 저장을 수행가능

하지만 만약 6을 저장하려 하면, 6%11=6이므로, 이미 17이 저장되어있는 인덱스 6에서 해시 충돌(collision)이 발생하게 된다.

---

◎해시(hash)의 사용목적

- collision이 발생할 가능성이 있음에도 해시를 사용하는 이유는 적은 리소스로 많은 데이터를 시간 효율적으로 관리할 수 있기 때문이다. 하지만 시간이 효율적인 만큼 데이터를 담을 hashtable의 크기를 미리 크게 확보해 놓아야 하므로 공간적으로는 비효율적이다.(해시 테이블은 데이터가 입력되지 않은 공간이 많아야 제 성능을 유지할 수 있다. 빈 공간이 많을수록 보통 충돌할 가능성이 줄어들기 때문이다.)

-데이터를 저장 탐색하는 자료구조로서의 역할뿐만 아니라, hash function을 통과한 key값은 그 원형을 역추적하기 힘드므로, 암호화에서도 자주 사용된다. 또한, 커다란 데이터를 해싱하면, 일정한 길이의 해시 코드가 나오므로 데이터를 축약하기 위해서 사용되기도 한다.

---

◎대표적인 해시함수(hashfunction)

 

- 나눗셈법

해시 함수 중에서도 가장 간단한 방법으로, 입력값을 테이블 크기로 나누고, 그 나머지를 인덱스로 활용하는 방법이다.

테이블의 크기를 2의 제곱수와 거리가 먼 소수(primenumber)로 정할수록 충돌 가능성이 줄어든다고 알려져 있다,

 

주소 = 입력값 % 테이블 크기

 

    //저장
    public void add(int key, int value){
        
        hashtable[div(key)] = value;
        
    }
    
    //나눗셈법
    private int div(int key){
        return key % this.hashtable.length;
    }

결과:

0 0 0 0 50 0 0 0 0 0 0 11 0 0 0 0 0 40 0 0 0 0 0

간단하게 구현할 수 있지만, 충돌(collision) 문제나 클러스터(cluster, 똑같은 해시 값이 아니더라도 해시 테이블 내의 일부 지역의 주소들을 집중적으로 반환하는 결과로 데이터들이 한 곳에 모이는 것) 문제에 취약하다.

 

 

- 자릿수 접기

일의 자리, 혹은 십의 자리 단위로 key값을 접어서 모두 더한 값을 key값으로 사용하는 방식이다.

ex) 751을 한 자릿수 접기로 해싱하면 7+5+1 = 13의 해시 코드 값이 나온다.

문자열을 키로 사용하는 해시 테이블에서 자주 쓰이는 알고리즘이며, 나눗셈 법보다는 collision, cluster 문제가 덜하다.

문자열을 자리수 접기 방식으로 해싱(출처: https://dbehdrhs.tistory.com/70)

코드:

//저장
    public void add(String string, int value){
        
        //해싱해서 인덱스 값으로 사용
        hashtable[digitfolding(string)] = value;
        
    }
    
    //자릿수 접기
    private int digitfolding(String string){
        int total = 0;        
        for(int i = 0; i<string.length(); i++){
            total = total + (int)string.charAt(i); //문자를 ASCII 코드 값으로 바꾸어 각각 더한다
        }
        
        return total % hashtable.length;
    }

 

자릿수 접기 해시함수의 문제점은 문자열의 길이에 따라 return 값이 제한되고 저장할 수 있는 공간이 달라진다는 것이다.

 

ex) 문자열의 길이가 10이라면, total값은 ASCII 코드의 값이 0~127 사이의 값이므로, 0~1270(127*10) 중에 하나이다.

만약 hashtable의 길이가 1270보다 큰 수 10000이라면, 이 해시함수로는 어떤 값을 넣더라도, 1271~ 9999의 값을 return 할 수 없으며, 이는 hashtable에서 index 1271~ 9999까지의 공간을 버리는 것과 같다.

 

 

코드 개선:

hashtable에 잉여 공간이 없도록 하기 위해서, shift연산자(<<)를 사용한다.

ex. DEC(10진수) 10000은 BIN(이진수)로 10 0111 0001 0000 (14자리)이다.

문자열의 길이가 10일 때, total 최댓값 DEC 1270은 BIN로 100 1111 0110(11자리)이다.

hashtable에 잉여 공간이 없도록 하기 위해서는 total값이 BIN로 14자리 이상 이어야 하므로 <<3을 이용한다,

 

코드:

//저장
    public void add(String string, int value){
        
        //해싱해서 인덱스 값으로 사용
        hashtable[digitfolding(string)] = value;
        
    }
    
    //자릿수 접기
    private int digitfolding(String string){
        int total = 0;        
        for(int i = 0; i<string.length(); i++){
            total = (total << 3) + (int)string.charAt(i); 
            //문자를 ASCII 코드 값으로 바꾸어 각각 더한다
            //shift 연산자를 이용해 잉여 공간이 없도록 한다
        }
        
        return total % hashtable.length;
    }

---

◎해시 충돌(hash collision)

해시 함수가 서로 다른 입력 값에 대해 동일한 해시 테이블 주소를 반환하는 것을 '충돌(Collision)'이라고 한다.

어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지는 못하므로, 해시 충돌이 생긴다.

 

-해시 충돌 해결:

1. OpenHasing(개방 해싱): 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 해결하는 방법,

해시함수에 의해 얻어진 주소가 아니더라도 다른 주소를 사용할 수 있음

2. ClosedHasing(폐쇄 해싱): 해시 테이블의 공간 안에서 문제를 해결하는 방법

해시함수에 의해 얻어진 주소가 아니면 다른 주소를 사용할 수 없음

---

◎체이닝(chaining)

폐쇄 해싱 방법 중 하나로, 충돌이 발생하면 각 데이터를 그 인덱스에서 선언된 링크드 리스트에 삽입하여 문제를 해결한다.

체이닝(chaining) (출처:https://dbehdrhs.tistory.com/70) 

코드:

import java.util.LinkedList;

public class Main {
    
    public static void main(String[] args) {
        Contact person1 = new Contact("abc","010"); // 이름: abc, 연락처: 010
        Contact person2 = new Contact("akj","011"); // 이름: akj, 연락처: 011
        
        ChainingHashTable hashtable = new ChainingHashTable(26);
        hashtable.put(person1.getKey(), person1.getValue()); //hashtable에 값 넣기
        hashtable.put(person2.getKey(), person2.getValue()); //해싱함수에서 맨 앞자리 알파벳만 비교하므로 abc와 akj는 같은 linkedlist에 들어간다
        
        System.out.println(hashtable.get("abc"));
        System.out.println(hashtable.get("akj"));
        
        
    }

}
class Contact {
    private String key;        //name
    private String value;     //phone number
    public Contact(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;
    }
}


    
class ChainingHashTable {
    
    public LinkedList<Contact>[] data; //array of LinkedList
    
    public ChainingHashTable(int size) {
        data = new LinkedList[size];
    }
 
    int getHashCode(String key) {
        int hashCode = key.charAt(0)-'a'; //맨 앞자리만 비교
        return hashCode;
    }
    
    int convertToIndex(int hashCode) {
        return hashCode % 26;
    }
    
    public void put(String key, String value) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        Contact contact = new Contact(key,value);
        if(data[index] == null) { //비어있으면 linkedlist 생성
            data[index] = new LinkedList();
        }
        data[index].add(contact); //데이터 추가
    }
    
    public String get(String key) {
        
        int hashCode = getHashCode(key);
        int index = convertToIndex(hashCode);
        LinkedList<Contact> contacts = data[index];
        for(Contact c : contacts) { //linkedlist를 선형 탐색하면서, key와 같은 값이 있으면 값 return
            if(c.getKey().equals(key)) {
                return c.getValue();
            }
        }
        return null;
    }
}

결과:

010
011

극단적으로, 모든 데이터의 hashcode가 같아서 한 LinkedList에 모든 데이터가 들어간다면, 시간 복잡도는 list의 탐색과 같은 O(N)이다.

---

Hash 관련 내용의 양이 많아서 2개의 글로 나누어 포스팅하겠다.

kkwong-guin.tistory.com/45

Java - 해시(hash)(2/2)