해시 테이블과 해시 함수

최종 수정: 2025.06.04

해시 테이블과 해시 함수

해시 테이블은 빠른 검색이 필요한 거의 모든 곳에서 사용되는 핵심적인 자료구조이다. 특히 웹 개발에서는 객체, 딕셔너리, 맵 등의 형태로 일상적으로 사용한다.

---

■ 해시 테이블 (Hash Table)

해시 함수와 배열을 함께 사용하는 자료 구조이다. key를 인덱스로 사용하지 않고 해시 함수에 넣어 리턴된 값을 인덱스로 사용한다. 인덱스에 key와 value을 쌍으로 저장한다. 저장한 데이터를 가지고 올 때도 해시 함수를 통해 히턴된 값으로 인덱스에 접근한다.

// 해시 테이블의 개념적 구조
const hashTable = new Array(10); // 크기 10인 배열

// 저장 과정
function set(key, value) {
  const index = hash(key) % 10; // 해시 함수로 인덱스 계산
  hashTable[index] = [key, value]; // 해당 위치에 저장
}

// 검색 과정  
function get(key) {
  const index = hash(key) % 10; // 같은 해시 함수로 인덱스 계산
  return hashTable[index] ? hashTable[index][1] : null;
}

---

■ 해시 함수 (Hash Function)

임의의 크기의 데이터를 고정된 크기의 값(해시값)으로 반환하는 함수이다.

입력: "Hello World" → 해시함수 → 출력: 3c4e
입력: "안녕하세요" → 해시함수 → 출력: 7a2f
입력: 매우 긴 문서 → 해시함수 → 출력: b8d9

 

위의 예시처럼, 모든 출력이 동일한 길이로 나온다.

 

특징

• 결정성(Deterministic): 같은 입력에 대해서는 항상 같은 출력이 나온다.
• 균등 분포: 출력값이 가능한 범위에 고르게 분포된다.
• 빠른 계산: 해시값 계산이 매우 빠르다.
• 일방향성: 해시값으로부터 원본 데이터를 역추적하기 어렵다.

---

■ 해시 충돌 (Hash Collision)

서로 다른 키가 같은 해시값을 가지는 경우를 말한다.

 

해결 방법

1. 체이닝(Chanining)

// 같은 인덱스에 연결 리스트로 여러 값 저장
hashTable[3] = [
  ["apple", "사과"],
  ["grape", "포도"]  // 같은 인덱스에 체인으로 연결
];

 

2. 개방 주소법(Open Addressing)

// 충돌 시 다음 빈 공간을 찾아서 저장
function set(key, value) {
  let index = hash(key) % size;
  
  while (hashTable[index] !== null) {
    index = (index + 1) % size; // 다음 인덱스로 이동
  }
  
  hashTable[index] = [key, value];
}

---

■ 예시

// JavaScript 객체 (내부적으로 해시 테이블)
const person = {
  name: "김철수",    // 해시 테이블에 저장
  age: 25,
  city: "서울"
};

// Map 객체 (명시적인 해시 테이블)
const userMap = new Map();
userMap.set("user1", {name: "김철수", age: 25});
userMap.set("user2", {name: "이영희", age: 30});

console.log(userMap.get("user1")); // O(1) 시간에 검색

---

■ 활용

• 데이터베이스 인덱싱: 빠른 레코드 검색
• 캐싱: 자주 사용되는 데이터를 빠르게 접근
• 중복 제거: Set 자료 구조의 구현
• 패스워드 저장: 암호화된 해시값으로 저장
• 체크섬: 데이터 무결성 검증