해시맵(HashMap)이란?
- 키(Key)와 값(value) 쌍을 저장하는 자료구조
- 각 키는 고유(unique)하며, 키를 사용하여 해당 값을 빠르게 검색 가능
해싱(Hashing)
- HashMap의 핵심 원리
- 키(Key)는 해싱 함수(Hashing Function)을 통해 정수값인 해시코드(HashCode)를 변환하고, 변환된 해시 코드는 Hash 배열의 각 요소인 '버킷(Bucket)'의 인덱스가 됨
해시맵(HashMap) 예시
각 배열의 요소를 버킷이라 함
정리
- 키(key)가 해시 함수에 의해 해시 코드로 변환되고 해당 해시코드는 배열의 각 요소인 버킷의 인덱스 역할
- 해당 버킷을 찾아가면 값을 삽입 및 조회 가능
HashMap의 특징
- 키 기반의 빠른 액세스 : 키를 사용하여 값을 빠르게 검색하거나 수정 가능
- 순서를 보장하지 않음 : HashMap은 내부적으로 Key가 삽입된 순서를 보장하지 않음
- 키의 중복 불가 : 키는 고유(Unique)하기 때문에 중복 불가, 이미 존재하는 키를 저장하면 기존 값(Value)가 덮어씌워짐
- null키와 값 : null키와 null 값을 저장 가능하지만 키는 중복되지 않기 때문에 null 키는 하나만 저장 가능
- 키 기반의 유연성 : 어떤 객체든 키로 사용 가능(Integer, String 이외에도 사용자 정의 클래스)
- 해싱 충돌 : 두 개 이상의 키가 동일한 해시 코드를 가질 때 충돌 발생 → 성능 저하를 초래
해싱 충돌 해결 방법
체이닝 (Chaining)
- 각 버킷을 연결리스트로 구현
- 충돌 발생 시 해당 버킷의 연결리스트에 새로운 키-값 쌍을 추가
- 구현이 간단하고 메모리 할당이 동적으로 이루어짐
개방 주소법 (Open Addressing)
- 모든 키-값 쌍이 해시 테이블의 배열 내에 직접 저장
- 충돌 발생 시 다른 버킷의 위치를 찾아 삽입을 시도
- 다른 위치를 찾는 과정에 대한 방법
- 선형 조사 (Linear Probing)
- 초기 위치에서 일정 간격으로 버킷을 조사하여 빈 위치 탐색
- 제곱 조사 (Quadratic Probing)
- 충돌 발생 시 제곱만큼 떨어진 위치 조사
- 이중 해싱(Double Hashing)
- 두 번째 해시 함수를 사용하여 버킷 위치 탐색
재해싱 (Rehashing)
- 해시 테이블이 가득 차거나 너무 많은 충돌 발생 시 해시 테이블의 크기를 늘리고 모든 키-값 쌍을 새로운 크기에 맞게 재 삽입
- 메모리 사용량을 늘리는 대신 충돌을 줄이고 성능을 향상시키는 데 효과적
버킷 확장(Bucket Expansion)
- 충돌 발생 시 해당 버킷의 크기를 확장하여 여러 키-값 쌍을 저장
커스텀 해시 함수 사용
- 데이터의 특성에 맞게 설계된 커스텀 해시 함수를 사용하여 충돌 최소화
HashMap 사용 상황
- 데이터의 순서가 중요하지 않고 키를 기반으로 빠른 데이터 액세스가 필요할 때 효과적
- 또한, 어떤 객체든 키로 사용할 수 있기에 이 점을 고려
해시 테이블 (Hash Table)이란?
- 일반적인 컴퓨터 과학의 자료구조 원칙
- 해시맵은 해시 테이블의 한 구현체로 Java에서 제공
- Hash-map이라는 용어는 자바말고도 다른 프로그래밍 언어나 라이브러이에서도 비슷한 구조나 개념을 나타내는 데 사용
(Python의 경우 'dict') - 언어마다 각각 제공하는 특징이나 동작 방식은 조금 다를 수 있음
- 따라서, 해시 테이블은 일반적인 자료 구조 원칙 또는 개념을 의미하며, 해시맵은 그 원칙을 구체적으로 구현한 특정 클래스나 자료구조를 의미
참고 자료
'Computer Science' 카테고리의 다른 글
| [알고리즘] 시간 복잡도와 공간 복잡도 (0) | 2024.11.05 |
|---|---|
| [알고리즘] 자주 사용하는 정렬 (0) | 2024.11.05 |
| [자료구조] 이진트리와 이진탐색트리 (0) | 2024.11.02 |
| [자료구조] Queue 개념 (0) | 2024.11.02 |
| [자료구조] Stack 개념 (0) | 2024.11.01 |
