HashMap

자바의 정석[기초편]으로 공부한 내용을 정리한 글입니다.

 

HashMap과 Hashtable의 관계와 구조

기본 개념 요약

• Map 인터페이스는 (키, 값) 쌍의 데이터 저장을 정의합니다.
• HashMap, Hashtable, LinkedHashMap, TreeMap은 Map 인터페이스를 구현한 대표적인 클래스입니다.

 

HashMap vs Hashtable

항목	HashMap	Hashtable
동기화	❌ 동기화 안됨 (멀티스레드 환경에 부적합)	✅ 동기화됨 (멀티스레드 환경에서도 안전)
버전	비교적 최신	오래된 클래스
성능	빠름	상대적으로 느림

• 지금은 거의 HashMap 사용을 권장하며, Hashtable은 레거시 코드에서만 사용됨.

 

HashMap의 종류

1. HashMap: 기본 키-값 저장용, 순서 보장 안 됨
2. LinkedHashMap: 입력 순서 유지
3. TreeMap: 정렬된 상태로 저장 (TreeSet처럼 비교 기준 필요)
   • 내부적으로 이진 탐색 트리 구조 사용
   • 범위 검색, 정렬된 탐색에 유리함
   • 성능은 HashMap보다 느림 (추가, 삭제 시 정렬 수행)

 

HashMap 내부 구조 및 저장 방식

키(key)와 값(value)

• Key: 중복 불가
• Value: 중복 허용
   
   

map.put("myId", "1234");
map.put("asdf", "1234");

→ 키는 "myId", "asdf"로 다르므로 각각 저장됨.

 

내부 클래스 구조

Entry[] table;// 해시테이블 역할
class Entry { 
    Object key; 
    Object value;
}

• HashMap은 Entry 배열을 내부적으로 관리하며, 각 인덱스마다 LinkedList 형식으로 데이터를 연결해 저장합니다.

 

해싱(Hashing) 원리

예시: 환자 정보 조회

• 주민번호 앞자리 72 → 해시 함수 적용 → 해시코드 7 → 배열의 7번 index에 직접 접근
• 빠른 검색이 가능

해싱 과정 요약

1. 키를 해시 함수에 전달 → 해시코드(정수) 반환
2. 배열 인덱스 계산 (보통 나머지 연산 등)
3. 해당 인덱스의 LinkedList에서 key를 비교하여 정확한 Entry 탐색

 

해시충돌(Collision) 처리

❗ 왜 충돌이 일어날까?

• 서로 다른 키라도 같은 해시코드가 나올 수 있음

 

Objects.hash("A") == Objects.hash("B") // 가능

해결 방식

• 같은 인덱스에 여러 값을 저장하기 위해 LinkedList 사용
• 같은 인덱스에 여러 엔트리를 연결해서 관리

 

해싱의 전체 흐름

1. 키로 해시함수 호출 → 해시코드 얻음
2. 해시코드 기반 인덱스 계산 → 배열 위치 찾음
3. 해당 배열 위치의 LinkedList에서 key를 비교 → 정확한 값 반환

 

HashMap의 특징

검색 속도	매우 빠름 (O(1) 평균)
정렬	안됨 (순서 없음)
중복	Key ❌, Value ⭕
동기화	❌ (스레드 안전X)
내부구조	해시 테이블 + 링크드 리스트
장점	빠른 검색, 저장, 삭제
단점	충돌 발생 가능성 있음, 정렬 불가

 

 

 

 

---

 

 

 

HashMap 구조와 해싱(Hashing) 원리

HashMap이란?

• Map 인터페이스를 구현한 대표적인 클래스입니다.
• 데이터를 Key-Value 쌍으로 저장합니다.
• 순서 없음, 키 중복 불가, 값 중복 가능

관련 클래스 계층 구조

• Map ← HashMap ← LinkedHashMap, TreeMap
• HashMap은 Hashtable의 개선판입니다.
  • Hashtable: 동기화됨, 구버전 → 성능 느림
  • HashMap: 동기화 안됨, 빠름

순서를 유지하고 싶다면?

• LinkedHashMap 사용 → 입력 순서를 유지

정렬이 필요하다면?

• TreeMap 사용 → 키를 기준으로 정렬된 순서 유지

 

HashMap 저장 구조와 내부 동작

▶️ 키-값 쌍 저장 구조

HashMap<String, String> map = new HashMap<>();
map.put("myId", "1234"); 
map.put("asdf", "1234");

• 키 "myId" → 값 "1234" 저장
• 중복된 키 "asdf"가 있으면, 마지막 값 "1234"로 덮어씀

▶️ 내부 구조

transient Entry[] table;
static class Entry implements Map.Entry {
    Object key; 
    Object value;
}

• Entry 배열을 사용해 데이터를 저장함
• Object[] key, Object[] value가 아니라 → Entry[]로 관리

 

해싱(Hashing)의 원리

해시 함수와 인덱스 계산

1. 키값 "72xxxx-xxxxxxx" 입력
2. hashCode()로 해시 코드 생성 → 예: 7
3. table[7] 번지에 저장

 

int hash = key.hashCode(); // 해시 코드 생성 
int index = hash % 배열길이; // 인덱스 계산

▶️ 해시 충돌 해결 방법

• 같은 인덱스에 여러 개가 저장될 수 있음 (충돌 발생)
• 이 때는 링크드 리스트로 연결해서 저장함 → 체이닝 방식

 

저장 vs 검색 과정

저장

1. 키 → 해시 함수 → 인덱스 계산
2. 인덱스 위치에 Entry 객체 저장

검색

1. 키로 해시 코드 계산 → 인덱스 도출
2. 해당 위치에서 키가 일치하는 항목 검색 (equals())