Computer Science/Algorithm, Data Structure

자바스크립트 자료구조 해시 테이블(Hash Table)

Write and Remember 2019. 5. 30. 20:23

 

2019/05/26 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 연결 리스트(Linked List)

 

자바스크립트 자료구조 연결 리스트(Linked List)

모든 자바스크립트 개발자가 알아야 하는 33가지 개념 지난 글에서 Stack과 Queue에 대해 알아보았고 오늘은 연결 리스트(Linked List)를 알아보자. 배열과 마찬가지로 연결 리스트는 데이터를 순차적으로 저장..

jeongw00.tistory.com

 

연결리스트에 이어서 Hash Table(해시 테이블)에 대해 알아보자.

 

출처: Wikipedia

 

해시 테이블은 키(key)를 값(value)에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다.

 

여기서 매핑이란 키(key) 역할을 하는 데이터와 값(value) 역할을 하는 데이터를

 

하나씩 짝지어 저장하는 데이터 구조다.

 

연관 배열(associative array)은 키 하나와 값 하나로 연관되어 있으며

 

키를 통해 연관되어 있는 값을 얻을 수 있다.

 

해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

 

여기서 해시 함수란

 

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

 

그런데 해시함수는 해쉬값의 개수보다 많은 키값을 해쉬값으로 변환하기 때문에

 

해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시 충돌이 일어난다.

 

출처: Wikipedia

 

해시 충돌을 최소화하는 방법은 여러 가지 있다.

 

Linear Probing(선형 검사)

 

Separate Chaining(분리 체이닝)

 

Coalesced Chaining(병합 체이닝)

 

Double Hashing(이중 해시)

 

Quadratic Probing(이차 검사)

 

분리 체이닝을 이용해 해시 충돌을 해결해보자.

 

출처: https://reactgo.com/hashtable-javascript/

 

class HashTable {
  // 기본 buckets size
  constructor(size) {
    this.buckets = new Array(size)
    this.size = size
  }

  // 해시 함수
  hash(key) {
    return key.toString().length % this.size;
  }

  // 해시 테이블에 새로운 데이터를 추가한다.
  set(key, value) {

    let index = this.hash(key);
	
    if (!this.buckets[index]) {
      this.buckets[index] = [];
    }

    this.buckets[index].push([key, value])
  }
  // key를 이용하여 데이터를 가져 온다.
  get(key) {

    let index = this.hash(key);
    if (!this.buckets[index]) return null
    // for of loop로 key와 일치하는 값 찾아내기
    for (let bucket of this.buckets[index]) {
      if (bucket[0] === key) {
        return bucket[1]
      }
    }
  }
}

const hashTable = new HashTable(10)

hashTable.set('userid1', 'example')
hashTable.set('userid2', 'say')
hashTable.set('userid3', 'other')
hashTable.set('userid4', 'sara')
hashTable.set('userid5', 'one')

hashTable.get('userid1') // example
hashTable.get('userid2') // say
hashTable.get('userid3') // other
hashTable.get('userid4') // sara
hashTable.get('userid5') // one

 

해시 함수의 예:

 

h(k) = k % m, 

 

key(하나의 자연수로 해석)를 테이블의 크기로 나눈 나머지는 0 ~ m-1 사이의 정수가 된다.

 

해시 테이블 이해하기 좋은 포프님 영상