해시테이블 자료구조 구현하기

github.com/donghyeon0725/algorithm_java

donghyeon0725/algorithm_java

제 깃허브입니다.

 

설명 링크

github.com/donghyeon0725/algorithm_java/blob/master/src/com/dataType/hashtable/README.md

donghyeon0725/algorithm_java

위 문서는 Markdown 형식으로 제작 되었습니다. 

안타깝게도 티스토리는 Markdown을 온전하게 지원하지 않아서 링크를 첨부합니다.

 

---

 

기본원리

 

키값(보통 문자열)을 해시라는 함수에 넣어서 해시값을 받아내고 (보통 int) 이를 다시 인덱스로 변환해서 배열에 접근하는 방법이다.

---

충돌

 

특정 두 가지 키값에 대해, 같은 해시값을 반환할 우려가 있음

그러면 같은 주소에 접근하는 것

이를 해시 충돌이라고 하는데 이것을 해결하는 방법에 따라

 

1. LinearHashtable : 선형 해시 테이블

2. ChaningHashtable : 체이닝 해시 테이블 

 

이라고 부를 수 있다. 

 

 

---

용어

 

제가 해시테이블을 구현할 때, 

기본적으로 관련 용어를 사용해서(예를 들면 슬롯, 해시, 해시값 등등) 구현했기 때문에 용어에 대해 미리 알아야 이해하기 수월하실 겁니다.

 

 

• 해쉬 => 임의 값을 고정 길이로 변환하는 것 (임의의 값을 특정 길이의 값으로 변환하는데, 그 값은 특정 의미를 가짐)
• 해쉬 테이블 => 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조(배열 : 키를 연산해서 얻은 인덱스로 접근이 가능함)
• 해싱 함수 (Hashing Function) => Key 에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 (주소를 찾을 수 있게 만듬, 원리 : 복호화가 안되고, 암호화할 때 같은 값을 암호화 하면 무조건 같은 해쉬 값이 나오는게 이 함수의 특징이다.)
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address) => Key를 해싱함수로 연산해서, 해쉬값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 key에 대한 데이터 위치를 있게 찾을 수 있음
• 슬롯(Slot) => 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 key를 추출할 수 있는 별도 함수도 존재할 수 있음

 

 

---

특징

 

장점

• 데이터 저장/읽기 속도가 빠르다.(검색속도가 빠르다.)
• 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움 => 바로 확인이 가능함(인덱스에 값이 있는지 확인만 하면 됨)

단점

• 일반적으로 저장 공간이 좀더 많이 필요하다. (미리 공간을 잡아두어야 함. 해시 함수를 통해서 나올 수 있는 값의 최대값 만큼 공간을 미리 할당해야함)
• 여러 키에 해당하는 주소가 동일한 경우 충돌을 해결하기 위한 별도 자료구조가 필요함 => 이 때문에 중복을 해결하기 위한 해시가 즉 성능이 된다. 일반적으로 공간을 많이 잡아 놓음으로서 성능 문제를 해결할 수 있긴함

주요용도

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 캐쉬 구현시(중복확인이 쉬워서) => url 에 매핑을 함으로써, url 앞에 해당하는 이미지를 저장해둠(자신의 pc에)

 

---

소스 구현하기에 앞서

 

해시 테이블을 구현하기 위해 내부적으로 LinkedList와 같은 자료형을 사용하고 있습니다.

보면 아시겠지만, 자바에서 기본제공하는 소스가 아니라 

제가 구현한 소스입니다. 

따라서 사용하실 때는 java 에서 기본 제공하는 것으로 바꾸셔야 할 수도 있습니다.

기본적인 사용법은 똑같이 구현을 해두어서, 

import 하는 부분의 소스만 바꿔주셔도 될 겁니다 (아마?)

 

1. ChainingHashTable 구현

package com.dataType.hashtable;

import com.dataType.linkedlist.LinkedList;

/**
 * **원리(Chaining 기법으로 충돌 해결[배열에 링크드리스트를 넣는 방법])**
 *
 * 해시 값을 가져온다.
 * 해시 값을 배열의 인덱스로 변환한다.
 * 인덱스 안에 해시값과 데이터를 함께 넣는다.
 *
 * 1. put
 * 2. get
 * 3. remove
 * 4. getHash
 * 5. convertToIndex
 * 6. searchKey
 *
 * 특히 getHash, convertToIndex, searchKey(슬롯을 찾는다) 세가지 메소드를 신경쓰며 구현하는 것이 구조설계에 있어서 중요한 것 같다.
 * */
public class ChainingHashTable<T> {
    private int capacity;
    /**
     * 데이터를 저장할 배열을 생성
     * 해시값으로 얻은 인덱스가 충돌의 경우를 대비해서 LinkedList로 생성을 한다.
     */
    LinkedList[] hashtable = null;

