What is HashMap ?

• HashMap은 자바의 java.util 패키지에 포함된 자료구조로, Map 인터페이스를 구현한 클래스
• HashMap은 키(key) - 값(value) 쌍을 저장하는 데 사용되며, 각 키는 유일(unique)해야 함
• 이 자료구조는 해시 테이블을 사용하여 데이터를 저장하고, 키를 통해 빠르게 값을 조회할 수 있게 해줌

HashMap의 특징

특징	설명
키-값 쌍	각 요소는 키와 값으로 구성된 쌍입니다. 키를 사용하여 해당 값에 접근할 수 있습니다.
해시 테이블 기반	내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장합니다. 키의 해시 코드를 사용하여 배열의 적절한 위치에 저장합니다.
빠른 조회	키의 해시 코드를 사용하여 상수 시간(O(1)) 내에 값을 조회할 수 있습니다. 해시 충돌 시 최악의 경우 O(n)이 될 수 있습니다.
순서 없음	HashMap에 저장된 요소들은 순서를 가지지 않습니다. 요소들이 추가된 순서를 보장하지 않습니다.
null 값	키로 하나의 null 값을 허용하며, 값으로 여러 개의 null 값을 허용합니다.
동기화되지 않음	HashMap은 동기화되지 않으므로 멀티 스레드 환경에서는 외부 동기화가 필요합니다. Collections.synchronizedMap() 또는 ConcurrentHashMap을 사용할 수 있습니다.

hash function?

• 어떤 데이터를 받아 고정된 크기의 값을 반환하는 함수
  👉🏻 key를 배열 크기 내의 인덱스로 바꿔주는 함수
• 이 반환값은 일반적으로 해시 코드 또는 해시 값이라고 불림

hash function의 특징

특징	설명
고정된 크기의 출력	입력 데이터의 크기와 상관없이, 항상 고정된 크기의 해시 코드를 생성
효율적인 계산	빠르게 계산될 수 있어야 함
결정적(deterministic)	동일한 입력에 대해 항상 동일한 출력을 반환해야 함
균일한 분포	해시 테이블 전체에 걸쳐 키를 균일하게 분포시켜야 함
충돌 최소화	서로 다른 입력에 대해 가능한 한 다른 출력을 생성해야 함, 충돌 발생 시 효율적으로 처리 필요
빠른 키 검색	키의 해시 코드를 사용하여 빠른 검색이 가능해야 함

❗️ HashMap의 key는 가능한 값이 거의 무한대에 가까우나, hash값 (hash code)은 int 타입의 고정된 범위로 나타낼 수 있는데, 이러한 상황에서 HashMap은 어떻게 충돌을 관리하고 효율적으로 데이터를 저장할까?

현상

HashMap에서 키의 가능한 값은 거의 무한대에 가까울 수 있으나, 해시 코드는 int타입으로 표현되는 고정된 범위를 가짐, 이로 인해 서로 다른 키가 동일한 해시 코드를 가질 수 있는 충돌이 발생할 수 있음. 이는 비둘기집 원리(PigeonHole principle)에 의해 발생하는 현상으로 제한된 수의 해시 코드로 무한대에 가까운 수의 키를 매핑해야 하는 상황에서 불가피하게 나타남

비둘기집 원리란?

n개의 비둘기집에 n+1마리 이상의 비둘기를 넣어야 한다면, 적어도 한 개의 비둘기집에는 두 마리 이상의 비둘기가 있어야한다는 것

충돌 관리책

HashMap은 이러한 충돌을 관리하기 위해 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)같은 기법을 사용함.
체이닝 방법 : 각 해시 버킷에 연결 리스트(Linked list)를 사용하여 여러 키-값 쌍을 저장할 수 있음
동일한 해시 코드를 가진 여러 키들이 하나의 리스트에 저장되고, 충돌이 발생하면 해당 리스트에 새 항목이 추가됨.
오픈 어드레싱 : 모든 키-값 쌍을 해시 테이블의 배열 자체에 직접 저장하고, 충돌이 발생할 경우 다른 버킷을 찾아 저장함. 대표적인 방법으로는 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 이중 해싱(Double Hashing)등이 있음

Separate Chaining

Open Addressing - Linear probing

Open Addressing - Quadratic probing

Open Addressing - Double Hashing

Open Addressing 주의점

• 중간 연결고리 역할을 하는 key의 삭세 시, 이미 있는 값도 없다고 판단할 수 있음

해결책

• 삭제 시 DELETE 같은 상싱적인 형태로 표시
  • DELETE 표시를 보고 다음 위치도 확인해봐야함을 알 수 있음
  • 단점 : DELETE를 만나면 무조건 다음 위치를 확인해야 함
• 삭제 위치 다음의 open addressing된 key들은 한 단계씩 앞으로 옮겨줌
  • 단점 : 이동시키는 추가적인 비용 발생

Java에서는 해시 충돌을 어떻게 해결했을까?

• jdk7까지는 linked list를 사용한 separate chaining을 활용
• jdk8에서 linked list와 red black tree를 혼용한 separate chaining을 활용