[자료구조] 해시 테이블(Hash Table) 이해와 구현 with 자바

 

🤔 해시?, 해시 테이블(Hash Table)?

해시 테이블을 알아보기 전에 해시(Hash)에 대해서 알아보겠습니다.

 

📌해시(Hash)

임의의 길이의 데이터를 고정된 길이의 값으로 매핑한 값을 말하며 해시 함수에 의해 매핑됩니다.

이때 매핑 전 원래 데이터를 키(Key), 매핑 후 고정된 길이의 값을 해시, 해시값(hash value)

매핑하는 과정을 해싱(hashing)이라고 합니다.

 

해시 함수에 의해 매핑된 해시값은 배열의 인덱스로 사용되고, 인덱스를 사용하여 값을 저장하거나 검색하게 됩니다.

 

📌 해시 테이블(Hash Table)

'저장된 자료의 양에 상관없이 평균 상수 시간 작업이 가능하게 할 수는 없을까?'

라는 질문을 시작으로, 자료를 검색, 삽입, 삭제하는 데 평균 O(1) 시간(상수시간)이 가능하도록 만든 효율적인 자료구조입니다.

 

해시 테이블은 키와 값쌍을 저장하는 자료 구조이며, 키를 해시 함수를 통해 해시 값으로 변환한 후에 해당 해시 값을 기반으로 배열 형태의 저장 공간(버킷)에 저장합니다.

여기서 버킷(bucket)은 실제 값이 저장되는 공간으로 개수가 고정적이며, 이후에 설명할 해시 충돌을 해결하기 위해 각 버킷에는 링크드리스트 등을 사용하여 여러 데이터를 저장하게 되는데 이를 슬롯(Slot)이라고 합니다.

 

장점 

•  key-value 구조로 1:1로 매핑되어 있기 때문에 검색, 삭제, 삽입과정에서 모두 평균적으로 O(1)의 시간복잡도를 갖고 있습니다 ( 빠르다 )

 

단점

• 인덱스가 순서대로 사용되어 데이터가 적재되지 않아 빈 공간이 생기며, 이는 공간의 낭비로 이어집니다.
• 해시 함수에 의해 매핑된 해시 값 즉, 인덱스가 중복될 경우 해시 충돌(Hash Collision)이 발생하게 되고 이를 해결하기 위해 추가적인 자료구조가 필요합니다.

 

 

✔ 해시 충돌(hash collision)

어떤 키가 이미 자리 잡고 있는 상태에서 다른 키가 삽입을 시도하는 것을 충돌이라고 합니다.

즉, 동일한 주소에 2개 이상의 키가 해싱되는 상황을 말합니다.

 

일차적으로는 해시함수를 구현할 때 '입력 키를 해시 테이블 전체에 고루 분산시켜 저장해야 한다'는 성질을 가지도록 구현해야 합니다.

두 키가 상대적으로 비슷하다고 해서 다른 키들보다 상대적으로 해시값이 더 비슷하지 않아야 하며, 이 성질을 잘 만족해야 서로 다른 두 키가 한 주소를 놓고 충돌할 확률이 낮아집니다.

 

해시함수를 잘 구현할지라도 충돌이 발생할 수 있습니다.

이를 체이닝(Chaining)과 개방 주소(Open Addressing)를 사용하여 해결할 수 있습니다.

 

💡 체이닝(Chaining)

같은 주소로 해싱되는 키를 모두 하나의 연결 리스트에 연결하여 관리하는 방법입니다.

위 그림처럼 입력한 키값을 해쉬 함수에 의해 해시값(인덱스)으로 반환하였고, 값이 같아 충돌하고 있습니다.

이럴 경우 슬롯을 연결리스트로 구현하여 해시값이 같더라도 충돌을 막을 수 있습니다.

값을 반환할 때에는 해당 버킷에 연결 리스트를 탐색 하며 key값과 일치하는 슬롯의 값을 반환하게 됩니다.

 

