[자료구조] Map과 Hash Table: 해시 함수와 해시 충돌의 해결, 해시 테이블 리사이징

반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

💋 Map ADT

✔️ 개념

• key-value 쌍을 저장한다.
• key는 중복되지 않는다.
• associative array, dictionary라고도 부른다.

 

✔️ 주요 동작

1. put(key, value): 지정된 키에 값을 연관시킵니다. 만약 이미 해당 키에 값이 존재한다면, 기존 값은 새로운 값으로 대체됩니다.
2. get(key): 지정된 키에 대응하는 값을 반환합니다. 만약 키가 존재하지 않으면 예외나 특별한 값을 반환할 수 있습니다.
3. remove(key): 지정된 키와 연관된 값을 제거합니다.
4. containsKey(key): 특정 키가 Map에 존재하는지 여부를 확인합니다.
5. containsValue(value): 특정 값이 Map 내에 하나 이상의 키에 의해 매핑되어 있는지 확인합니다.
6. size(): Map에 저장된 키-값 쌍의 개수를 반환합니다.
7. isEmpty(): Map이 비어있는지 여부를 반환합니다.
8. keys(): 모든 키를 반환합니다.
9. values(): 모든 값들을 반환합니다.
10. clear(): Map 내의 모든 키-값 쌍을 제거하여 비웁니다.

 

✔️ 구현

hash table과 tree-based로 크게 2가지 방식으로 구현할 수 있다.

이번 포스팅에서는 hash table에 대해 알아보자!

 

💋 Hash Table

✔️ 개념

