해시 맵 (해시 테이블)

• 해시 테이블이라고도 불림
• Key-Value 쌍으로 데이터를 저장하는 자료구조
• 내부적으로는 배열을 사용
• 해시 함수를 통해 키를 배열의 인덱스로 변환하여 데이터를 저장하고 검색

구성 요소

1. 키(Key)와 값(Value)

• 키(Key): 저장된 데이터를 고유하게 식별하는 값이다. 중복이 허용되지 않는다.

• 값(Value): 키에 연결되어 저장되는 실제 데이터다. 값은 중복될 수 있다.

해시맵은 이 키와 값의 쌍(Key-Value Pair)을 하나의 단위(Entry 또는 Node)로 저장한다.

2. 해시 함수 (Hash Function)

키(Key)를 입력받아 정수 형태의 **해시 코드(Hash Code)**를 생성하는 함수

3. 버킷 (Bucket) 또는 슬롯 (Slot)

해시 함수에 의해 계산된 해시 코드가 가리키는, 데이터가 실질적으로 저장되는 공간

내부적으로는 배열의 각 칸으로 생각할 수 있으며, 버킷의 인덱스는 해시 코드를 배열의 크기로 나눈 나머지 값 등으로 결정된다.

핵심 동작 원리

1. 저장: put('key', 'value')

   • key를 해시 함수에 넣는다. hash('key') -> 5
   • 해시 함수가 반환한 숫자 5를 인덱스로 삼아, 내부 배열의 5번 칸에 value를 저장
   • 만약 기존의 5번 칸에 이미 값이 저장되어 있었다면 새로운 값으로 대체된다.

2. 검색: get('key')

   • key를 저장할 때와 똑같은 해시 함수에 넣는다. hash('key') -> 5
   • 내부 배열의 5번 칸으로 바로 찾아가서 값을 꺼내온다.

해시 함수

• 임의의 길이의 데이터를 고정된 길이의 문자열로 변환하는 함수
• 해시 맵에서는 저장하거나 검색하려는 데이터의 '키(Key)'를 입력받아, 해당 데이터가 저장될 위치를 나타내는 숫자 '인덱스(Index)'로 변환하는 역할

쉬운 비유

거대한 도서관에서 책을 찾는다고 가정한다.

책 제목(key)를 사서(해시 함수)에게 말하면, 사서는 제목(key)를 바탕으로 "A-12-3" 같은 위치 번호(Index)를 즉시 계산하고 그곳으로 안내한다.

좋은 해시 함수의 조건

해시 테이블의 성능은 해시 함수에 크게 좌우되므로, 좋은 해시 함수는 다음과 같은 조건을 만족해야 한다.

• 효율성: 해시 값을 계산하는 과정이 빨라야 한다. 해시 함수 자체가 복잡하고 오래 걸린다면 해시 테이블의 장점인 속도를 살릴 수 없다.

• 분포의 균일성: 키 값들이 배열의 특정 위치에 몰리지 않고, 인덱스 공간 전체에 최대한 고르게 분산되어야 한다. 이는 '해시 충돌'을 최소화하는 데 매우 중요하다.

• 결정론성: 동일한 키에 대해서는 항상 동일한 해시 값(인덱스)이 나와야 한다. 이 특성 덕분에 언제든지 키를 통해 저장된 값을 다시 찾아갈 수 있다.

해시 충돌과 해결법

해시 충돌? e.g.) 만약 'key1'과 'key2'가 해시 함수를 거쳤더니 둘 다 같은 인덱스를 반환하는 현상

분리 연결법

• 내부 배열의 각 칸(버킷)에 값을 하나만 저장하는 대신, 연결 리스트를 하나씩 두는 것
• 충돌이 발생하면, 해당 인덱스의 연결 리스트에 새로운 노드를 추가해 데이터를 저장한다

예시

'lisa'와 'john'이 같은 인덱스 1로 해싱된 경우

Buckets (Array)
[0] -> null
[1] -> [key: 'lisa', val: 25] -> [key: 'john', val: 30] -> null // 연결 리스트 노드 추가
[2] -> [key: 'sandra', val: 28] -> null
...