[자료구조] 해시테이블(Hash Table)

Web Development/자료구조

[자료구조] 해시테이블(Hash Table)

devflate 2024. 5. 1. 22:33

무엇인가?

해시 테이블은 키/값 쌍 데이터를 저장하는 데 사용되는 데이터 구조이다.

해시 테이블은 해시 함수를 이용하여, index를 설정하고, 그 내부에 데이터를 저장한다.
해시 테이블을 사용하면 O(1)의 성능으로 데이터를 참조, 수정, 삭제할 수 있다.

왜 사용하는가?

장점
- 효율적인 데이터 검색 및 관리
해시 함수를 통해서 계산된 인덱스를 사용하여 데이터를 O(1)의 시간 복잡도를 가지고 참조, 수정, 삭제가 가능하다.
- 데이터 중복 방지
키의 유일성을 통해 중복 데이터 삽입을 방지할 수 있다.
- 동적 크기 조정
데이터의 양에 따라 해시 테이블의 크기를 동적으로 조정할 수 있어, 자원의 효율적인 사용이 가능하다.
단점
- 해시 충돌
두 개 이상의 키가 동일한 해시 값을 가질 경우, 충돌이 발생하고, 이는 데이터 접근 속도를 저하시킬 수 있다.
- 메모리 낭비
충돌을 관리하기 위한 추가적인 자료 구조가 필요하거나, 해시 테이블이 과도하게 클 경우, 빈 공간이 많이 생길 수 있다.
- 해시 함수 의존성
해시 함수의 성능이 해시테이블 전체의 성능에 큰 영향을 미친다.
- 순서 유지 불가
해시테이블은 데이터의 순서를 유지하지 않기 때문에, 순서가 중요한 경우, 다른 자료 구조를 사용하는 것이 좋다.

해시함수

해시테이블에서 중요한 것은 해시함수의 효율성이다.

해시함수의 요구사항

- 계산하기 쉬워야 한다.
- 해시 테이블 전체에 균일한 분포를 제공해야 한다. 클러스터링이 발생하면 안된다.
- 충돌 감소 : 요소 쌍이 동일한 해시 값에 매핑될 때 충돌이 발생한다. 이러한 충돌은 피해야 한다.

충돌해결 방법

해시테이블을 사용하다보면, 해시 함수가 도출한 인덱스가 동일하게 나오는 경우가 발생한다.
이 때 데이터 간, 충돌이 발생할 수 있다. 이를 해결하기 위한 기술들은 아래와 같다.

Seperate chaining (Open hashing)
가장 흔히 사용되는 충돌 해결 방법이다. 연결리스트를 이용하여 주로 구현된다. 해시테이블 내의 각각의 인덱스에 대응하는 연결리스트들을 만든 후, 데이터를 연결리스트에 삽입한다. 만약 같은 인덱스에 들어가는 데이터가 있다면, 같은 연결리스트에 삽입한다.
이 방법을 사용했을 때, 해시된 키의 분포가 균일하다면, 조회 기능의 평균 비용은 연결 목록당 평균 키 수에만 의존한다.

Linear Probing(Open addressing)
Hash 충돌에 대한 해결방법 중 하나로, 추가적인 공간을 사용하지 않는 Open Addressing 방법 중의 하나이다.

충돌이 발생한 경우, 이미 채워진 공간이 아니라 비어있는 공간이 나올 때 까지 인덱스를 증가시키며 탐색하는 방식이다.
따라서 구현이 쉽지만, 충돌이 발생한 구간에서는 계속 충돌이 발생하는 문제가 있다.

Quadratic Probing(Open addressing)

Quadratic Probing은 Linear Probing 방식과 비슷하지만, 충돌이 발생할 경우, 다음 빈 공간(슬롯 사이의 간격)을

원래 해시된 인덱스에 임의의 다항식의 연속 값을 추가하여 계산하여 적용한다는 특징이 있다.

Double hashing
Double hashing은 Linear Probing 방식과 비슷하지만, 충돌이 발생할 경우, 다음 빈 공간(슬롯 사이의 간격)을 2개의 해시함수를 계산하여 적용한다는 특징이 있다.

자바스크립트 코드로 해시테이블(Hash Table) 만들어보기
이전 글 [자료구조] - 양방향연결리스트, https://steadyg.tistory.com/37 에서 만들었던, DoublyLinkedList를 통해서,
Hash Table을 만들어보았다.

import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class HashData {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}

class HashTable {
  constructor() {
    this.arr = [];
    for (let i = 0; i < 10; i++) {
      this.arr[i] = new DoublyLinkedList();
    }
  }

  hashFunction(number) {
    return number % 10;
  }

  set(key, value) {
    try {
      if (this.get(key) === null) {
        this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
      } else {
        throw new Error('이미 값이 존재합니다.');
      }
    } catch (e) {
      console.log(e);
    }
  }

  get(key) {
    let currentNode = this.arr[this.hashFunction(key)].head;
    while (currentNode != null) {
      if (currentNode.data.key == key) {
        return currentNode.data.value;
      }
      currentNode = currentNode.next;
    }
    return null;
  }

  remove(key) {
    const list = this.arr[this.hashFunction(key)];
    let currentNode = list.head;
    let deletedIndex = 0;

    while (currentNode != null) {
      if (currentNode.data.key == key) {
        return list.deleteAt(deletedIndex);
      }
      currentNode = currentNode.next;
      deletedIndex++;
    }
    return null;
  }
}

export { HashTable };

- https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/
- https://www.geeksforgeeks.org/hash-table-data-structure/
- https://jicoding.tistory.com/67
- https://yusang.tistory.com/114
- ChatGPT
- https://velog.io/@edie_ko/hashtable-with-js