[자료구조] 자바 해시 소개 및 구현

https://www.youtube.com/playlist?list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk

Data Structures

 

Rob Edwards 교수님의 CS310 Data Structures in Java를 공부하고 정리한 내용입니다.

 

부스트 코스 자바로 구현하고 배우는 자료구조에서도 학습할 수 있습니다.

 

이번 포스팅에서는 Linked List와 비교하여 해시가 어떤 장점이 있는지 알아보고, chaining 등 충돌 문제를 해결하기 위한 방법을 알아봅니다. 체인 해시를 직접 구현해봅니다.

---

Hash Introduction

Hash는 key와 value를 가지고 있는데, key가 주어지면 연관된 value를 바로 얻어낼 수 있다. find, contains 등 특정 원하는 요소를 찾을 때 Linked List는 시간복잡도가 O(n)이라는 단점이 있다. 하지만 Hash를 사용하면 시간복잡도 O(1)로 원하는 값을 찾을 수 있다.

 

Hash는 다음과 같이 두개의 Associative arrays를 사용한다.

 

 

Hash Function을 이용하면 어떤 값이나 객체가 들어왔을 때, 고유한 정수 값을 얻을 수 있다.

 

위 예제의 경우 Hash는 key인 student id에 Hash Function을 이용해서 특정한 정수값을 얻고, 그 값을 index로 grade에 key와 연관된 value를 저장한다.

 

그 과정에서 다른 객체임에도 같은 Hash Function의 결과가 나오는 충돌문제가 일어나기도 하는데, 이 포스팅에서 충돌 문제를 해결하기 위해 어떤 전략을 사용하는지, 그리고 어떻게 Hash를 구현하는지 정리해보려 한다.

---

Hash Function

Hash Function의 결과값은 정수인 고유한 property이다. 자유롭게 작성할 수 있지만 아래와 같은 점을 고려하면 좋다.

• be fast to compute
• if two things are "equal" should return the same value
• Always return the same value for an object during one run of the code
• possible to return different values for an object in seperate run
• minimize collisions

---

Hash Collision

 collision

예를 들어, phone number를 key로 사용한다고 하자. 619 555 1212의 경우 값이 너무 길어서 hash function을 통해 값을 줄이려 한다. 만약 hash function을 공백을 기준으로 더하게 구현한다면 hash code는 2386이 된다.

 

그런데 새 친구 번호가 619 550 1217이라고 하면 hash code는 마찬가지로 2386이 된다.

 

위처럼 서로 다른 두 key가 있을 때 같은 hash code를 갖는 것을 Collision이라고 한다. Collision이 일어나지 않기 위해서는 hash function을 복잡하게 작성해서 결과의 분포를 넓게 만들어주는 것이 좋다.

 

String

자바에서는 unicode를 사용해서 문자열을 표기한다. 문자열의 hashCode를 얻고 싶을 때, 각 character의 unicode를 더하는 것으로 구현한다고 하자. "this"의 hashCode를 구하면 t는 116, h는 104, i는 105, s는 115로 변환해서 440을 얻을 수 있다. 하지만 "hits", "tish" 처럼 순서만 다른 경우에 충돌이 일어난다. 그래서 문자열의 경우 다음과 같이 구현할 수 있다.

 

public int hashCode(String s) {
    int g = 31;
    int hash = 0;
    for (int i=0; i<s.length; i++)
        hash = g * hash + charAt(i);
    return hash;
 }

 

위와 같이 작성하면 g(g(g116 + 104) + 105) + 115 와 같이 분포를 넓힐 수 있다.

 

Compressing Number

hashCode를 array의 크기에 맞게 압축시킨다. 충돌을 방지하기 위해서는 해시테이블 크기를 최적화해야하는데, 홀수 혹은 소수로 만들면 좋다. hashCode의 결과를 table size로 나누는 방식을 사용한다. 그 나머지를 hashCode로 사용하는데, table size가 홀수거나 소수이면 결과의 분포가 고르게 나온다고 한다.

 

그런데 hashCode는 array의 index로 사용할 것이기 때문에 양수여야한다. hashCode의 결과는 음수가 될 수 있는데, 자바에서는 -10 % 3의 결과가 -1이다. 그래서 table size로 나누기 전에 hashCode를 양수로 바꾸는 과정이 필요하다.

 

Make Integer Positive

Java에서는 음수를 표현하기 위해 2의 보수를 사용한다. 양수일 때 첫 숫자는 0이고, 음수이면 1이다.

8진수를 예로 들면

0 1 1 1 1 1 1 0 = 126

0 1 1 1 1 1 1 1 = 127

1 1 1 1 1 1 1 1 = -1