    /**
     * 데이터를 저장하는 구조이다.
     * 고유 식별 값인 해시와 데이터를 저장하는 공간이다.
     * */
    private class Slot<N> {
        int hash = 0;
        N value = null;

        public Slot(int hash, N value) {
            this.hash = hash;
            this.value = value;
        }
    }

    /**
     * 생성자를 통해서 저장 공간의 크기를 정한다.
     * 
     * 슬롯을 더 많이 사용할 수록 해시 충돌이 적어서, 접근이 빠르다.
     * */
    public ChainingHashTable(int capacity) {
        this.capacity = capacity;
        this.hashtable = new LinkedList[capacity];
    }

    /**
     * 값을 식별할 해쉬값을 얻는다.
     * */
    private int getHash(String key) {
        int hashCode = 0;
        for(char c : key.toCharArray()) {
            // 아스키 코드를 모두 더한 값을 해시값으로 사용한다.
            hashCode += c;
        }
        return hashCode;
    }

    /**
     * 해시값을 인덱스로 변환한다.
     * */
    private int convertToIndex(int hash) {
        return hash % capacity;
    }

    /**
     * 인덱스를 통해 찾은 LinkedList에서 hash 값을 비교하여 슬롯을 찾아온다.
     * */
    private Slot<T> searchSlot(LinkedList<Slot> list, int hash) {
        if (list == null) return null;
        Slot slot = null;
        for (int i=0; i<list.size(); i++) {
            slot = list.get(i);
            if (slot.hash == hash) {
                return slot;
            }
        }
        return null;
    }

    /**
     * 데이터를 삽입한다.
     *
     * 1. 해시값을 받는다.
     * 2. 인덱스로 변환해서 얻은 주소로 접근한다.
     * 3. 접근한 주소에 값이 없으면 링크드 리스트를 생성하고 있으면, 슬롯을 찾는다.
     * 4. 중복되는 키 값이면 덮어쓰기, 아닌 경우 그냥 추가
     * */
    public void put(String key, T data) {
        int hash = getHash(key);
        int index = convertToIndex(hash);

        if (this.hashtable[index] == null) {
            hashtable[index] = new LinkedList<T>();
        }

        // 슬롯을 찾는다.
        Slot<T> slot = searchSlot(hashtable[index], hash);

        if (slot == null) {
            hashtable[index].add(new Slot<T>(hash, data));
        } else {
            // 슬롯이 이미 있을 때, 키 값이 같은지 다른지 비교해야함
            slot.value = data;
        }
    }

    /**
     * 인덱스로 링크드리스트를 찾고
     * 찾은 링크드 리스트에서 슬롯을 찾아 data를 반환한다.
     * */
    public T get(String key) {
        int hash = getHash(key);
        int index = convertToIndex(hash);

        if (this.hashtable[index] == null) {
            return null;
        }

        Slot<T> slot = searchSlot(hashtable[index], hash);

        if (slot == null) {
            return null;
        } else {
            return slot.value;
        }
    }

    /**
     * 인덱스를 먼저 찾고
     * 찾은 링크드리스트에 동일한 해시값을 가진 슬롯이 있으면 제거
     * */
    public void remove(String key) {
        int hash = getHash(key);
        int index = convertToIndex(hash);

        LinkedList<Slot> list = hashtable[index];

        for (int i=0; i<list.size(); i++) {
            if (list.get(i).hash == hash) {
                list.remove(i);
                return;
            }
        }
    }

}

 

출력

// 슬롯 크기 3으로
ChainingHashTable ht = new ChainingHashTable(3);

ht.put("sung", "She is pretty");
ht.put("jin", "She is model");
ht.put("hee", "She is hee"); // => 같은 306 이라는 해시값을 가짐
ht.put("hfd", "She is hfd"); // => 같은 306 이라는 해시값을 가짐
ht.put("min", "She is cute");
ht.put("sung", "She is sung"); // 중복된 키값


System.out.println(ht.get("sung")); // She is pretty 가 아닌 => She is sung
System.out.println(ht.get("jin"));
System.out.println(ht.get("hee")); // 해시값이 같음
System.out.println(ht.get("hfd")); // 해시값이 같음
System.out.println(ht.get("min"));
System.out.println(ht.get("jae")); // null

ht.remove("hfd");
System.out.println(ht.get("hfd")); // null

 

결과

She is sung
She is model
She is hfd
She is hfd
She is cute
null
null

---

2. LinearHashTable 구현

package com.dataType.hashtable;

/**
 * **원리(Linear 기법으로 충돌 해결[남는 공간을 찾아가는 기법])**
 *
 * 해시 값을 가져온다.
 * 해시 값을 배열의 인덱스로 변환한다.
 * 인덱스 안에 해시값과 데이터를 함께 넣는다.
 *
 * 1. put
 * 2. get
 * 3. remove
 * 4. getHash
 * 5. convertToIndex
 * 6. searchKey
 *
 * 특히 getHash, convertToIndex, searchKey(슬롯을 찾는다) 세가지 메소드를 신경쓰며 구현하는 것이 구조설계에 있어서 중요한 것 같다.
 * */
