자료구조란 데이터를 어떤 형식으로 저장하고 관리할지를 정해놓은 방식입니다. 쉽게 말하면 "이 데이터는 이렇게 담아두면 꺼내 쓸 때 훨씬 편하다"는 보관 방식이라고 볼 수 있습니다. 오늘은 그 중에서도 실무에서 가장 많이 쓰이는 자료구조 중 하나인 해시테이블을 알아보겠습니다.
해시테이블이란?
해시테이블(Hash Table)은 키(Key)와 값(Value)을 쌍으로 저장하는 자료구조입니다. 쉽게 말하면 "이 이름에 해당하는 정보는 여기 있다"는 식으로, 이름표를 달아서 데이터를 보관하는 방식입니다.
데이터를 저장할 때 키를 해시 함수(Hash Function)라는 수식에 넣어 특정 번호(인덱스)를 계산하고, 그 번호에 해당하는 버킷(Bucket)이라는 칸에 값을 넣습니다.
해시테이블을 배우는 이유
학교 사물함을 떠올려 봅시다. 내 사물함 번호를 모른다면 1번부터 끝 번호까지 하나씩 열어봐야 합니다. 하지만 내 이름을 넣으면 번호를 바로 알려주는 시스템이 있다면, 한 번에 내 사물함으로 찾아갈 수 있습니다.
이것이 해시테이블의 핵심입니다. 데이터가 100만 개여도 키만 알면 딱 한 번의 계산으로 위치를 찾아갑니다. 배열처럼 처음부터 하나씩 훑지 않아도 됩니다.
또한 JavaScript의 Object와 Map, Python의 dict, Java의 HashMap이 모두 내부적으로 해시테이블로 만들어져 있습니다. 개발하면서 자연스럽게 매일 쓰고 있는 구조이기 때문에 제대로 이해해두면 코드를 읽는 눈이 달라집니다.
핵심 개념
① 키(Key)와 값(Value)
해시테이블에 저장하는 데이터는 항상 키: 값 형태의 쌍입니다. 예를 들어 학생 성적표를 만든다면 "홍길동": 95 처럼, 이름이 키고 점수가 값이 됩니다. 키는 데이터를 찾을 때 사용하는 이름표 역할을 합니다.
② 해시 함수(Hash Function)
키를 넣으면 저장 위치(인덱스)를 알려주는 함수입니다. 같은 키를 넣으면 항상 같은 위치가 나와야 한다는 것이 핵심입니다. 이 일관성 덕분에 저장할 때와 꺼낼 때 모두 같은 위치를 계산할 수 있습니다.
③ 버킷 (Bucket)
실제로 데이터가 담기는 칸입니다. 해시테이블은 여러 개의 버킷으로 구성되어 있고, 해시 함수가 계산한 번호의 버킷에 데이터가 들어갑니다.
④ 해시 충돌(Hash Collision)
서로 다른 키가 해시 함수를 통해 같은 인덱스를 가리키는 경우입니다. 사물함 비유로 돌아가면, 두 명의 이름이 같은 사물함 번호로 계산되는 상황입니다. 이때는 주로 같은 칸에 데이터를 연결 리스트 형태로 이어 붙이는 방식으로 해결합니다.
해시 충돌은 어떤 해시 함수를 써도 완전히 없앨 수는 없습니다.
중요한 건 충돌을 최소화하는 좋은 해시 함수를 사용하고, 충돌이 나더라도 잘 처리하는 것입니다.
실습 ㅡ 동작 과정 따라가기
학생 이름과 점수를 저장하는 해시테이블을 만들어보겠습니다. 버킷이 5개(인덱스 0~4)이고, 해시 함수는 "이름 글자 수 % 5" 라고 가정합니다.
데이터 저장하기
"홍길동"(3글자) → 3 % 5 = 3 → 3번 버킷에 저장
"기상호"(3글자) → 3 % 5 = 3 → 3번 버킷에 저장 (충돌 발생! → 이어 붙임)
"성준수"(3글자) → 3 % 5 = 3 → 3번 버킷에 저장 (충돌 처리)
"최종수"(3글자) → 3 % 5 = 3 → 동일
위 예시는 단순한 설명용 해시 함수라 충돌이 많이 납니다. 실제로는 훨씬 정교한 해시 함수를 사용해서 충돌을 최소화 합니다.
데이터 찾기
"홍길동"의 점수를 찾고 싶다면 → 해시 함수에 "홍길동"을 넣어 3번 버킷으로 바로 이동 → 저장된 값 반환.
배열처럼 처음부터 하나씩 뒤지지 않아도 됩니다.
코드로 보기
// 간단한 해시테이블 구현 (JavaScript)
class HashTable {
constructor(size = 5) {
this.table = new Array(size); // 버킷 배열 생성
this.size = size;
}
// 해시 함수: 키를 숫자 인덱스로 변환
hash(key) {
let hash = 0;
for (let i = 0; i < key.lenght; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size; // 버킷 수로 나눈 나머지
}
// 데이터 저장
set(key, value) {
const index = this.hash(key);
if (!this.table[index]) {
this.table[index] = []; // 버킷 초기화
}
this.table[index].push([key, value]); // 충돌 시 이어 붙임
}
// 데이터 조회
get(key) {
const index = this.hash(key);
const bucket = this.table[index];
if (bucket) {
const item = bucket.find(pair => pair[0] === key);
return item ? item[1] : null;
}
return null;
}
}
const ht = new HashTable();
ht.set("홍길동", 95);
ht.set("기상호", 88);
console.log(ht.get("홍길동")); // 출력: 95
console.log(ht.get("기상호")); // 출력: 88
참고 ㅡ 배열(Array)과 비교하면
해시테이블이 왜 필요한지 더 잘 이해하려면 배열과 직접 비교해보는 게 좋습니다. 배열은 순서가 있어서 몇 번째 항목인지는 빠르게 알 수 있지만, "홍길의 점수"처럼 특정 이름으로 값을 찾으려면 처음부터 끝까지 하나씩 확인해야 합니다. 반면 해시테이블은 이름 자체가 위치를 결정하기 때문에, 데이터가 늘어나도 탐색 속도가 변하지 않습니다.
| 항목 | 배열 (선형 탐색) | 해시테이블 |
| 데이터 접근 방식 | 인덱스(번호)로 접근 | 키(이름표)로 접근 |
| 특정 값 탐색 | 처음부터 하나씩 확인 | 해시 함수로 위치 바로 계산 |
| 탐색 시간 복잡도 | O(n) | O(1) 평균 |
| 100만 개 탐색 시 | 최대 1,000,000번 | 평균 1~2번 |
| 언제 쓰는지? | 순서가 중요하거나 인덱스로 접근 할 때 | 키-값 쌍으로 빠른 검색이 필요할 때 |
O(1)은 평균값입니다. 해시 충돌이 심하게 발생하면 최악의 경우 O(n)까지 느려질 수 있습니다.
좋은 해시 함수를 쓰는 이유가 바로 여기에 있습니다.
마치며
해시테이블의 개념을 배우고 나면 단순히 "키-값을 빠르게 저장하고 꺼내는 방법"을 하나 익히는 것에서 그치지 않습니다. "어떤 키를 기준으로 데이터를 묶을 수 있을까?"라는 시각 자체가 생기기 시작합니다.
예를 들어 특정 값이 이미 나왔는지 O(1)로 바로 확인하거나, 데이터 목록에서 각 항목이 몇 번 등장하는지 한 번의 순회로 정리하는 것처럼, 해시테이블을 쓰면 구조 자체가 달라지는 문제들이 있습니다. 단순히 "빠른 탐색이 필요할 때 해시테이블을 써야지"가 아니라, "이 데이터에서 키로 삼을 수 있는 게 뭘까?"를 먼저 떠올릴 수 있게 되는 것이 진짜 목표입니다.
이것으로 해시테이블이 무엇인지, 왜 쓰는지, 어떻게 동작하는지까지 살펴보았습니다. 궁금한 점은 댓글 남겨주세요!