🔎 체이닝을 사용한 해시 테이블 구현

public class ChainedHashTable {
    public Slot[] hashTable;

    public ChainedHashTable(Integer size){
        this.hashTable = new Slot[size]; //입력받은 크기만큼 해시 테이블 생성
    }
    // 링크드 리스트 구현
    public static class Slot{
        String key;
        String value;
        Slot next;

        public Slot(String key, String value){
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }

    //해시 함수
    public Integer hashFunction(String key){
        return (int)(key.charAt(0)) % hashTable.length;
    }

    //데이터 저장
    public void saveData(String key, String value){
        Integer index = hashFunction(key);

        if(hashTable[index] != null ){ // 해당 인덱스에 데이터가 존재한다면 (충돌)
            Slot findSlot = hashTable[index];
            Slot prevSlot = hashTable[index];

            while ( findSlot != null){
                if( findSlot.key.equals(key) ){ //key값이 일치한다면 해당 key값의 value를 변경합니다.
                    findSlot.value = value;
                    return;
                } else { // key값이 일치하지 않는다면 다음 슬롯을 탐색하기 위해 설정 해줍니다.
                    prevSlot = findSlot;
                    findSlot = findSlot.next;
                }
            }

            prevSlot.next = new Slot(key, value);

        } else { // 해당 인덱스에 데이터가 존재하지 않는다면
            hashTable[index] = new Slot(key, value);
        }
        return;
    }

    public String getData(String key){
        Integer index = hashFunction(key);

        if(hashTable[index] != null ){
            Slot findSlot = hashTable[index];
            while (findSlot != null){// 연결 리스트를 탐색하며 key값과 일치하는 값을 반환합니다.
                if (findSlot.key.equals(key)) { 
                    return findSlot.value;
                } else {
                    findSlot = findSlot.next;
                }
            }
            return null;
        } else {
            return null;
        }
    }


    public static void main(String[] args) {
        ChainedHashTable hashTable = new ChainedHashTable(10);
        hashTable.saveData("Jang", "01021213111");
        hashTable.saveData("Hong", "01034873497");

        System.out.println(hashTable.getData("Hong"));
    }
}

 

💡 개방 주소 (Open Addressing)

체이닝과 달리 추가 공간을 사용하지 않고 충돌이 일어나더라도 주어진 공간에서 해결합니다.

이 때문에 모든 키가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없습니다.

또한 주어진 공간만 사용할 수 있으므로 적재율이 1을 넘을 수 없습니다.

 

 

📌 적재율

해시 테이블에 원소가 차 있는 비율은 해시 테이블의 성능에 매우 중요한 영향을 미칩니다.

이 비율을 적재율(Load Factor)이라고 하는데 해시 테이블의 크기가 m이고, 저장된 key의 총 수가 n이면 적재율은 n/m이 됩니다.

적재율이 높을수록 충돌 확률이 높아져 해시 테이블의 성능이 나빠집니다.

( 체이닝 방법은 적재율이 1을 넘어도 사용할 수 있습니다 )

 

개방 주소 방법은 충돌 시 주어진 테이블의 공간에서 다음 주소를 탐색하여 빈 공간에 저장합니다.

이때 다음 주소를 탐색하는 방법은 대표적으로 선형 탐색, 이차원 탐색, 더블 해싱 이 있습니다.

 

 

🔎 선형 탐색(Linear Probing)

가장 간단한 충돌 해결 방법으로, 충돌이 일어난 바로 다음 자리부터 순차적으로 탐색해 나가는 방법입니다.

 

🚨 1차 군집(Primary Clustering)

선형 탐색은 특정 영역에 키가 몰릴 때 치명적으로 성능이 떨어집니다.

이러한 현상을 1차 군집(Primary Clustering)이라고 합니다.

바로 다음 자리를 순차적으로 탐색해 나가기 때문에 몰려있는 영역에 해쉬값이 반환되었다면 몰려있는 만큼 탐색 횟수가 증가하게 되고, 영역이 커질수록 해당 영역이 해싱될 확률이 커지므로 군집이 심하지 않은 영역에 비해 영역의 크기가 빠르게 증가합니다.

 

 

🔎 이차원 탐색(Quadratic Probing)

바로 다음 자리를 탐색하는 대신 보폭을 이차 함수에 의해 넓히면서 탐색하는 방법입니다.

이렇게 되면 특정 영역에 키가 몰려도 이차 함수의 보폭만큼 이동하기 때문에 빠르게 군집 영역을 벗어날 수 있습니다.

🚨 2차 군집(Secondary Clustering)

하지만 여러 개의 키가 동일한 초기 해시 값을 갖는다면 모두 같은 순서로 탐색되기 때문에 비효율을 피할 수 업습니다.

이런 현상을 2차 군집(Secondary Clustering)이라고 합니다.

 

 

🔎 더블 해싱(Double Hashing)

2개의 해시함수를 사용하여 충돌 발생 시 다음 자리를 탐색할 때  두 번째 해시함숫값만큼 이동하는 방법입니다.

두 키의 첫 번째 해시값이 같더라도 두 번째 해시값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 이동하게 됩니다.

그러므로 2차 군집문제는 발생하지 않게 됩니다.

 

 

🔎 오픈 주소(선형 탐색) 법을 이용한 해시테이블 구현

public class OpenAddressingHashTable {
    public Slot[] hashTable;

