해시(Hash)와 해시코드(HashCode)

1. 해시(Hash)

• 정의: 해시는 임의의 데이터를 고정된 크기의 고유한 값으로 변환하는 과정을 말합니다. 이 변환 과정에서 사용되는 함수가 해시 함수(Hash Function)입니다.

• 목적: 해시는 주로 데이터를 빠르게 검색하기 위해 사용됩니다. 데이터의 키(Key)를 해시 함수에 입력하면, 이 함수는 해당 키에 대한 고유한 해시 값을 반환합니다. 이 해시 값은 데이터가 저장될 위치를 결정하는 데 사용됩니다.

• 해시 함수의 특성:
• 결정적: 동일한 입력이 주어지면 항상 동일한 출력(해시 값)이 나와야 합니다.
• 효율성: 해시 함수는 빠르게 계산되어야 합니다.
• 균일성: 입력 값들이 해시 테이블 내에서 가능한 한 균등하게 분포되도록 해시 값을 생성해야 합니다.
• 충돌 방지: 서로 다른 입력이 동일한 해시 값을 가지는 경우를 해시 충돌(Hash Collision)이라고 합니다. 완벽한 충돌 방지 해시 함수는 존재하지 않으므로, 충돌이 발생할 경우 이를 처리할 수 있는 방법(예: 체이닝, 개방 주소법 등)이 필요합니다.

2. 해시코드(HashCode)

• 정의: 해시코드는 객체의 데이터를 정수 값으로 변환한 값입니다. 자바에서 해시코드는 int 타입의 값으로 표현되며, 객체를 해시 기반 데이터 구조(예: HashMap, HashSet)에 저장하거나 비교할 때 사용됩니다.

• 자바에서의 해시코드:
• 모든 자바 객체는 hashCode() 메소드를 가지고 있으며, 기본적으로 객체의 메모리 주소를 기반으로 해시코드를 반환합니다. 그러나 이 메소드는 필요에 따라 재정의할 수 있습니다.
• hashCode() 메소드를 재정의할 때는 equals() 메소드도 함께 재정의하는 것이 일반적입니다. 이는 동일한 데이터를 가진 두 객체가 동일한 해시코드를 가지도록 하기 위함입니다.

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

@Override
public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj == null || getClass() != obj.getClass()) return false;
    Person person = (Person) obj;
    return age == person.age && Objects.equals(name, person.name);
}

• 해시코드의 역할:
• 빠른 검색: 해시코드는 객체를 특정한 슬롯(Slot)이나 버킷(Bucket)에 배치하는 데 사용됩니다. 예를 들어, HashMap에서 키에 해당하는 해시코드를 통해 빠르게 값을 검색할 수 있습니다.
• 효율적인 저장: 해시코드는 객체를 그룹화하여 저장하는 데 도움을 줍니다. 이는 데이터 구조의 성능을 최적화하는 데 기여합니다.

3. 해시 충돌 (Hash Collision)

• 정의: 서로 다른 두 입력 값이 동일한 해시코드를 반환하는 상황을 해시 충돌이라고 합니다. 해시 충돌은 피할 수 없는 문제이며, 이 상황을 처리하는 다양한 방법이 있습니다.

• 충돌 처리 방법:
• 체이닝(Chaining): 해시 테이블의 각 슬롯이 연결 리스트로 구성되어 있어, 동일한 해시코드를 가진 여러 항목을 이 리스트에 저장합니다.
• 개방 주소법(Open Addressing): 해시 충돌이 발생하면 다른 슬롯을 탐색하여 데이터를 저장하는 방식입니다. 이 방법에는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.

4. 해시와 해시코드의 예시 (Java)

import java.util.HashMap;
import java.util.Map;

public class HashExample {
    public static void main(String[] args) {
        // HashMap을 사용한 예시
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);

        // "apple"이라는 키의 해시코드를 출력
        int hashCode = "apple".hashCode();
        System.out.println("HashCode for 'apple': " + hashCode);

        // HashMap에서 "apple" 키로 값 검색
        int value = map.get("apple");
        System.out.println("Value for 'apple': " + value);
    }
}

5. 중요 개념 요약

• 해시: 데이터의 빠른 검색을 위한 고정 크기의 고유한 값으로의 변환.

• 해시코드: 객체의 데이터를 정수 값으로 표현한 것으로, 해시 기반 데이터 구조에서 사용됨.

• 해시 충돌: 동일한 해시코드를 갖는 서로 다른 입력 값이 발생하는 상황으로, 이를 처리하기 위한 방법이 필요함.