redblacktree1 Java HashMap 충돌 처리 : 체이닝, LinkedList ↔ Tree 전환, 설계 원리와 내부 동작 분석 Java 컬렉션 중 하나인 HashMap은 매우 자주 쓰고 일반적으로 O(1)의 조회 성능을 기대할 수 있다.그 이유는 내부적으로 HashTable 구조를 기반으로 key의 해시값에 따라 배열의 인덱스를 계산하여 데이터를 저장하고 조회하기 때문이다. 그런데 여기서 생기는 “해시 충돌” 문제는 어떻게 해결되고 있을까?이 글에서는 그 과정을 개념 → 코드 → 의문점 → 추론 흐름으로 정리했다. 1. 해시 충돌(Hash Collision)이란?서로 다른 두 객체가 같은 hashCode() 값을 갖는 경우이다.결국 동일한 배열 인덱스에 저장되어 있음충돌이 발생함이렇게 동일한 버킷에 여러 객체가 들어가는 상황이 발생한다. 충돌 해결 방법 1. 체이닝(Chaining)같은 인덱스에 여러 엔트리를 연결 리스트나 트.. 2025. 8. 7. 이전 1 다음