• 배열과 해시 함수(hash function)을 사용해 map을 구현한 자료 구조
• (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠르다. ⇒ O(1)

 

✔️ Hash function이란?

 

• 입력된 키를 일정한 크기의 숫자로 매핑하는 함수
• 가능한 서로 다른 키들에 대해 다른 해시 값을 생성한다.
• 좋은 해시 함수는 해시 충돌을 최소화하고 데이터를 고르게 분산 시킬 수 있다. ⇒ 뒤에서 자세히 설명

 

 

• Hash Function의 input: 저장할 값의 key
• Hash Function의 output: Hash Table을 구현한 배열에서 해당 key, value를 저장할 인덱스

⇒ key를 Hash Function에 넣으면, 해당 키와 값을 저장할 배열의 인덱스를 반환한다.

 

✔️ 동작 방식

 

 

• insert
• 데이터를 저장하려는 키를 해시 함수에 적용하여 해시 값을 구한다. ⇒ 배열의 인덱스로 사용
• 계산된 해시 값에 해당하는 인덱스에 데이터를 저장한다.
• key, hash (삽입 당시에 계산한 해시값), value의 3가지 값이 저장된다.
• hash값은, 다시 해시 함수를 돌려서 계산하면 비효율적이어서 그냥 같이 저장한다고 한다.
• get
• 해시 함수를 사용하여 키의 해시 값을 계산해 인덱스로 이동해 저장된 데이터를 찾는다.

 

데이터를 저장할 인덱스를 버킷이나 슬롯이라고 부르기도 한다.

 

대략 아래와 같은 느낌으로 구현할 수 있다.

 

class HashTable:
	def __init__(self, size):
		self.size = size
		self.table = [None] * size

	def hash_function(self, key):
		return hash(key) % self.size

	def insert(self, key, value):
		index = self.hash_function(key)
		if self.table[index] is None:
			self.table[index] = [(key, value)]
		else:
			# Handle collision using chaining
			self.table[index].append((key, value))

	def get(self, key):
		index = self.hash_function(key)
		if self.table[index] is not None:
			# Search in the chain for the specified key
			for k, v in self.table[index]:
				if k == key:
					return v
		return None

 

💋 Hash Collision

✔️ 개념

해시 충돌은 서로 다른 데이터가 동일한 해시 값을 가지는 상황(key는 다른데, hash가 같을 때)이다.

해시 테이블의 크기는 제한되어 있기 때문에 현실적으로는 피할 수 없는 현상이다.

 

 

 

⇒ hash 충돌은 피할 수 없지만, 해시 함수의 결과 값이 골고루 분포되도록, 해시 충돌이 균등하게 발생하도록 해시 함수를 정하는 것이 좋다.

⇒ hash 충돌이 일어났을 때, 가장 효율적인 알고리즘을 통해서 충돌을 잘 해결하는 것이 중요하다!

 

✔️ hash collision의 해결 방법 - seperate chaining (체이닝)

• 개념
• 각 배열의 인덱스에 LinkedList를 사용하여 키들을 모아둔다.
• 충돌이 발생하면 연결 리스트에 노드를 추가한다.

 

해시 테이블:
----------------------------
0:  -> [Data1] -> [Data4] -> ...
1:  -> [Data2] -> ...
2:  -> [Data3] -> ...
3: 
4: 
5:  -> [Data5] -> ...
6: 
7:  -> [Data6] -> ...
8: 
9: 
----------------------------

 

• 과정
1. 해시 테이블 초기화
• 해시 테이블을 만들고, 각 인덱스에 빈 LinkedList를 할당한다.
2. 데이터 삽입
• 해당 데이터의 해시 값을 계산하고 그 해시 값을 인덱스로 하는 LinkedList에 데이터를 추가한다.
• 해당 인덱스에 다른 데이터가 이미 존재하는 경우에, 그냥 LinkedList의 다음 노드에 데이터를 추가한다.
3. 데이터 검색 또는 삭제
• 동일한 해시 함수로 해당 인덱스을 찾고, LinkedList에서 데이터를 검색하거나 삭제한다.
• 장점
• 구현이 간단하고 유연하다.
• 동적으로 크기를 조절하기 쉽다.
• 단점
• 메모리 사용이 비효율적일 수 있다. ⇒ 모든 인덱스에 LinkedList를 넣어놔야만 한다.
• 연결 리스트의 길이가 길어지면 검색 시간이 길어질 수 있다. ⇒ LinkedList의 탐색 시간 복잡도는 O(n)
• 참고: LinkedList 대신 트리를 사용하여 충돌을 해결할 수 있으며, 이로써 탐색 시간을 효율적으로 유지할 수 있다.

 

✔️ hash collision의 해결 방법 - open addressing (개방 주소법)

• 개념
• 충돌이 발생하면 다른 빈 버킷을 찾아 이동하거나 특정 규칙에 따라 다른 위치에 값을 저장한다.
• 해시 값을 통해 나온 인덱스가 아닌, 다른 인덱스에 데이터를 저장한다!
• 결국 하나의 인덱스에는 하나의 데이터만 저장된다.
• 대표적인 개방 주소법에는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다.
• 과정
1. 해시 테이블 초기화
• 해시 테이블을 만들고, 모든 버킷을 초기화한다.
2. 데이터 삽입
• 데이터를 삽입할 때, 해당 버킷이 비어있으면 데이터를 삽입
• 충돌이 발생하면 다른 방법을 사용하여 빈 버킷을 찾아 데이터를 삽입
3. 데이터 검색 또는 삭제
• 검색 또는 삭제 시에도 동일한 방법으로 데이터를 찾거나 삭제
• 장점
• 메모리 사용이 효율적이다. ⇒ 인덱스에 직접 데이터를 저장하므로 오버헤드(포인터를 저장해야한다던가,,,)가 없다!
• 캐시 효율이 높을 수 있다. ⇒ 데이터가 메모리에 연속적으로 저장되어 있어 캐시 라인(cache line) 활용이 쉽다!
• 단점
• 구현이 복잡할 수 있다. ⇒ 충돌 발생 시 어떤 인덱스에 데이터를 저장해야 할지 규칙을 정하기 어렵다.
• 선형 탐사 방식에는 특정 영역에 데이터가 몰리는 클러스터링(Clustering)이 발생해 성능 저하가 발생할 수 있다.

 

💋 Hash Table Resizing

데이터가 많이 차면, 해시 테이블의 크기를 늘려주어야 한다.

 

 

현재 8개의 버킷 중 6개가 차있다. 자바에서는 capacity의 3/4이 차게 되면 사이즈를 늘리게 된다.

 

 

1. 현재 데이터 이동
• 기존 해시 테이블의 데이터를 새로운 크기의 해시 테이블로 이동시킨다.
• 이동할 때에는 각 데이터의 해시 값을 다시 계산하지 않고, 이미 저장된 해시 값을 사용한다.
• 데이터를 해시 테이블에 넣고 나면, 그 다음에는 해시 함수를 또 굴려서 해시값을 얻어내는게 아니라, 해시값을 위의 96, 202처럼 함께 저장한다.
2. 새로운 해시 함수 사용
• 해시 테이블이 리사이징되면, 해시 함수의 결과가 이전과 다를 수 있다.
• 해시 테이블이 리사이징될 때는 새로운 해시 함수를 사용하여 데이터를 저장한다.
• 위의 경우에, 기존에는 해시 값을 8로 나눈 나머지를 인덱스로 활용하다가, 해시 테이블의 크기를 늘리면서 해시값을 16으로 나눈 나머지를 인덱스로 사용하게 되었다.
3. 크기 조절
• 일반적으로 해시 테이블의 크기를 2배로 늘리는 경우가 많다.
• 새로운 크기는 기존 크기의 2배인 소수(prime number)를 선택하는 것이 일반적이다.
• 소수를 선택함으로써 해시 함수의 결과가 균등하게 분포되도록 할 수 있습니다.
4. 재해시(Rehashing)
• 해시 테이블의 크기가 변경되었으므로, 모든 데이터를 새로운 크기에 맞게 다시 해싱한다.
5. 데이터 이동
• 재해시된 결과를 기반으로 데이터를 새로운 크기의 해시 테이블에 이동시킨다.

 

💋 프로그래밍 언어 별 Hash Table 구현

 

✔️ Python

• 파이썬에서는 내장된 dict 타입이 해시 테이블을 구현

 

pythonCopy code
# 해시 테이블 생성
my_dict = {}

# 데이터 추가
my_dict['key1'] = 'value1'

# 데이터 접근
print(my_dict['key1'])

 

✔️ Java

• 자바에서는 HashMap 클래스를 사용해서 해시 테이블을 구현

 

javaCopy code
// 해시 맵 생성
HashMap<String, String> myMap = new HashMap<>();

// 데이터 추가
myMap.put("key1", "value1");

// 데이터 접근
System.out.println(myMap.get("key1"));

 

✔️ C++

• C++에서는 std::unordered_map이 해시 테이블 구현

 

cppCopy code
// 해시 맵 생성
std::unordered_map<std::string, std::string> myMap;

// 데이터 추가
myMap["key1"] = "value1";

// 데이터 접근
std::cout << myMap["key1"] << std::endl;

 

✔️ JavaScript

• 자바스크립트에서는 객체(Object)가 해시 테이블의 역할을 하고, Map 객체도 사용

 

javascriptCopy code
// 객체 생성
let myObj = {};

// 데이터 추가
myObj['key1'] = 'value1';

// 데이터 접근
console.log(myObj['key1']);

 

 

 

python은 dictionary의 유효 데이터 수 x 3와 같거나 큰 수 중에서 가장 작은 2의 배수를 새로운 capacity 크기로 결정한다. (python 3.10.x 기준)

 

💋 참고자료

• https://www.geeksforgeeks.org/what-is-hashing/
• https://www.baeldung.com/cs/hashing-separate-chaining
• https://www.youtube.com/watch?v=ZBu_slSH5Sk&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=6
• https://www.youtube.com/watch?v=HraOg7W3VAM

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!