Map이란?

• Map
  • 키(Key)와 값(Value)이 쌍으로 이루어진 자료구조
    • 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고, Key를 통해 Value를 얻는다.
    • 다순히 순서를 표현하는 인덱스와 달리, Map의 Key는 개발자가 의미를 부여할 수 있다.
  • 값(Value)은 중복될 수 있지만, Key는 고유한 값을 가져야 한다.
    • 만일 기존에 저장된 데이터와 중복된 키와 값을 저장하면, 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.
  • 저장 순서가 유지되지 않는다.

HashMap이란?

📌 요약

• HashMap의 기본 구조: 배열 + 연결 리스트 + 트리
  • 해시 함수를 이용해 Key의 해시값을 기반으로 특정 인덱스(bucket)에 저장
  • 같은 해시값을 가진 Key가 여러 개 존재하면 연결 리스트(Linked List)로 연결
  • 자바 8부터는 일정 개수 이상 충돌이 발생하면 연결 리스트 -> 트리(Tree)로 변환하여 성능을 최적화.

해싱(Hashing)

Java에서 Map은 인터페이스이고, 그런 Map의 구현체 중 하나가 HashMap이다.

데이터를 저장하려면 자료구조가 필요한데, HashMap은 자료구조로 배열(array)을 사용한다.
HashMap은 해싱(Hashing)을 통해 Map 데이터가 저장될 위치의 인덱스를 구한다. (그래서 이름이 HashMap이다)

hey(x)를 해싱함수(function)에 넣어 인덱스(Y)를 산출한 후, 해당 인덱스에 Map 데이터를 저장하는 것이 HashMap의 기본 원리이다.

• 해싱(Hasing)이란?
  • 해싱(Hasing)은 데이터를 저장하거나 검색하기 위해 키(key)를 고정된 크기의 해시코드(hashCode)로 변환하는 과정이다.
  • 이 해시코드를 이용해 데이터를 저장할 배열 인덱스(index)를 결정한다.
• 해시 함수(Hash Function)란?
  • 해시 함수는 키를 입력받아서 정수형 해시코드를 출력하는 함수이다.
  • Java에서는 Object 클래스의 hashCode() 메서드가 기본 해시 함수 역할을 한다.

해싱의 조건

해싱은 인덱스를 구하는 것이다. 따라서 아래의 조건을 준수해야 한다.

1. hasing의 결과는 정수여야 한다.
   • key를 매개변수로 받은 hash함수는 key의 해쉬코드와 key의해쉬코드를 오른쪽으로 16비트 shift한 결과를 ^(xor) 연산한 값을 반환한다. 이는 정수(int)이다.
   • 
2. hasing의 결과는 배열의 크기를 넘어서면 안 된다.
   • 인덱스 i에 (n-1) & hash의 결과를 넣어주는데, 이 식은 hash % n과 같은 결과를 나타낸다.
   • hash에 나머지 연산을 실행하므로, 그 결과는 배열의 크기인 n보다 작은 정수가 인덱스가 된다.
   • 

해싱의 장점

이처럼 HashMap은 key가 있다면 해싱함수를 통해 바로 해당 인덱스의 위치로 이동할 수 있다.
key를 통해 인덱스 산출 후 데이터에 접근한다면, 시간복잡도는 O(1)이 된다.
즉, 데이터 접근 성능이 매우 뛰어나다.

Node

HashMap 내부의 배열을 버킷(bucket)이라고 부른다.
버킷 안에 저장된 Map 데이터를 자바에서는 Node 객체로 만들어 관리한다.

HashMap 클래스안에 Node 배열을 table이란 이름으로 관리하는 필드를 확인할 수 있다. 이 table이 버킷이다.

버킷안에 저장된 Node객체를 확인할 수 있다.
필드로 hash값, key, value, 그리고 next값을 알 수있다.

충돌 (Collision)