1 1 1 1 1 1 1 0 = -2이다.

 

hashCode에 0x7FFFFFFF을 & 연산자를 이용해주면 음수로 바꿀 수 있다. & 연산자 이므로 맨 앞자리는 0으로 변환되고 그 뒷자리는 변환되지 않는다.

 

int hashval = data.hashCode(s) & 0x7FFFFFFF % tableSize

 

요약하면 위 방법으로 hashCode를 양수로 변환하고 tableSize에 맡게 압출시킬 수 있다.

---

LoadFactor() 메서드

LoadFactor λ : 해시에 데이터가 얼마만큼 있는지 알려준다. 

λ = number of entries / total size of array

 

보통 0.6, 0.7 이상일 때 table을 resize할 필요가 있다.

---

Chaining

collision을 해결하기 위한 구조로, Hash와 LinkedList를 합친 자료구조이다. 각 position 별로 Linked List를 만든다.

 

 

위 그림처럼 모든 position에 head 노드가 있는데, hashTable[hashValue]로 해당 위치의 Linked List에 접근할 수 있다.

 

hashTable[hashValue].add(hashElement)를 사용하면 데이터를 추가할 때 시간복잡도는 O(1)이다.

 

hashCode를 만드는 과정에서 Collision이 일어나도 아래 그림처럼 LinkedList에 계속해서 추가해주면 된다.

 

Chaining을 사용하면,많은 데이터를 수용할 수 있고 resizing 또한 자주해줄 필요가 없어서 안정적으로 사용할 수 있다. 하지만 Hash Function이 같은  Hash Code만 반환해서 하나의 chain이 너무 길어지면

 

최악의 경우 remove, find 등이 O(n)의 시간복잡도를 갖을 수 있다.

 

따라서 chain이 너무 길어지거나, loadFactor가 커지면 hash를 재조정한다.

 

rehashing 이전

rehashing 이후

 

연결 리스트의 위치를 그대로 옮기면, chain의 길이는 그대로이므로 여전히 find, remove 등에서 시간복잡도가 여전히 O(n)이 될 수 있다. 그래서 tableSize를 두배로 늘려주고 처음부터 다시 위치를 초기화한다. 

---

Hash 클래스 구현

위에 언급한 chain Hash를 구현할 것인데, array의 모든 position은 LinkedList이다. 내부 클래스로 HashElement를 가지고 있고 HashElement는 Key와 Valye를 가지고 있다.

 

해시 크기인 tableSize, 저장된 element 갯수 numElements가 있고, maxLoadfactor가 있다.

 

public class Hash<K, V> implements HashI<K,V> {
    class HashElement<K,V> implements Comparable<HashElement<K,V>> { // linkedList라는 것을 확신하려면?
        K key;
        V value;
        public HashElement(K key, V value) {
            this.key = key;
            this.value = value;
        }
        public int compareTo(HashElement<K,V> o) {
            return (((Comparable<K>this.key).compareTo(o.key))
        }
    }
    int numElements, tableSize;
    double maxLoadFactor;
    LinkedList<HashElement<K,V>> [] harray;
}

 

HashElement는 독립된 key를 가져야하므로, compareTo를 구현한다.

---

생성자

public class Hash<K, V> implements HashI<K,V> {
    class HashElement<K,V> implements Comparable<HashElement<K,V>> { // linkedList라는 것을 확신하려면?
        ...
    }
    int numElements, tableSize;
    double maxLoadFactor;
    LinkedList<HashElement<K,V>> [] harray;
    
