728x90
1. 해시맵
해시맵이란 데이터 키와 값이 쌍으로 구성되어있는 자료구조입니다. 주로 데이터를 빠르게 검색하거나 저장할때 사용되며 내부적으로 해시함수를 이용해 저장할 인덱스를 계산합니다.
해시함수란 임의 길이의 입력(문자열, 객체 등)을 고정 길이의 값(해시값, 해시 코드)으로 매핑하는 함수입니다
예를 들어 살펴보겠습니다.
아래와 같은 자료가 있다고 생각해보겠습니다.
| Key | Value |
| cat | 10 |
| dog | 20 |
| fox | 30 |
| bird | 40 |
| frog | 50 |
이를 해시 인덱스로 변환하는 건 아래와 같습니다. (무조건 이런방식으로 계산되는 것은 아닙니다.)
| Key | 각 문자의 아스키 코드 변환 | 아스키코드의 합(sum) | 해시 인덱스 (Sum % 8) |
| cat | c(99) + a(97) + t(116) | 312 | 0 |
| dog | d(100) + o(111) + g(103) | 314 | 2 |
| fox | f(102) + o(111) + x(120) | 333 | 5 |
| bird | b(98)+i(105)+r(114)+d(100) | 417 | 1 |
| frog | f(102)+r(114)+o(111)+g(103) | 430 | 6 |
이렇게 되면 아래처럼 데이터가 저장되게 됩니다.
| Index | Key & Value |
| 0 | ("cat", 10) |
| 1 | ("bird", 40) |
| 2 | ("dog", 20) |
| 3 | |
| 4 | |
| 5 | ("fox", 30) |
| 6 | ("frog", 50) |
| 7 |
이렇게 해시인덱스가 계산되기때문에 같은 인덱스에 다른 Key도 들어올 수 있습니다. 이를 해결하기 위해 아래와 같은 방법이 사용됩니다.
1) 체이닝 방식
체이닝 방식에서는 같은 인덱스에 요소가 있다면 연결리스트 방식으로 복수로 저장합니다. 즉 첫번째 요소에는 다음 요소의 주소가 들어가는 것입니다.
체이닝 방식은 충돌이 많아도 각 슬롯에 여러 항목을 저장할 수 있어 해시맵 전체가 꽉 차는 문제가 발생하지않는다는 장점이 있습니다. 다만 슬롯내에서 리스트 탐색이 필요하므로 충돌이 많아질수록 검색 성능이 저하된다는 단점이 있습니다.
자바의 내장함수인 해시맵이 체이닝 방식을 사용합니다.
이를 자바와 파이썬 코드로 확인해보겠습니다.
class HashMap:
def __init__(self, size=5):
self.size = size # 데이터가 저장될 슬롯의 수
self.table = [[] for _ in range(size)] ## 사이즈만큼의 내부 리스트가 만들어짐 -> 내부 리스트를 엔트리라고 지칭
def _hash(self, key):
return hash(key) % self.size # hash() : 문자열을 특정 정수값으로 바꾸는 함수
def put(self, key, value):
index = self._hash(key)
for pair in self.table[index]: # 테이블안에 같은 이름의 키를 가진 엔트리가 있는지 탐색
if pair[0] == key: # 추가할 엔트리와 같은 키를 가진 요소가 있을 경우
pair[1] = value # 해당 엔트리의 값을 변경
return
self.table[index].append([key, value]) # 키가 중복되지않으면 새 엔트리 추가
def get(self, key):
index = self._hash(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
return None
def remove(self, key):
index = self._hash(key)
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
return
hm = HashMap()
hm.put("apple", 10)
hm.put("banana", 20)
hm.put("apple", 30)
print(hm.get("apple")) # 30
hm.remove("banana")
print(hm.get("banana")) # None
자바
import java.util.*;
public class HashMapChaining {
private static class Entry {
String key;
int value;
Entry(String key, int value) {
this.key = key;
this.value = value;
}
}
private List<Entry>[] table;
private int size;
@SuppressWarnings("unchecked") // 제네릭 배열을 생성할때 발생하는 형 변환 경고 무시
public HashMapChaining(int size) {
this.size = size;
table = new LinkedList[size];
for (int i = 0; i < size; i++) {
table[i] = new LinkedList<>();
}
}
private int hash(String key) {
return Math.abs(key.hashCode()) % size;
}
public void put(String key, int value) {
int index = hash(key);
for (Entry e : table[index]) {
if (e.key.equals(key)) {
e.value = value; // Update
return;
}
}
table[index].add(new Entry(key, value)); // Insert
}
public Integer get(String key) {
int index = hash(key);
for (Entry e : table[index]) {
if (e.key.equals(key)) {
return e.value;
}
}
return null;
}
public void remove(String key) {
int index = hash(key);
Iterator<Entry> it = table[index].iterator();
while (it.hasNext()) {
if (it.next().key.equals(key)) {
it.remove();
return;
}
}
}
public static void main(String[] args) {
HashMapChaining hm = new HashMapChaining(5);
hm.put("apple", 10);
hm.put("banana", 20);
hm.put("apple", 30);
System.out.println(hm.get("apple")); // 30
hm.remove("banana");
System.out.println(hm.get("banana")); // null
}
}2) 오픈 어드레싱
오픈 어드레싱 방식은 같은 해시 인덱스에 중복된 키가 발생한다면 다른 빈자리를 찾아 삽입하는 방식입니다.
즉, 같은 해시 인덱스에 요소가 들어있다면 다음 해시 인덱스 중 비어있는 가장 첫번째 인덱스에 요소를 삽입합니다.
오픈 어드레싱 방식은 모든 데이터가 배열내에 저장되기 때문에 메모리 접근이 빠르고 캐시 효율이 높다는 장점이 있습니다.
반면에 테이블이 꽉 차면 삽입이 불가능하고 삭제처리와 재해싱 관리가 복잡해진다는 단점이 있습니다.
파이썬의 기본자료구조인 딕셔너리가 오픈 어드레싱 방식의 해시테이블을 사용합니다.
이를 파이썬과 자바코드로 확인해보겠습니다
class HashMap:
def __init__(self, size=8):
self.size = size
self.table = [None] * size # 오픈 어드레싱에서는 중첩리스트를 사용하지않음
self.DELETED = ("<deleted>", None)
# 엔트리가 삭제된 자리임을 표시하기 위함
# 원래 비어있던 자리와 구분하기 위함
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self._hash(key)
for i in range(self.size):
idx = (index + i) % self.size
entry = self.table[idx]
if entry is None or entry == self.DELETED:
self.table[idx] = (key, value)
return
if entry[0] == key:
self.table[idx] = (key, value)
return
def get(self, key):
index = self._hash(key)
for i in range(self.size):
idx = (index + i) % self.size
entry = self.table[idx]
if entry is None:
return None
if entry != self.DELETED and entry[0] == key:
return entry[1]
return None
def remove(self, key):
index = self._hash(key)
for i in range(self.size):
idx = (index + i) % self.size
entry = self.table[idx]
if entry is None:
return
if entry != self.DELETED and entry[0] == key:
self.table[idx] = self.DELETED
return
hm = HashMap()
hm.put("apple", 10)
hm.put("banana", 20)
hm.put("apple", 30)
print(hm.get("apple")) # 30
hm.remove("banana")
print(hm.get("banana")) # None
자바
public class HashMapOpenAddressing {
private static class Entry {
String key;
int value;
Entry(String key, int value) {
this.key = key;
this.value = value;
}
}
private Entry[] table;
private int size;
private final Entry DELETED = new Entry("<deleted>", 0);
public HashMapOpenAddressing(int size) {
this.size = size;
table = new Entry[size];
}
private int hash(String key) {
return Math.abs(key.hashCode()) % size;
}
public void put(String key, int value) {
int index = hash(key);
for (int i = 0; i < size; i++) {
int idx = (index + i) % size;
Entry entry = table[idx];
if (entry == null || entry == DELETED) {
table[idx] = new Entry(key, value);
return;
}
if (entry.key.equals(key)) {
entry.value = value;
return;
}
}
}
public Integer get(String key) {
int index = hash(key);
for (int i = 0; i < size; i++) {
int idx = (index + i) % size;
Entry entry = table[idx];
if (entry == null) return null;
if (entry != DELETED && entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
public void remove(String key) {
int index = hash(key);
for (int i = 0; i < size; i++) {
int idx = (index + i) % size;
Entry entry = table[idx];
if (entry == null) return;
if (entry != DELETED && entry.key.equals(key)) {
table[idx] = DELETED;
return;
}
}
}
public static void main(String[] args) {
HashMapOpenAddressing hm = new HashMapOpenAddressing(8);
hm.put("apple", 10);
hm.put("banana", 20);
hm.put("apple", 30);
System.out.println(hm.get("apple")); // 30
hm.remove("banana");
System.out.println(hm.get("banana")); // null
}
}2. 해시맵의 성능
해시맵의 시간복잡도는 평균 O(1)이지만 체이닝방식이든 오픈 어드레싱 방식이든 충돌이 많을 경우 탐색 시간이 추가로 계속 발생되게 되어 최악의 시간복잡도는 O(n)이 됩니다. 또한 해시맵이 저장될 공간이 추가로 필요하므로 공간복잡도는 O(n)이 됩니다.
'CS(Computer Science) 이론 > 자료구조' 카테고리의 다른 글
| [자료구조] 힙(heap) (0) | 2025.09.11 |
|---|---|
| [자료구조] 트리 (0) | 2025.09.07 |
| [자료구조] 큐(QUEUE) (0) | 2025.09.07 |
| [자료구조] 스택 (0) | 2025.09.06 |
| [자료구조] 연결리스트 (0) | 2025.09.04 |