[자료구조] 맵(Map)과 해시 테이블(Hash Table) 🫢

오늘은 자료구조 맵(Map)과 해시테이블(Hash Table)에 대해 알아보겠습니다.

Map이란

Map은 키(Key)와 값(value)으로 저장하는 자료구조이다. 각 키는 중복이 될 수 없으면 키를 이용하여 해당 값을 빠르게 찾을 수 있다.

 

해싱(Hashing)

해싱 함수는 키(Key)를 받아서 정수값인 해시코드(HashCode)를 반환하고 반환된 해시코드는 값이 저장되는 버킷의 인덱스가 된다.

Hash Table이란?

배열과 해시 함수를 사용하여 map을 구현한 자료구조

 

 

위의 그림과 같이 k1이라는 키(Key)를 해싱함수에 넣으면 해시코드를 반환하고 그 해시코드를 인덱스로 버킷을 만들어서 저장을 한다.

 

구조

• 키(Key) : 고유한 값. 해시 함수의 input이 된다.
• 값(value) : 저장소에 최종적으로 저장되는 값으로 키와 매칭되어서 저장, 삭제, 검색 등이 가능하다.
• 해시 함수(Hash Function) : 키(Key)를 해시(Hash)하는 역할을 한다. 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시코드로 변경하여 키와 값이 저장되는 버킷의 인덱스 역할을 한다. 하지만 서로 다른 키가 같은 해시코드를 가지는 경우를 해시 충돌이라고 하는데, 이런 해시 충돌 상황을 최소화하면서 해시 함수를 만드는 것이 중요하다.
• 해시 (Hash) : 해시 함수(Hash Function)의 결과물이며, 버킷에서 키와 값과 함께 저장되면 인덱스로 사용된다.

특징

• 키 기반의 빠른 인덱스 : 키를 이용해서 값을 빠르게 검색하거나 수정할 수 있다.
• 순서를 보장하지 않음 : HashMap은 내부적으로 키의 순서를 보장하지 않는다.
• 키 중복 불가 : 키를 중복해서 사용할 수 없다. 이미 있는 키에 대한 값을 저장하면 값이 덮어씌워진다.
• null 가능 : HashMap에서는 키와 값에 모두 null이 들어갈 수 있다. 키는 중복이 불가능하기에 null 키는 하나만 저장 가능하다.
• 해싱 충돌 : 두 개 이상의 키가 동일한 해시코드를 가지는 상황이 발생할 수 있다. 이는 성능 저하를 초래한다.

해싱출돌이라는 말이 이해가 안 될 수 있다. 해싱 함수는 키를 받아서 작업을 처리하고 해시코드를 반환한다. 이 과정에서 같은 해시코드를 반환할 수 있다. 해싱 충돌을 처리하기 위한 다양한 방법이 있다.

 

해싱 출동 해결방법

1) 체이닝 (Chaning)

이 방법은 연결리스트로 구현된다. 만약 해시코드가 같아서 충돌이 일어날 거 같으면 해당 버킷의 연결리스트로 키와 값의 쌍을 추가한다.

체이닝은 이렇게 그냥 기존 버킷에 연결리스트만 추가하면 됨으로 간단하게 구현된다.

 

2) 개발 주소법(Open Addressing)

모든 키-값 쌍이 해시테이블 배열 내에 직접 저장된다.

충돌이 바생하면, 다른 버킷의 위치를 찾아 삽입을 시도한다.

 

3) 재해싱 (Refreshing)

해시 테이블이 가득 차거나 충돌이 너무 많이 발생하는 경우, 해시 테이블의 크기를 늘리고 키-값 쌍을 새로운 크기에 맞게 다시 삽입하는 방법. 이 방법은 메모리를 늘리는 대신 충돌을 줄이고 성능을 향상하는데 효과적이다.

 

언제 사용 ?

데이터의 순서가 중요하지 않고, 키를 기반으로 빠른 액세스 데이터가 필요할 때 사용하면 좋다.