해시를 사용하다보면 서로 다른 key가 동일한 인덱스를 부여받는 충돌(collision)이 발생할 수 있다.
충돌은 크게 2가지를 이유로 발생한다.

1. 함수 알고리즘의 성능이 좋지 못한 경우
2. 저장되는 데이터의 양이 해시 테이블의크기(size)보다 큰 경우

key는 무한대로 존재할 수 있지만, 인덱스는 배열의 크기보다 작은 정수로 한정되어 있다.
따라서 key 사이의 충돌은 불가피하다.

충돌처리법 1. 서로 다른 키가 같은 해시코드를 가지는 경우 by.LinkedList

해시 함수는 유한한 범위의 값을 반환하기 때문에, 충돌을 피할 수 없다.
java의 HashMap은 충돌을 해결하기 위해 체이닝(Chaining) 방식을 사용한다.

Chaining 기법

• 개방해싱 또는 Open Hashing 기법 중 하나.
  • 해시 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 발생했을 때, 연결 리스트(Linked List) 자료구조를 활용해 해결하는 방법
  • 같은 인덱스에 여러 값을 저장하는 방법.
  • 버킷에 연결 리스트(LinkedList) 를 두어, 충돌된 항목을 모두 저장.
    • 검색 시에는 해당 리스트를 순회하며 equals()로 정확한 키를 찾음.

HashMap.java

• first node가 next를 가지는 경우, 마지막 node를 찾을때까지 반복문을 돌리며 equals()가 일치하는 노드를 조회한다
  

충돌처리법 2. 많은 데이터로 인한 성능 저하 개선

버킷에 데이터가 몰리면 검색 속도가 저하된다.
해시 테이블이 꽉 차면 성능이 O(1)에서 O(n)으로 악화될 수 있다.
따라서, 버킷의 데이터가 일정 수준을 넘어가면 사이즈를 조절하는 방법(리사이징)과 버킷의 데이터가 너무 많은 경우 탐색 방법을 변환하는 방법(트리화)을 사용할 수 있다.

리사이징(resizing)

버킷의 75%가 채워지면 충돌 확률이 크게 늘어난다.
그래서 HahsMap은 버킷의 입실률이 75%를 넘으면 버킷의 사이즈를 늘린다.

• 리사이징(resizing)
  • 일정비율(로드 팩터, 보통 0.75)을 초과하면 해시 테이블의 크기를 2배로 확장
  • 데이터 재배치(Rehashing) 수행

구체적 구현 (HashMap.java)

• threshold(newThr)
  • 버킷의 사이즈를 resize() 할 때의 임계점.
  • 처음 버킷 생성 시 지정된다.