    public class Hash<K,V> implements HashI<K,V> {
        LinkedList<HashElement<K,V>[] harray;
        public Hash(int tableSize) {
            this.tableSize = tableSize;
            harray = (LinkedList<HashElement<K,V>>[]) new LinkedList[tableSize];
            for (int i=0; i<tableSize;i++)
                harray[i] = new LinkedList<HashElement<K,V>>();
            maxLoadFactor = 0.75
            numElements = 0;
        }
    }
}

 

생성자에 대해 알아보는데, 초기에 harray의 모든 position에 empty한 LinkedList를 추가한다.

java api에서는 tableSize를 16으로, maxLoadFactor를 0.75로 초기화한다고 한다.

데이터를 추가할 때, hash의 LoadFactor가 maxLoadFactor보다 커지면 harray를 resize해야한다.

 

maxLoadFactor가 크면, resize를 자주해줄 필요 없지만 연결 리스트의 분포가 고르지 못하고 chain이 길어지는 단점이 있다. (따라서 데이터를 조회할 때 최악의 경우 O(n)의 시간복잡도를 가질 수 있다는 단점이 있다.)

 

maxLoadFactor가 작으면, resize를 자주해야하지만 ,연결 리스트를 골고루 분포할 수 있다.

일반적으로 0.75가 가장 적절한 Load Factor라고 한다.

---

Add() and Remove() method

add 메서드에는 4가지 과정이 필요하다.

1. loadFactor가 maxLaodFactor보다 커질시에 HashTable을 resize한다.

2. Key, Value에 따른 Object를 생성한다.

3. Key를 hashCode로 만들어서 index를 정한다.

4. harray에 삽입한다.

 

public class Hash<K, V> implements HashI<K,V> {
   //생략
    public boolean add(K key, V value) {
        // loadFactor에 따라 resize
        if (loadFactor() > maxLoadFactor)
        resize(tableSize*2);
        // 객체 생성
        HashElement<K,V> he = new HashElement(key, value);
        // Hash Code 추출
        int hashval = key.hashCode()
        hashval = hashval&0x7FFFFFFF;
        hashval = hashval % tableSize;
        // Hash Array에 삽입
        harray[hashval].add(he);
        numElement++;
        return true;
    }
}

 

헷갈리리 수 있는 점은 harray[hashval] 자체가 LinkedList라는 것이다.

 

remove는 더 간단하다. 위처럼 resize하거나 Object를 만들 필요 없이, index만 구한뒤에 harray에서 삭제하면 된다.

 

public class Hash<K, V> implements HashI<K,V> {
   //생략
    public boolean remove(K key, V value){
        // index 찾기
        int hashval = key.hashCode();
        hashval = hashval & 0x7FFFFFFF;
        hashval = hashval % tableSize;
        // 해당하는 index의 키와 값 제거
        harray[hashval].remove(he);

        numElements--;
        return true;
    }
}

---

getValue() 메서드

public class Hash<K, V> implements HashI<K,V> {
   //생략
    public V getValue(K key) {
        int hashval = key.hashCode()&0x7FFFFFFF % tableSize
        for (HashElement<K,V> he : harray[hashval]) {
            if (((Comparable<K>)key).compareTo(he.key) == 0)
                return he.val;
        return null;
    }
}

 

Key에 따라서 index인 hashval을 얻고, 해시에서 해당 hashval의 chain(LinkedList)을 얻는다.

그리고 Key를 찾을 때까지 탐색하고 같은 Key값을 따르면 해당하는 Value를 반환한다.

 

getValue()의 시간복잡도는

Best Case : O(1) 해시 충돌이 드물게 발생해서 연결 리스트의 요소가 적을 때

Worst Case : O(n) 해시 충돌이 빈번하게 발생하여 chain의 길이가 길어질 때

---

resize() 메서드

연결리스트가 너무 길어지면 resize함수를 사용해서 해시의 크기를 조절해야 한다. 새로운 연결리스트 배열을 만들어 기존 배열의 모든 요소의 key와 value를 찾아내어 복사한다.

 

resize의 시간 복잡도는 O(n)이기 때문에 maxLoadFactor를 적절하게 설정해서 너무 잦은 resize를 지양하는 것이 좋다.

 

public class Hash<K, V> implements HashI<K,V> {
   //생략
    public void resize(int newSize) {
        LinkedList<HashElement<K,V>>[] new_array = (LinkedList<HashElement<K,V>>[]) new LinkedList[newSize];
        for (int i=0; i<newSize;i++)
            new_array[i] = new LinkedList<HashElement<K,V>>();
        for (K key: this) {
            V val = getValue(key);
            HashElement<K,V> he = new HashElement<K,V>(key, val);
            int hashVal = (key.hashCode()&0x7FFFFFFF)%newSize;
            new_array[hashVal].add(he);
       }
        hash_array = new_array;
        tableSize = new_size;
    }
}

---

Key 반복자

LinkedList나 array는 순서가 있는 반면에, Hash는 순서가 없다. 해시코드에 의해 위치가 결정되기 때문에, resize 할 때마다 데이터의 순서가 바뀐다. 순서와 상관없이 모든 key를 반환한다.

class IteratorHelper<T> implements Iterator<T>{
    T[] keys;
    int position;
    public IteratorHelper() {
        Keys = (T[]) Object[numElements];
        int p =0;
        for (int i=0; i<tableSize; i++) {
            LinkedList<HashElement<K,V>> list = hash_array[i];
            for (HashElement<K,V> h : list)
                keys[p++]= (T)h.key();
        }
        position = 0;
    } //모든 key를 얻게됐다.
    public boolean hasNext() {
        return position<keys.length;
    }
    public T next() {
        if (!hasNext())
            return null;
        return keys[position++];
    }
}