해시(Hash), 해시맵(HashMap), 해시셋(HashSet)

자료구조 키-값 쌍으로 저장되는 MAP과 데이터의 중복을 허용하지 않는 SET을 학습하려고 합니다.
두 자료구조 모두 Hash 알고리즘을 사용하기 때문에 HashMap과 HashSet으로 설명하고자 합니다.

해시 (Hash)

해시(Hash)는 데이터의 키(Key)를 해시 함수(Hash Function)에 넣어 고정된 크기의 해시 값(Hash Value) 또는 해시 코드(Hash Code)를 생성하는 과정입니다.. 즉 해시(Hash)는 입력된 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다.

Hash

위 그림에서 해시는 4가 됩니다.

 

해시의 구성 요소는 다음과 같습니다.

• Key : 데이터를 찾는데 사용하는 고유한 식별자로, 해시 함수에 입력되는 값입니다.
• Value : 해당 키에 연결된 실제 데이터로, 해시 테이블에 저장되는 값입니다.
• Hash Function : 주어진 키를 입력받아 고정된 크기의 해시 값을 출력하는 함수입니다.
• Hash Table : 생성된 해시 값을 기반으로 키-값 쌍으로 데이터를 저장하고, 효율적으로 데이터를 조회할 수 있도록 돕는 자료 구조입니다.

---

해시 함수 (Hash Function)

해시 함수는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수로, 동일한 입력에 대해서는 항상 같은 출력을 생성하지만, 출력값으로부터 원본 데이터를 역추적할 수 없는 특성을 가집니다.

Hash Function

위 그림처럼 해시 함수는 특정 값을 주면 해시 함수 알고리즘에 따라 고정된 데이터를 출력하는 함수입니다.

 

해시 함수의 예시로는 Division Method 즉 나눗셈을 이용하는 방식이 있습니다. 

 

---

해시 테이블 (Hash Table)

해시 함수의 결과로 생성된 해시 값은 데이터가 저장될 해시 테이블(Hash Table)의 인덱스로 사용되며, 이를 통해 데이터를 빠르게 검색하거나 저장할 수 있습니다.

 

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

해시 테이블(Hash Table)은 키와 값을 함께 저장한 자료구조입니다. 이는 행과 열로 구성된 표와 유사합니다.

INDEX	KEY	VALUE
0	A	100
1	B	200
2	C	300

 

인덱스를 활용해 저장하거나 검색하는데 실제 값이 저장되는 장소를 버킷(bucket) 또는 슬롯(slot)이라 합니다.

해시 테이블의 동작

put("A", 15)를 한다고 가정하겠습니다.

키는 A입니다. 해당 키를 해시 함수에 입력하면 해시값이 나옵니다. 여기서는 8로 나왔다라고 가정하면 해시 테이블은 인덱스가 3이니 8 % 3 = 2가 됩니다. 인덱스 2에 키-값을 저장합니다.

 

 

이번에는 get("A") 를 해보겠습니다.

찾으려는 키 A를 해시 함수에 입력하면 해시값이 출력됩니다. 8이 나왔다고 가정하면 8 % 3 = 2이므로 인덱스 2에서 저장된 키와 찾으려는 키가 맞는지 확인하고 값을 반환합니다.

---

해시 충돌(Hash Collision)

 % 연산을 사용해봤으면 알겠지만 같은 값이 나올 수 있습니다. 예를 들면 10과 100을 % 10 할 경우 같은 값이 나오게 되어있습니다. 이렇게 해시 함수가 서로 다른 두 개의 키를 동일한 해시값으로 매핑하는 것을 해시 충돌이라 합니다.

 

해시 충돌이란 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미합니다.

 

해시 충돌이 발생하는 원인은 무한한 가짓수의 입력값을 받아 유한한 가짓수의 츨력을 생성하기 때문에 무조건 발생하게 됩니다.

 

다음은 해시 충돌이 발생한 상황입니다.

A를 해시 함수로 해시 8이 나와 8 % 3 = 2로 인덱스 2번에 키-값을 저장한 상황에서 B를 해시 함수로 해시값으로 만들었더니 우연히 인덱스가 2가 나온 상황입니다.

 

 

해시 충돌의 해결 방법은 두 가지 정도로 하나는 같은 해시 값이 나오는 데이터를 연결 리스트 등의 구조로 저장하는 체이닝(Chaining)과 충돌이 발생하면 다른 빈 공간을 찾아 데이터를 저장하는 오픈 어드레싱(Open Addressing)이 있습니다.

 

체이닝(Chaining)

체이닝은 충돌 발생 시 그림과 같이 연결 리스트로 연결하는 방식입니다. A와 B가 충돌이 발생한 상황에서 A 다음 아이템이 B인 형태로 서로 연결 리스트로 연결합니다.

 

오픈 어드레싱(Open Addressing)

오픈 어드레싱은 충돌이 발생하면 그림처럼 탐사를 통해 빈 공간을 찾아나서는 방식입니다.이 방식은 체이닝 방식과 달리 전체 버킷(슬롯) 이상은 저장할 수 없고 빈 공간을 찾아 저장하기 때문에 모든 원소가 반드시 자신의 해시 값과 일치한 주소에 저장한다는 보장이 없습니다.

---

해시 셋(Hash Set)

Hash는 중복되지 않은 고유한 값을 저장하는 데이터 구조로 해시 테이블을 사용해 데이터를 관리합니다.

Set은 이미지처럼 중복된 데이터를 허용하지 않습니다. 

 

해시 테이블로 Set을 구현할 수 있습니다.

해시 테이블에서 값은 중복이 되지만 키는 중복되면 체이닝, 오픈 어드레싱 등의 충돌 해결 방법으로 중복을 피하는걸 이용하면 어떨끼?

 

이 처럼 해시 셋은 해시 테이블을 기반으로 셋을 구현한 것으로 값을 키로 사용하여 중복된 값을 허용하지 않는 방식입니다.

그림처럼 값은 필요가 없기 때문에 아무값을 넣고 키에 데이터를 넣어 중복을 허용하지 않는 방식입니다.

---

최종 수정일 : 2025-01-22