해시 테이블(Hash Table)은 키-값(key-value) 쌍으로 데이터를 저장하는 자료구조 중 하나이다. 각각의 데이터는 해시 함수(Hash Function)를 사용하여 키(key)로 변환된 인덱스에 해당하는 버킷(Bucket)에 저장된다. 해시 함수는 키의 고유한 값(Hash Code)을 이용하여 해당 키가 저장될 위치를 계산하는 함수이다.

해시 테이블에서 탐색을 할 때, 먼저 탐색할 데이터의 키를 해시 함수에 넣어 해당 버킷의 인덱스를 계산한다. 이후 해당 인덱스에 저장된 값과 찾고자 하는 값이 일치하는지를 확인하여 탐색을 수행한다.

해시 테이블을 사용하는 이유는 일반적인 배열에 비해 상수 시간 안에 탐색, 삽입, 삭제 연산을 수행할 수 있기 때문이다. 하지만, 해시 충돌(Collision)이 발생할 수 있는데, 이 경우에는 다른 키의 데이터와 충돌하지 않도록 하기 위한 해시 충돌 해결(Collision Resolution) 기법을 사용해야 한다.

주로, 대용량 데이터를 빠르게 탐색하고자 할 때 유용합니다.

해시 충돌 해결 기법

해시 충돌 해결 기법에는 크게 두 가지가 있다.

1. 개방 주소(Open Addressing)

   개방 주소(Open Addressing) 방식은 충돌이 발생하면, 다른 버킷에 빈 공간이 있는지를 확인하고 비어있는 버킷에 데이터를 저장하는 방식이다. 선형 조사(Linear Probing), 이차원 조사(Quadratic Probing), 이중 해시(Double Hashing) 등의 방식이 있다.

2. 체이닝(Chaining)

   체이닝(Chaining) 방식은 각 버킷에 연결 리스트를 생성하여 충돌이 발생하면, 해당 버킷의 연결 리스트에 데이터를 추가하는 방식이다.

구현 방법

자바스크립트에서는 객체(Object)를 이용하여 해시 테이블을 구현할 수 있다. 객체의 프로퍼티 이름이 키(key)에 해당하며, 해당 프로퍼티의 값이 데이터(value)에 해당한다.