목록으로

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

약 2분 읽기스터디#Development댓글로 이동

CS 스터디

main
date
Oct 29, 2023
slug
data-structure-hash-table
author
status
Public
tags
Development
summary
CS 스터디
type
Post
thumbnail
category
스터디
updatedAt
Apr 14, 2026 09:44 PM
Key, Value 로 데이터를 저장하는 자료구조
빠르게 데이터를 검색할 수 있는 자료구조이다.
빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
해시 테이블의 평균 시간복잡도는 O(1)
해시 테이블은 각각의 Key 값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용하여 값을 저장하거나 검색하게 된다.
notion image
자바스크립트 HashTable 구현하기
classHashTable {
  table =new Array(16);
constructor() {}

// key와 value를 받아 해시 테이블에 저장한다.
  setItem = (key, value) => {
    table[key] = value;
  };

// key를 통해 value를 가져온다.
  getItem = (key) => {
return "";
  };
}
16 칸 짜리 HashTable class를 생성하였고 배열에 값을 설정하는 setItem 메서드를 생성하였다.
HashTable의 배열에 접근하기위해서는 인덱스로 접근해야한다. 위에 선언한것 처럼 String 타입을 key로 사용할 수 없다.
그렇기 때문에 String 값을 number 형태로 바꾸어 number index에 데이터가 저장 되도록 해야한다.
이렇게 자료형을 변환하여 저장시켜주는 함수를 hash function 이라고 한다.
굳이 해시 함수를 사용하여 배열에 값을 할당하는 이유
classHashTable {
  table =new Array(71);
constructor() {}

// key와 value를 받아 해시 테이블에 저장한다.
  setItem = (key, value) => {
// table[key] = value;const index = this.hashToIndex(key);
    this.table[index] = value;
  };

// key를 통해 value를 가져온다.
  getItem = (key) => {
const idx = this.hashToIndex(key);
return this.table[idx];
  };

// 문자열을 받아 인덱스로 변호나
  hashToIndex = (key) => {
let hash = 17;
for (let i = 0; i < key.length; i++) {
      hash = (13 * hash * key.charCodeAt(i)) % this.table.length;
    }
return hash;
  };
}
해시 함수를 작성하는 방법 중 하나는 key로 들어오는 문자열을 charCode로 변환한 값을 사용한다.
const hashTable =new HashTable();

hashTable.setItem("firstName", "jeon");
hashTable.setItem("lastName", "dahoon");

console.log(`성은 ? ${hashTable.getItem("firstName")}`);
console.log(`이름은 ? ${hashTable.getItem("lastName")}`);
notion image