자료구조 3. Hash Table

HashTable (with Linked List)

1. Hash Table

  해시 테이블은 키와 값의 쌍을 저장하는 구조이다. 예를 들어 전화번호부에서 이름(Key)을 통해 전화번호(Value)를 알아낼 수 있는 것처럼 키를 이용하여 값을 얻어낼 수 있다. 해시 테이블은 다음과 같은 구성을 갖고 있다.

 

 1) Key

   Key는 데이터 저장/탐색을 위한 고유의 값(identifier)이다. 데이터 저장 시 Key는 해시 함수에 입력되어 Data가 해시 테이블의 저장소 어느 곳에 저장될 것인지를 결정한다. 

 

 2) Hash Function

   해시 함수는 키를 해시로 변환하는 함수이다. 여러가지 값을 갖고 있는 키를 일정한 형식을 갖도록 변환함으로써 저장소를 관리한다. 예를 들어 해시 테이블의 저장소가 2칸(bucket) 이라면 hash function이 fn(){ return %2 }라 정의하고 Key가 홀수인 경우 저장소의 1번 칸에, 짝수인 경우는 0번 칸에 저장하도록 구조를 만들 수 있을 것이다. 이 때 Key가 11, 20, 21이 들어왔다면 11과 21은 해시 함수 에 의해 1이라는 같은 값을 갖게 된다. 이 경우 두 값은 어떻게 저장될까?

 3) bucket

4*3 Hash Table

   버킷은 테이블의 크기이자 키를 입력받는 해시 함수의 결과 범위이다. 위 그림에서 bucket은 갈색으로 칠해진 부분을 의미하며 그림의 bucket의 크기는 4이고 범위는 0~3이다.

 

 4) slot

   슬롯은 한 개의 버킷에 저장될 키 값의 개수이다. 위 그림에서 slot의 크기는 3이다. 이전 예시에서 hash function이 %2일 때 key가 11, 21모두 같은 0번 bucket에 저장해야 한다고 했다. 이 때 slot이 2라면 0번 버킷의 1번 slot에는 11, 2번 slot에는 21을 저장할 수 있을 것이다. 즉, 해시 테이블의 전체 저장공간은 버킷의 수 * 슬롯의 수가 된다. 위 그림의 해시 테이블 전체 저장공간은 12칸 이다. 만약 슬롯이 연결 리스트라면 연결 리스트는 저장공간을 동적을 할당 가능하므로 해시 테이블의 전체 저장공간을 유동적으로 할당 및 사용 가능하다.

 

2. 기억장소 활용률

  기억장소 활용률이란 해시테이블 전체 기억장소에 데이터가 담겨있는 비율이다. 조사에 의하면 식별자 밀도(Identifier density), 부하율, 적재 밀도(Load factor, Loading density)라는 단어들과 혼용되서 사용되는 것으로 보인다. 기억장소 활용률은 슬롯이 배열인 경우는 '저장된 데이터수 / (슬롯의 수 * 버킷의 수)', 슬롯이 연결리스트 등 공간이 동적할당되는 경우는 '저장된 데이터 수 / 버킷의 수' 로 계산된다. 

  해시 테이블은 기억장소의 활용률에 따라 성능에 차이가 있다. 일반적으로 기억장소 활용률이 25~75% 일 때 가장 성능이 좋으며, 해시 테이블에 데이터 입력/삭제가 발생할 때 기억장소 활용률을 계산하여 25~75% 범위를 벗어나면 해시 테이블의 크기를 리사이징 하기도 한다.

 

 

3. 해시함수

 1) 좋은 해시함수의 조건

   해시함수는 Key를 해시 테이블의 버킷주소로 변환(Hashing)하는 역할을 한다. 해시 테이블의 버킷은 한정적이기 때문에 해시함수는 최대한 각각의 키들이 각자 다른 값으로 변환되어 같은 버킷에 여러 키가 몰리는 충돌이 발생하지 않아야 한다. 즉, 버킷이 8개가 있다면 각 버킷이 Key에 대응될 확률이 모두 동일하게 1/8 씩 차지하는 것이 좋은 것이다. 이러한 함수를 균등 해시 함수(uniform hash function)라고 한다.

 

 2) 해시함수의 기법

   대표적인 해시함수의 기법은 중간제곱법(mid-squre method), 나눗셈법(division method), 숫자분석법(digit analysis method), 접지법(folding method) 등이 있다.

 

4. 충돌과 오버플로우

 1) 충돌과 오버플로우 발생이유

   해시 테이블에서 충돌이란 서로다른 키가 같은 버킷에 해시되는 경우를 의미한다. 이 때 해당 버킷의 슬롯이 충분하다면 저장이 모두 가능하고, 충분하지 않으면 오버플로우가 발생한다. 이러한 충돌과 오버플로우를 해결하기 위한 방법은 크게 Chaining과 Open Addressing이 있다.

 

 2) Chaining

   체이닝은 슬롯을 연결리스트와 같이 공간의 제한이 없는 구조를 사용하여 같은 버킷을 해시되는 데이터들을 모두 저장하는 방법이다.

 

 3) Open Addressing

   개방 주소법은 충돌발생 시 해시 테이블 영역 내의 다른 빈 공간을 찾아 저장하는 방식이다. 대표적으로 선형조사법이 있다.

 

   3-1) Linear Probing