• (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  • DEFAULT_LOAD_FACTOR: 75%
  • DEFAULT_INITIAL_CAPACITY: 16, 버킷의 처음 사이즈.
    • 이때 threshold는 16의 75%인 12가 된다.
    • 버킷에 데이터가 저장되어 그 수가 12개를 넘어가면 버킷의 사이즈는 원래 사이즈의 2배인 32가 되고, threshold도 2배인 24가 된다.
• newThr = oldThr << 1;
  • HashMap에 정수를 두 배 늘리기 위해 << 쉬프트 연산자를 이용한다.
  • 정수를 왼쪽으로 1비트 이동시켜 원래의 값의 두배로 증가시킨다.

트리화(Treeify)

버킷의 사이즈를 조절하더라도 충돌은 발생할 수 있다.
Java는 충돌의 횟수에 따라 충돌한 데이터들의 저장방식을 달리한다.
초기에는 앞서 언급한 것 처럼 LinkedList(연결리스트)를 기반으로 작동한다.
Node 객체 내부에 존재하는 next 필드를 따라 조회하며 equals()로 같은 키를 가지는 노드를 탐색한다.

그러나 충돌 횟수가 일정 수치를 넘어가면 LinkedList 방식의 데이터 저장은 효율이 크게 떨어지게 된다.
만약 어떤 Node 객체가 n번 충돌되어 n번째 Node의 next에 저장되면, 해당 Node를 탐색하는데 소요된 시간복잡도가 O(n)이 된다.
충돌이 많아질수록 효율이 떨어지는 것이다.

이를 개선하기 위해 Java 8부터는 일정 충돌 수치를 초과하면 해당 버팃의 데이터 구조를 Red-Black Tree로 변환하여 성능을 O(log n)으로 최적화한다.

Red-Black Tree

• 레드-블랙 트리(Red-Black Tree)
  • 이진 탐색 트리(BST)의 일종
  • 균형을 유지하기 위한 규칙들이 적용된 균형 이진 탐색 트리(Balanced BST)
  • 삽입 및 삭제시에도 효율적인 탐색 성능을 유지하도록 설계되어있다.

• 핵심 속성 (5가지 규칙)
  1. 각 노드는 빨간색(Red) 혹은 검은색(Black)이다.
  2. 루트 노드는 항상 검은색이다.
  3. 모든 리프 노드(NIL 노드)는 검은색이다.
  4. 빨간색 노드는 연속해서 존재할 수 없다.
     • 즉, 빨간색 노드의 부모나 자식은 항상 검은색
  5. 어떤 노드에서든 리프까지 가는 모든 경로에는 동일한 개수의 검은색 노드가 존재한다.

• ⭐️ 왜 시간 복잡도가 O(log n)일까?
  • 이진 탐색 트리의 탐색 시간: O(h) (여기서 h는 트리의 높이)
  • 레드-블랙 트리의 최대 높이: O(log n)으로 제한됨
    • 이유: 삽입/삭제 시 트리의 균형을 유지하는 회전(Rotation)과 색상 변경(Recoloring)**을 통해 트리의 높이를 제한함
    • 레드-블랙 트리는 최악의 경우에도 트리의 높이가 2 * log(n + 1)을 넘지 않음

따라서, 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(log n)으로 유지된다.

💡 직관적 이해

• LinkedList의 경우: 데이터가 쌓일수록 탐색 시간이 선형적으로 증가 -> O(n)
• 레드-블랙 트리의 경우: 트리의 균형이 유지되어 데이터가 많아도 탐색 경로가 짧음 -> O(log n)

구체적 구현(HashMap.java)

1. 버킷 저장 시점에 크기 조회
   • binCount는 충돌의 횟수를 체크한다.
   • 충돌 횟수가 TREEIFY-THRESHOLD - 1을 넝므면 treeifyBin()을 통해 트리로 전환한다.
     

2. TreeNode로의 변환
   • 단순 Node 객체로는 Red-Black Tree를 구현할 수 없다. 따라서, Node객체를 TreeNode 객체로 바꿔줘야 한다.
     • TreeNode는 단순히 Node 객체에 기능 몇가지가 추가된 것이라고 이해하면 된다.
     • 
     • 

결론

HashMap의 설계 결정 과정

🚩 문제	💡 해결 아이디어	⚙️ 설계 결정
빠른 데이터 검색이 필요함	해시 함수를 사용해 인덱스 찾기	hashCode()로 O(1) 접근
해시 충돌 발생 가능	체이닝(LinkedList) 또는 오픈 어드레싱	체이닝 방식 채택, 충돌 시 연결 리스트 사용
충돌 시 키의 정확성 확인 필요	equals()로 동등성 비교	equals()로 정확한 키 확인
데이터 증가로 인한 성능 저하	리사이징 및 트리화(Treeify) 적용	해시 테이블 확장 + 트리 구조로 최적화

한 줄 요약

"HashMap은 빠른 검색을 위해 해시를 사용하고, 해시 충돌을 체이닝과 트리화로 해결하며, equals()로 정확성을 보장하는 구조다."

---

Reference

• 🧱 Java Collections Framework 종류 💯 총정리
• [자료구조] HashMap 파헤치기 1 (Linked List + Red Black Tree)