public class LinearHashTable<T> {
    private int capacity;
    Slot<T>[] hashtable = null;

    /**
     * 슬롯 객체
     * */
    private class Slot<N> {
        int hash = 0;
        N value = null;

        public Slot(int hash, N value) {
            this.hash = hash;
            this.value = value;
        }
    }

    public LinearHashTable(int capacity) {
        this.capacity = capacity;
        this.hashtable = new Slot[capacity];
    }

    /**
     * 선형 탐색 기법으로 인덱스 값 충돌 문제를 해결한 해시 테이블은 해시 함수의 성능이 곧 테이블의 성능이다.
     *
     * 해시함수가 각각 인덱스 간의 간격이 멀어지도록 잘 설계된 함수라면 빠른 성능을 보장하겠지만,
     * 촘촘하게 인덱스를 반환하는 함수라면 충돌이 많이 일어날 것이고 성능은 떨어지게 된다.
     * */
    public int getHash(String key) {
        int hashCode = 0;
        for(char c : key.toCharArray()) {
            // 아스키 코드를 모두 더한 값을 해시값으로 사용한다.
            hashCode += c;
        }
        return hashCode;
    }

    public int convertToIndex(int hash) {
        return hash % capacity;
    }

    /**
     * 해시값으로 얻은 인덱스를 찾아갔을 때
     * 이미 값이 있으면 빈 공간이 나올 때까지 찾아가 값을 넣는 방법이다.
     * 이때 해시 값을 슬롯에 같이 넣기 때문에 여전히 값은 식별이 가능하다.
     * */
    public void put(String key, T data) {
        int hash = getHash(key);
        int index = convertToIndex(hash);

        if (this.hashtable[index] == null) {
            hashtable[index] = new Slot(hash, data);
            return;
        }



        int nextIndex = index + 1;
        // 빈 공간을 찾을 때까지 탐색
        while( nextIndex < capacity && this.hashtable[nextIndex] != null ) {
            nextIndex++;
        }

        if (this.hashtable[nextIndex] == null) {
            this.hashtable[nextIndex] = new Slot<T>(hash, data);
        }

    }

    /**
     * 인덱스로 찾은 값에서 다음 값으로 넘겨가며 해시값을 비교해서 슬롯을 찾아온다.
     *
     * 값이 없다면 더이상 검색을 하지 않는다.
     * */
    public T get(String key) {
        int hash = getHash(key);
        int index = convertToIndex(hash);

        // 비어 있으면 null 리턴
        if (this.hashtable[index] == null) {
            return null;
        }

        if (this.hashtable[index].hash == hash) {
            return this.hashtable[index].value;
        }

        int nextIndex = index + 1;
        //같은 해시값을 찾을 때까지
        while ( nextIndex < capacity && this.hashtable[nextIndex] != null ) {
            if (this.hashtable[index].hash == hash) {
                return this.hashtable[index].value;
            }
            nextIndex++;
        }
        return null;
    }

    /**
     * 삭제할 때 중간에 값을 제거해버리면
     *
     * 충돌 문제로 다른 공간에 저장된 데이터에 대한 탐색을 멈춰버릴 가능성이 있기 때문에 그 자리에 비어 있지 않은 다른 값을 넣어주어야 한다.
     * */
    public void remove(String key) {
        int hash = getHash(key);
        int index = convertToIndex(hash);

        // 비어 있으면 null 리턴
        if (this.hashtable[index] == null) {
            return;
        }

        int nextIndex = index;
        //같은 해시값을 찾을 때까지
        while ( nextIndex < capacity && this.hashtable[nextIndex] != null) {

            if (this.hashtable[nextIndex].hash == hash) {
                this.hashtable[nextIndex] = new Slot<T>(-1, null); // 더미 데이터
                return;
            }

            nextIndex++;
        }
        return;
    }

}

 

출력

LinearHashTable ht = new LinearHashTable(8);

ht.put("sung", "She is pretty");
ht.put("jin", "She is model");
ht.put("hee", "She is hee"); // => 같은 306 번에 해당하는 해쉬값을 가짐
ht.put("hfd", "She is hfd"); // => 같은 306 번에 해당하는 해쉬값을 가짐
ht.put("min", "She is cute");
ht.put("sung", "She is sung"); // 중복된 키값


System.out.println(ht.get("sung")); // She is pretty 가 아닌 => She is sung
System.out.println(ht.get("jin"));
System.out.println(ht.get("hee"));
System.out.println(ht.get("hfd")); // 해시값 조차 같게 되는 경우 문제가 되긴 함.
System.out.println(ht.get("min")); // null
System.out.println(ht.get("jae")); // null

ht.remove("hfd");
System.out.println(ht.get("hfd")); // null

 

결과

She is pretty
She is model
She is hee
She is hee
She is cute
null
null