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

해시 테이블(Hash Table)은 실무에서 필수적인 자료 구조이며 자주 사용되는 자료 구조 중 하나이다.
이뿐만 아니라 다른 자료 구조에 비해 월등히 빠른 속도를 가진다.

 

해싱(Hashing)

아래의 이미지는 해시 함수를 통해 키가 해시 값으로 변환되는 과정을 도식화한 것이다. 이러한 일련의 과정을 해싱이라고 한다. 

 

위의 이미지는 'John Smith'라는 문자열을 해시 함수를 통해 '01'이라는 새로운 해시 값으로 변환했다. 그리고 01에 들어 있는 값인 521-8976을 찾았다.

해싱이란 임의의 크기의 데이터를 해시 함수를 사용하여 고정된 크기의 값으로 변환하는 작업이다.

 

해시 함수(Hash Function)

해시 테이블에서 가장 중요한 것을 꼽으라면 해시 함수라고 할 수 있다.

 

그렇다면 해시 함수는 무엇일까?

 

해시 함수란 임의의 길이를 갖는 데이터(Key)를 고정된 길이의 데이터(Hash Value)로 매핑하는 데 사용되는 함수다.

여기서 전자는 입력 데이터를, 후자는 매핑된 데이터다. 즉, 원래의 데이터를 키(Key), 매핑 후의 데이터 값을 해시 값(Hash Value)이라고 한다.

 

 

해시 함수는 키를 해시 값으로 인코딩하는 함수이다.

 

좋은 해시 함수의 조건은 아래와 같다.

• 해시 값 충돌 최소화
• 사용할 키의 모든 정보를 이용하여 해싱
• 쉽고 빠른 연산

 

해시 충돌(Hash Collision)

해시 충돌이란 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써 생기는 문제이다.

 

아무리 좋은 함수를 사용하더라도 해시 충돌은 피할 수 없는 경우가 다반사다. 왜냐하면 해시 함수의 입력 값은 무한하지만 출력 값은 유한하기 때문이다.(비둘기집 원리) 그렇기 때문에 해시 충돌을 최소화하는 것이 더 효율적일 것이다.

 

해시 충돌 해결 방법

개별 체이닝 기법(Separate Chaining)

개별 체이닝 기법은 충돌 발생 시 연결 리스트(Linked List)를 추가하는 방식이다.

 

위의 그림에서 152번 인덱스에 'John Smith'와 'Sandra Dee'가 충돌되었다. 이때 'John Smith' 뒤에 'Sandra Dee' 를 연결함으로써 충돌을 처리하였다.

 

연결된 방식을 살펴보면 연결 리스트의 형식과 유사한 것을 볼 수 있다.

 

2024.08.23 - [CS] - [자료구조] 선형(Linear) 자료구조의 종류와 특징

[자료구조] 선형(Linear) 자료구조의 종류와 특징

 

개방 주소법 기법(Open Addressing)

개방 주소법 기법은 저장해야 하는 인덱스에 이미 존재하는 값이 있으면 다른 인덱스에 저장하는 방식이다. 즉, 해시 함수로 얻은 주소가 아닌 다른 주소 공간에 저장한다.

 

위의 그림에서 152번 인덱스에 'John Smith'와 'Sandra Dee'가 충돌되었다. 이때 'John Smith' 를 152번 인덱스에 'Sandra Dee' 를 그다음 비어 있는 153번 인덱스에 연결함으로써 충돌을 처리하였다.

 

비어 있는 인덱스를 찾아 삽입하는 기법에는 크게 3가지가 있다.

• 선형탐사(Linear Probing): 인접한 인덱스에 데이터를 삽입
• 제곱탐사(Quadratic Probing): 말 그대로 제곱하는 방식(1², 2², 3²...)으로 비어 있는 인덱스를 탐사
• 이중해싱(Double Hashing): 다른 해시 함수를 한 번 더 적용하는 방식

해시 테이블(Hash Table)

해시 테이블이란 해시 함수를 사용하여 변환된 값(Hash Value)을 색인(Index)을 기준으로 키(Key)와 값(Value)을 저장하는 자료 구조이다. 즉, 해싱을 통해 변환된 데이터가 저장되는 곳이다.

해시 테이블의 가장 큰 장점은 다른 자료 구조보다 빠르게 원하는 데이터를 찾을 수 있다는 점이다. 특정 데이터를 검색할 때 시간 복잡도가 O(1)로 나타난다.(단, 해시 충돌이 없는 경우)

해시 테이블은 무한에 가까운 데이터(Key)를 유한한 개수의 해시 값으로 매핑한 테이블이다.