[자료구조] 해시(Hash)와 해시 테이블(Hash Table)

[자료구조] 해시(Hash)와 해시 테이블(Hash Table)

해시는 데이터 보안, 검색 최적화,, 암호화, 분산 시스템 등 다양한 분산 시스템에서 활용된다.

해시 테이블은 매일 사용하는 기술 속에 자리잡고 있지만, 그 원리에 대해 명확히 이해하고 있지 않은 것 같아서

해당 포스팅에서 해시에 대해 조금 더 자세히 알아보고자 한다.

해시(Hash)란?

해시(Hash)란 어떤 데이터를 일정한 길이의 고유한 값(해시 값)으로 변환하는 과정을 의미한다.

이때 사용되는 해시 함수(Hash Function)는 입력값을 특정한 규칙에 따라 변환하여, 짧고 고유한 숫자나 문자값(해시 값)으로 매핑하는 역할을 한다. 

해시의 특징은 다음과 같다.

• 고정된 길이 : 입력 크기에 관계없이 항상 동일한 길이의 해시 값을 반환한다.
• 빠른 연산 속도 : 해시 값 계산이 빠르게 이루어진다.
• 해시 충돌 가능성 : 서로 다른 입력값이 같은 해시 값을 가질 수 있다.

해시는 원본을 변환해서 값을 저장하여 보안을 강화하거나, 파일의 해시값을 비교하여 데이터의 무결성을 확인하는 등의 방법으로 활용할 수 있다.

해시는 데이터를 효율적으로 저장하고 검색하는데에도 활용이되는데, 대표적인 예가 해시 테이블(Hash Table)이다.

 

해시 테이블(Hash Table)이란?

해시 테이블은 키(Key)와 값(Value)을 저장하는 자료 구조로, 해시 함수를 사용하여 데이터를 빠르게 검색할 수 있도록 한다. 쉽게 말해, 키를 입력하면 즉시 해당 값에 접근할 수 있는 데이터 저장소라고 할 수 있다.

 

이름 (Key)	전화번호 (Value)
Alice	010-1234-5678
Bob	010-9876-5432

 

예를 들어, `Alice`라는 키를 사용해 전화번호를 저장하고, 나중에 `Alice`를 검색하면 해당 전화번호를 빠르게 찾아올 수 있다.

 

해시 테이블의 동작 방식

 

1. 키(Key)에 해시 함수를 적용해서 해시 값(Hash Value)를 생성한다.

2. 해시 값을 이용해서 해시 테이블의 특정 위치(Index)를 결정한다.

3. 해당 위치에 값(Value)를 저장한다.

4. 검색할 때도 같은 해시 함수를 사용하여 빠르게 데이터를 찾는다.

 

해시 충돌 (Hash Collision)

서로 다른 키가 같은 해시 값을 가질 경우 해시 충돌(Hash Collision)이 발생한다.

이를 해결하는 대표적인 방법으로 체이닝(Chaining) 방식과 개방주소법(Open Addressing) 방식이 있다.

 

체이닝(Chaining)

체이닝은 해시 충돌이 발생할 때, 동일한 해시 값을 가진 모든 요소를 연결 리스트(Linked List)로 저장하는 방식이다.

즉, 해시 테이블의 각 슬롯이 여러 개의 요소를 담을 수 있도록 구성된다.

 

개방주소법(Open Addressing)

개방 주소법은 해시 충돌이 발생할 때, 해시 테이블 내의 다른 빈 슬롯을 찾아 데이터를 저장하는 방식이다.

즉, 모든 데이터를 해시 테이블 자체 내에 저장하며, 별도의 구조를 사용하지 않는다.

 

해시 테이블의 장단점

✅ 장점

• 빠른 검색 속도 (O(1)) : 키를 해시 값으로 변환하여 즉시 데이터를 찾을 수 있다.
• 효율적인 데이터 저장 : 딕셔너리 형태로 데이터를 쉽게 저장할 수 있다.
• 중복 제거 가능 : 해시를 이용하면 데이터의 중복을 쉽게 감지할 수 있다.

❌ 단점

• 해시 충돌 발생 가능 : 두 개의 키가 같은 해시 값을 가질 수 있다.
• 메모리 사용량 증가 : 충분한 공간을 확보하지 않으면 성능이 저하될 수 있다.
• 정렬된 데이터 검색이 어려움 : 일반적인 배열이나 트리 구조보다 정렬된 데이터를 검색하는데 불리할 수 있다.