Linear Probing

    선형 조사법이란 해시 테이블을 1차원 배열로 보고 충돌 발생 시 가까운 빈 슬롯에 저장하는 것이다. 위 그림은 Key1, Key2, Key3이 모두 0번 버킷에 해싱된 상황이다. Key들을 순서대로 해싱하였을 때 Key3을 해싱하는 경우 0번 버킷의 슬롯이 모두 차있으므로 충돌이 발생한다. 선형 조사법에서는 Key3를 버킷 0과 가까운 버킷 1의 슬롯에 저장한다.

 

 

Linear Probing

     선형 조사법의 경우 충돌 시 가까운 빈 슬롯에 데이터를 저장하므로 사용되는 버킷이 한 구역으로 밀집(Primary Clustering)되는 경향이 있다. 예를 들어 슬롯이 1, 해시함수가 %10 이고 숫자 1, 11, 3, 4, 5, 13 라는 키가 순서대로 해시된다 생각해보자. 이 경우 11에서 충돌이 발생하여 버킷 1 대신 2에 저장된다. 그 후 13일 때 버킷 3에서 충돌이 발생하여 버킷 4가 비었는지 해당 버킷에도 이미 데이터가 존재하므로 버킷 5으로 밀린다. 버킷 5도 데이터가 들어있으므로 버킷 6에 13이 저장된다. 여기서 44라는 키를 해시해보자. 원래는 버킷 4에 들어가야 하지만 충돌이 발생하고 선형 조사법에 의해 7번 슬롯에 들어가게 된다. 즉, 선형 조사법에 의해 충돌을 해결한 경우 바로 다음 슬롯에 값을 넣으며, 바로 다음 슬롯에 넣은 값에 이해 다시 충돌이 발생하고 바로 다음 슬롯에 값을 넣는다가 계속 반복되게 된다. 따라서 사용되는 버킷이 특정 구간에 군집화 되며 검색 시간 또한 증가한다. 이러한 단점을 극복하기 위해 이차 조사법(quadratic probing), 재해싱 등의 기법이 등장하였다. 

 

3. 구현

  구현 코드는 다음과 같다. 

class HashTable {
  constructor(bucketNum = 8) {
    this._size = 0;
    this._bucketNum = bucketNum;
    this._storage = LimitedArray(this._bucketNum);
  }

  insert(key, value) {
    const index = hashFunction(key, this._bucketNum);
    const tuple = [key, value];

    if (this._storage.get(index) === undefined) {
      this._storage.set(index, new TupleLinkedList());
      this._storage.get(index).addToTail(tuple);
      this._size++;
    } else {
      let findNode = this._storage.get(index).keyOf(key);
      if (findNode === null) {
        this._storage.get(index).addToTail(tuple);
        this._size++;
      } else {
        findNode.value[1] = value;
      }
    }
    //resize
    if (this._size > this._bucketNum * 0.75) {
      this._resize(this._bucketNum * 2);
    }
  }

  retrieve(key) {
    const index = hashFunction(key, this._bucketNum);
    if (this._storage.get(index) === undefined || this._storage.get(index).contains(key) === false) {
      return undefined;
    } else {
      return this._storage.get(index).keyOf(key).value[1];
    }
  }

  remove(key) {
    let result = undefined;
    const index = hashFunction(key, this._bucketNum);
    let findNode = this._storage.get(index).keyOf(key);

    if (findNode !== null) {
      result = findNode.value[1];
      this._storage.get(index).remove(findNode.value);
      this._size--;
    }

    //resize
    if (this._size < this._bucketNum * 0.25) {
      this._resize(this._bucketNum / 2);
    }
    return result;
  }

  _resize(newBucketNum) {
    const newHashTable = new HashTable(newBucketNum);
    this._storage.each(function (linkedlist) {
      if (linkedlist !== undefined && linkedlist.size() > 0) {
        let node = linkedlist.head;
        while (node !== null) {
          newHashTable.insert(...node.value)
          node = node.next;
        }
      }
    })

    this._bucketNum = newBucketNum;
    this._storage = newHashTable._storage;
  }
}

  Tuple LinkedList는 연결 리스트 게시물의 코드에서 LinkedList를 상속받은 클래스이다. 코드는 다음과 같다.

class TupleLinkedList extends LinkedList {
    constructor() {
        super();
    }
    
    contains(key) {
        let node = this.head;
        while (node !== null) {
            if (node.value[0] === key) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    indexOf(key) {
        let node = this.head;
        let idx = 0;
        while (node !== null) {
            if (node.value[0] === key) {
                return idx;
            }
            node = node.next;
            idx++;
        }
        return -1;
    }

    keyOf(key) {
        let node = this.head;
        while (node !== null) {
            if (node.value[0] === key) {
                return node;
            }
            node = node.next;
        }
        return null;
    }
}

 

---

참고 사이트

Hash table - Wikipedia