[javascript] 해시 테이블 (Hash Table) 데이터 구조

08 Dec 2023

javascript

해시 테이블은 효율적인 데이터 저장과 검색을 위한 자료 구조입니다. 이 자료 구조는 키-값 쌍을 저장하고 특정 키를 사용하여 효율적으로 값을 가져올 수 있습니다.

해시 함수 (Hash Function)

해시 테이블은 해시 함수를 사용하여 데이터를 저장하고 검색합니다. 해시 함수는 입력값으로부터 고유한 해시 코드를 생성합니다. 이 고유한 코드를 사용하여 값을 저장하거나 검색하는 데에 사용됩니다.

function hashFunction(key, size) {
  let hashCode = 0;
  for (let i = 0; i < key.length; i++) {
    hashCode += key.charCodeAt(i);
  }
  return hashCode % size;
}

해시 함수는 키가 같으면 항상 같은 해시 코드를 반환해야 합니다. 이는 충돌을 방지하기 위해 중요합니다.

충돌 해결 (Collision Resolution)

가장 일반적인 충돌 해결 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다. 체이닝은 각 버킷에 연결 리스트를 유지하는 방식이며, 개방 주소법은 충돌이 발생하면 다른 빈 버킷을 찾는 방식입니다.

// 체이닝 방식
class HashTable {
  constructor() {
    this.size = 10;
    this.buckets = new Array(10);
    for (let i = 0; i < this.size; i++) {
      this.buckets[i] = [];
    }
  }

  insert(key, value) {
    let index = hashFunction(key, this.size);
    this.buckets[index].push({key, value});
  }

  search(key) {
    let index = hashFunction(key, this.size);
    for (let item of this.buckets[index]) {
      if (item.key === key) {
        return item.value;
      }
    }
    return null;
  }
}

해시 테이블의 성능

해시 테이블의 성능은 해시 함수, 충돌 해결 방법, 그리고 테이블의 크기에 따라 달라집니다. 잘 설계된 해시 함수와 충돌 해결 방법은 해시 테이블의 성능을 향상시킬 수 있습니다.

해시 테이블은 O(1)의 시간 복잡도로 값을 검색할 수 있는 뛰어난 성능을 보여줍니다. 따라서 많은 상황에서 데이터 검색에 사용됩니다.

결론

해시 테이블은 키-값 쌍을 효율적으로 저장하고 검색할 수 있는 자료 구조입니다. 잘 설계된 해시 함수와 충돌 해결 방법은 해시 테이블의 효율성을 높일 수 있습니다.

참고:

https://en.wikipedia.org/wiki/Hash_table
https://www.geeksforgeeks.org/hashing-set-1-introduction/