[JAVA] Hash

Hash란?

해시(Hash)는 데이터를 고정된 크기의 고유한 값(숫자)으로 변환하는 함수 또는 그 결과 값을 의미합니다.

이때 사용되는 함수는 해시 함수(Hash Function)라고 부릅니다.

 

해시 함수의 특징

Deterministic	같은 입력이면 항상 같은 출력
Fast	계산이 빠르다
Uniformity	해시값이 고르게 분포되면 성능이 좋다
Collision 가능성 존재	서로 다른 입력값이 같은 해시값을 가질 수 있음
One-way (암호학적 해시)	입력값을 추정하기 어렵게 설계됨 (SHA-256 등)

 

해시의 사용처

• 해시 테이블 구현 (HashMap, HashSet, Hashtable)
• 암호학 (비밀번호 저장 시 해싱: SHA-256, bcrypt)
• 데이터 무결성 검증 (파일 해시: MD5, SHA)
• 캐시 키 생성
• 블록체인 (블록 간 연결)

 

해시 충돌이란?

 

• 해시 함수는 무한한 입력값을 유한한 크기의 해시값(정수)로 매핑합니다.
• 결국 서로 다른 객체가 동일한 해시값(hashCode)을 갖게 되는 경우가 발생하며, 이를 해시 충돌(Collision)이라고 합니다.
• Java의 hashCode()는 32비트 정수이기 때문에, 많은 객체가 존재할수록 충돌 확률은 자연스럽게 증가합니다.

 

+ 이러한 이유로 자바에서 hashCode()를 오버라이딩 할 때 단짝처럼 equals()도 오버라이딩 해야합니다. 별개의 객체가 우연히 해시코드가 똑같이 나오게 되더라도, equals()로 값의 동등성을 한번 더 확인 하는 과정을 거치게 되면 충돌을 방지 할 수 있습니다.

 

Java에서 충돌 시 어떻게 처리되는가?

 

Java의 HashMap은 다음 순서로 충돌을 처리합니다:

1. 먼저 hashCode()를 기준으로 배열 인덱스(bucket)를 계산합니다.
2. 만약 해당 버킷에 이미 값이 있다면:
   • equals()로 key가 같은지 비교
   • 같으면 값을 덮어씀
   • 다르면 체이닝 방식으로 연결하여 저장

체이닝 방식

• 충돌된 키들은 LinkedList 형태로 같은 버킷에 이어 붙입니다. 이를 체이닝(Chaining)이라고 합니다.
• 그러나 리스트가 너무 길어지면 탐색 속도는 O(n)까지 느려집니다.
• Java 8부터는 다음 조건에서 해당 리스트를 Red-Black Tree로 변환하여 탐색 속도를 O(log n) 으로 유지합니다.

트리로 전환되는 조건

• 같은 버킷 내 충돌된 항목 수가 8개 이상
• 전체 버킷 크기(table.length)가 64 이상

이 경우 내부적으로 Node 대신 TreeNode로 저장됩니다.

 

왜 equals()가 중요한가?

• hashCode()가 같더라도 객체가 동일한지는 equals()로 최종 판단합니다.
• HashMap이나 HashSet은 동일한 key를 중복 저장하지 않기 위해 equals()로 비교합니다.

주의

hashCode()만 오버라이드하고 equals()를 오버라이드하지 않으면, 충돌 시 동일 객체로 판단하지 못해서 중복 저장이 발생할 수 있습니다.

 

 왜 둘 다 오버라이드해야 하는가?

HashMap, HashSet과 같은 해시 기반 자료구조는 다음과 같은 순서로 객체의 동등성을 판단합니다:

1. hashCode()로 버킷 위치를 찾고
2. 해당 버킷 안에서 equals()로 객체 동등성 비교

따라서 두 메서드가 논리적으로 일치해야 정확하게 작동합니다.

 Java의 규칙 (중요)

equals()가 같다면, hashCode()도 같아야 한다.

 

 둘 다 오버라이드하지 않으면 생기는 문제

 equals()만 오버라이드하고 hashCode()는 그대로 두면?

• equals()는 같다고 판단하지만, 서로 다른 해시 버킷에 들어가서 중복 저장됨

 hashCode()만 오버라이드하고 equals()는 그대로 두면?

• 해시값이 같아도, equals()는 다르다고 판단 → 중복 저장됨

 

 

항목 설명

hashCode() 역할	객체의 버킷 위치 결정
equals() 역할	같은 버킷 내에서 실제 동등한 객체인지 확인
둘 다 필요한 이유	한쪽만 정확해도 일관된 동작 보장 불가능
오버라이드 실수 시 문제	중복 저장, 삭제 불가, 검색 실패 등 버그 발생 가능