    public OpenAddressingHashTable(Integer size){
        this.hashTable = new Slot[size]; //입력받은 크기만큼 해시 테이블 생성
    }

    public static class Slot{
        String key;
        String value;

        public Slot(String key, String value){
            this.key = key;
            this.value = value;
        }
    }

    //해시 함수
    public Integer hashFunction(String key){
        return (int)(key.charAt(0)) % hashTable.length;
    }

    //데이터 저장
    public void saveData(String key, String value){
        Integer index = hashFunction(key);

        if(hashTable[index] != null ) { // 해당 인덱스에 데이터가 존재한다면 (충돌)

            // open addressing 방법은 모든 key 가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없기 때문에
            // key값과 비교하여 확인 후 데이터를 저장해야 합니다. 
            if (hashTable[index].key.equals(key)) {
                hashTable[index].value = value;
                return;

            } else {
                Integer currentIndex = index + 1; // 다음 공간 탐색

                while (hashTable[currentIndex] != null) {
                    if (hashTable[currentIndex].key.equals(key)) {
                        hashTable[currentIndex].value = value;
                        return;
                    } else {
                        currentIndex++;
                        if (currentIndex >= hashTable.length) {
                            return;
                        }
                    }
                }
                hashTable[currentIndex] = new Slot(key, value);
                return;
            }
        } else {
            hashTable[index] = new Slot(key, value);
        }
        return;
    }

    public String getData(String key) {
        Integer index = hashFunction(key);

        if (hashTable[index] != null) {
            if (hashTable[index].key.equals(key)) {
                return hashTable[index].value;
            } else {
              Integer currentIndex = index + 1;

              while (hashTable[currentIndex] != null ){
                  if (hashTable[currentIndex].key.equals(key)) {
                      return hashTable[currentIndex].value;
                  } else {
                      currentIndex++;
                      if (currentIndex >= hashTable.length) {
                          return null;
                      }
                  }
              }
              return null;
            }

        } else {
            return null;
        }
    }


    public static void main(String[] args) {
        OpenAddressingHashTable cht = new OpenAddressingHashTable(10);
        cht.saveData("Jang", "01021213111");
        cht.saveData("Hong", "01034873497");

        System.out.println(cht.getData("Jang"));
    }
}

 

 

---

 

📚 Reference

쉽게 배우는 자료구조 with 자바 - 문병로,

https://kang-james.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9CHASH-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0