자료구조 / HashMap

---

HashMap 이란?

HashMap은 키(key)와 값(value)의 쌍으로 이루어진 데이터를 저장하는 자료구조이다. 키는 중복되지 않으며, 각 키는 하나의 값과 연결된다.

키(key)를 주면 해싱 함수에 의해 해시코드로 변환되고, 해당 해시코드는 배열의 각 요소인 버킷의 인덱스 역할을 한다. 해당 버킷을 찾아가면 값을 삽입 및 조회할 수 있다.

---

HashMap의 특징

1. 키를 사용하여 값을 빠르게 검색하거나 수정할 수 있다.

2. 'HashMap'은 내부적으로 키의 순서를 보장하지 않는다.

3. 같은 키를 중복해서 사용할 수 없다. 이미 존재하는 키에 대해 값을 저장하면 기존 값이 덮어씌워진다.

4. 'HashMap'은 null 키와 null 값을 저장할 수 있다. 하지만 키는 중복이 불가하므로 null 키는 하나만 저장될 수 있다.

5. 어떤 객체든 키로 사용할 수 있다.

6. 두 개 이상의 키가 동일한 해시 코드를 가질 때 충돌이 발생한다. 이는 성능 저하를 초래할 수 있다.

---

해싱 충돌 해결 방법

1) 체이닝 (Chaining)
	이 방법에서 각 버킷은 연결리스트로 구현된다.
	충돌이 발생하면, 해당 버킷의 연결리스트에 새로운 키-값 쌍을 추가한다.
	체이닝은 구현이 간단하고, 메모리 할당이 동적으로 이루어진다.

2) 개방 주소법 (Open Addressing)
	모든 키-값 쌍이 해시테이블의 배열 내에 직접 저장된다.
	충돌이 발생하면, 다른 버킷의 위치를 찾아 삽입을 시도한다.
	"다른 위치를 찾는" 과정은 또 여러 방법으로 나뉜다.

	- 선형 조사 (Linear Probing):
	초기 위치에서 일정 간격으로 버킷을 조사하여 빈 위치를 찾는다.
    
	- 제곱 조사 (Quadratic Probing):
	충돌 발생 시 제곱만큼 떨어진 위치를 조사한다.
    
	- 이중 해싱 (Double Hashing):
	두 번째 해시 함수를 사용하여 버킷 위치를 찾는다.
    
3) 재해싱 (Rehashing)
	해시 테이블이 가득 차거나 충돌이 너무 많이 발생할 경우, 해시 테이블의 크기를 늘리고 모든 키-값 쌍을 새로운 크기에 맞게 재삽입하는 방법.
	이 방법은 메모리 사용량을 늘리는 대신 충돌을 줄이고 성능을 향상시키는 데 효과적이다.

4) 버킷 확장 (Bucket Expansion)
	충돌이 일어나면 해당 버킷의 크기를 확장하여 여러 키-값 쌍을 저장할 수 있게 한다.

5) 커스텀 해시 함수 사용
	데이터의 특성에 맞게 설계된 커스텀 해시 함수를 사용하여 충돌을 최소화한다.
    

출처 : cchoijjinyoung.log

---

HashMap의 장점

• 빠른 조회 속도: 키를 사용하여 데이터를 상수 시간에 조회할 수 있어 대용량 데이터에서 효과적이다.

• 유연한 크기 조절: 크기를 동적으로 조절할 수 있어 데이터의 추가 및 삭제가 용이하다.

---

HashMap 사용 예시

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // HashMap 생성
        Map<String, Integer> myMap = new HashMap<>();

        // 1. 데이터 추가
        myMap.put("Apple", 100);
        myMap.put("Banana", 150);
        myMap.put("Orange", 120);

        // 2. 데이터 조회
        int applePrice = myMap.get("Apple");
        System.out.println("Price of Apple: " + applePrice);

        // 3. 데이터 수정
        myMap.put("Apple", 110);

        // 4. 데이터 삭제
        myMap.remove("Banana");

        // 5. 데이터 존재 여부 확인
        boolean containsOrange = myMap.containsKey("Orange");
        System.out.println("Contains Orange: " + containsOrange);

        // 6. 전체 데이터 순회
        System.out.println("All Entries:");
        for (Map.Entry<String, Integer> entry : myMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 7. 크기 확인
        int size = myMap.size();
        System.out.println("Map Size: " + size);

        // 8. 데이터 초기화
        myMap.clear();
        System.out.println("Map Cleared. Is Map Empty? " + myMap.isEmpty());
    }
}

---

HashMap 구현