해시

자료구조 알고리즘

해시

진호우 2025. 3. 25. 00:32

해시(Hash)란?

해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키(key) 값(value)을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 이다.

대표적인 구현 방식으로 해시 테이블(Hash Table)이 있으며, 해시 함수(Hash Function)를 사용하여 데이터를 저장할 위치를 결정한다.

해시의 특징

키-값(Key-Value) 저장 방식
데이터를 키(Key)와 값(Value) 형태로 저장하여 빠르게 검색할 수 있다.
빠른 검색 속도
평균적으로 O(1)(상수 시간) 만에 데이터를 조회할 수 있다.
해시 함수 사용
키를 특정한 해시 함수(Hash Function)를 통해 변환하여 저장할 위치를 결정한다.
해시 충돌(Collision) 해결 필요
서로 다른 키가 같은 해시 값으로 변환되는 경우가 발생할 수 있으며, 이를 해결하기 위한 기법이 필요하다.

해시 함수

자바스크립트에서는 오브젝트라는 자료형을 제공하는데, 이 자료형은 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있다.

해시 함수를 구현할 때 고려할 내용

해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다.
해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다. 충돌의 의미는 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미한다.

충돌 처리

위에서 처럼 해시 함수의 결괏값이 같으면 충돌이라고 한다. 하나의 버킷에 2개의 값을 넣을 수는 없으므로 해시 테이블을 관리할 때는 반드시 충돌 처리를 해야한다.

체이닝으로 처리하기

체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법이다. 체이닝은 춫ㅇ돌이 발생하면 해당 버킷에 연결 리스트로 같은 해시값을 가지는 데이터를 연결한다.

단점: 해시테이블 공간 활용성이 떨어짐, 검색 성능이 떨어짐

개방 주소법으로 처리하기

개방 주소법은 체이닝에서 연결 리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입한다. 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용한다.

이중 해싱 방식

이중 해싱 방식은 말 그대로 해시 함수를 2개 사용한다. 때에 따라 해시함수를 N개로 늘리기도 한다.

자바스크립트에서 해시 테이블 구현

자바스크립트의 Map 또는 객체(Object)를 사용하여 해시 테이블을 구현할 수 있다.

const hashTable = {};

// 데이터 추가
hashTable["name"] = "Alice";
hashTable["age"] = 25;
hashTable["city"] = "New York";

// 데이터 조회
console.log(hashTable["name"]); // Alice
console.log(hashTable["age"]); // 25

// 데이터 삭제
delete hashTable["city"];

console.log(hashTable); // { name: 'Alice', age: 25 }

자바스크립트의 객체는 기본적으로 해시 테이블처럼 동작하며, 키-값 쌍을 빠르게 저장하고 검색할 수 있다.

Map을 이용한 해시 테이블 구현

자바스크립트의 Map 객체는 해시 테이블을 보다 효율적으로 사용할 수 있도록 제공되는 내장 자료구조이다.

const hashMap = new Map();

// 데이터 추가
hashMap.set("name", "Alice");
hashMap.set("age", 25);
hashMap.set("city", "New York");

// 데이터 조회
console.log(hashMap.get("name")); // Alice
console.log(hashMap.get("age")); // 25

// 데이터 삭제
hashMap.delete("city");

console.log(hashMap); // Map(2) { 'name' => 'Alice', 'age' => 25 }

Map과 Object의 차이점

구분	Object	Map
키 유형	문자열만 가능	모든 데이터 타입 가능
순서 보장	X	O (입력 순서 유지)
성능	일반적으로 느림	최적화된 해시 테이블로 빠름
크기 확인	Object.keys(obj).length 필요	map.size 사용 가능

해시 테이블의 시간 복잡도

연산	평균 시간 복잡도	최악의 시간 복잡도 (충돌 발생 시)
삽입 (Insert)	O(1)	O(n)
조회 (Search)	O(1)	O(n)
삭제 (Delete)	O(1)	O(n)

평균적으로 해시 테이블의 연산은 O(1)(상수 시간) 안에 수행된다.
하지만 해시 충돌이 많아지면 O(n)(선형 시간)까지 성능이 저하될 수 있다.

해시 테이블의 활용 사례

캐싱(Cache) 시스템
- 웹 브라우저나 서버에서 자주 사용되는 데이터를 빠르게 조회하기 위해 사용
- 예: 로컬 스토리지(Local Storage), DNS 캐싱
데이터베이스 인덱싱
- 데이터베이스에서 데이터를 빠르게 검색하기 위해 해시 테이블을 이용한 인덱싱 기법을 사용
중복 검사(Duplicate Detection)
- 문자열, 배열 등에서 중복된 요소가 있는지 빠르게 검사할 때 사용
로그 분석 및 카운팅
- 특정 이벤트 발생 횟수(count)를 저장하고 빠르게 조회하는 데 활용
암호화 및 보안
- 비밀번호 저장 시 해시 함수를 사용하여 보안성을 높인다