해시 정리 (Hash)

1. 해시(Hash)란?

고정되지 않은 길이의 데이터를 고정된 길이의 데이터로 바꾸는 함수

 

해시 특징

 

특징                                             설명

고정 길이	어떤 길이의 입력이든 출력은 일정한 길이
빠른 계산	매우 빠르게 변환됨
충돌 가능성 있음	서로 다른 입력이 같은 출력값이 될 수 있음 (→ 충돌)

 

 

2. 해시 테이블(Hash Table)

- 해시 테이블(Hash Table)

해시를 사용해서 (Key -> Value) 쌍을 저장하는 자료구조

빠르게 찾기 위해 해시 함수를 사용하고, 그 결과값에 따라 버킷(Buket)에 데이터를 저장하는 구조입니다.

 

- 버킷

해시 함수를 결과값(해시코드)을 기반으로 계산된 인덱스에 위치한 저장 공간이다.

해시 테이블은 내부적으로 배열로 구성되어있고 그 배열의 각 칸이 하나의 버킷입니다.

 

버킷에 데이터가 저장되는 구조

[버킷0] → null
[버킷1] → null
[버킷2] → {"banana": "바나나"}
[버킷3] → null
[버킷4] → {"melon": "멜론"}
[버킷5] → null
[버킷6] → {"apple": "사과"} → {"mango": "망고"}  ← 충돌 발생 시 체이닝 구조

 

 

3. 해시 충돌(Hash Collision)

서로 다른 Key들이 같은 해시값으로 매핑되는 현상

 

예:

• "apple" → 456 → 인덱스 6
• "banana" → 466 → 인덱스 6

→ 둘 다 같은 인덱스를 사용하려고 하면?
→ 충돌 발생

 

Java HashMap 충돌 처리

1. 동일 인덱스에 두 개 이상의 key 저장-> LinkedList에 연결

2. 연결 리스트가 너무 길어짐 -> Tree로 변경

3. 그로 인해 검색 속도 저하를 최소화

 

해시 테이블의 시간복잡도

평균 시간복잡도 -> O(1) 상수 시간( 입력 크기와 상관없이 항상 일정한 시간 )

최악 시간복잡도 -> O(n) 선형 시간( 입력 크기만큼 반복 )

 

 

자바 Hash 내부 구조 요약

 

요소                      설명

해시 함수	key -> 정수 해시코드 생성
배열	여러 개의 버킷을 담는 저장소
버킷	실제 데이터(Key-Value)를 저장하는 공간
충돌 처리	같은 버킷에 여러 데이터가 들어올 경우, LinkedList or Tree로 연결

 

요약

해시테이블은 Key를 해시함수로 변환해 인덱스를 계산하고, 그 인덱스에 해당하는 "버킷"에 데이터를 저장하는 구조입니다.

버킷은 충돌이 발생한 경우 내부의 여러 데이터를 리스트나 트리로 연결하여 저장할 수 있고, 충동 처리 구조에 따라 성능이 달라집니다.