[알고리즘] 해시 알고리즘

전지호·2025년 1월 3일

자료구조&알고리즘

목록 보기

6/25

해시 알고리즘이란?

해시 함수의 정의

해시 알고리즘은 데이터를 고정된 크기의 값으로 변환하는 수학적 함수, 즉 해시 함수(Hash Function)를 말한다.
이 과정에서 생성된 고정 크기의 값은 해시 값(Hash Value) 또는 해시 코드(Hash Code)라고 불린다.

해시 함수의 주요 특성

해시 함수는 다음과 같은 특성을 가져야 한다.

결정적(Deterministic): 동일한 입력값은 항상 동일한 해시 값을 반환해야 합니다.
고정된 출력 크기: 입력 데이터의 크기에 관계없이 해시 값은 일정한 크기를 가져야 한다. 예를 들어, SHA-256 알고리즘은 항상 256비트(32바이트)의 해시 값을 생성한다.
효율성(Efficiency): 해시 함수는 빠르게 계산될 수 있어야 한다.
충돌 회피(Collision Resistance): 서로 다른 두 입력값이 동일한 해시 값을 가질 가능성이 낮아야 한다. 완벽한 충돌 회피는 불가능하지만, 충돌 발생 가능성을 최소화하는 것이 중요하다.

해시 함수의 용도

데이터 검색 및 저장: 해시 테이블(Hash Table)과 같은 자료구조에서 빠른 데이터 검색을 위해 사용된다.
데이터 무결성 검증: 파일이나 메시지의 변경 여부를 확인하기 위해 해시 값을 비교한다.
암호화 및 보안: 비밀번호 저장, 디지털 서명, 인증 등에 사용되는 암호화 해시 알고리즘이 있다.
데이터 분산 및 로드 밸런싱: 대규모 시스템에서 데이터를 효율적으로 분산시키기 위해 활용된다.

자바에서의 해시 알고리즘

자바는 해시 알고리즘을 다양한 형태로 제공하며, 주로 다음 두 가지 영역에서 사용된다.

객체의 hashCode() 메서드와 해시 기반 컬렉션
암호화 해시 알고리즘 (Cryptographic Hash Algorithms)

hashCode() 메서드

자바의 모든 객체는 Object 클래스로부터 hashCode() 메서드를 상속받는다.
이 메서드는 객체를 고유하게 식별할 수 있는 정수형 해시 코드를 반환한다.
해시 코드는 주로 해시 기반 컬렉션(HashMap, HashSet, Hashtable 등)에서 객체를 빠르게 저장하고 검색하는 데 사용된다.

메서드 오버라이딩

사용자 정의 클래스에서 hashCode()를 오버라이딩할 때는 equals() 메서드와의 일관성을 유지해야 한다.
즉, 두 객체가 equals()로 동일하다고 판단되면, 두 객체의 hashCode()도 동일해야 한다는 소리이다.

public class User {
	private String id;
    
    public User(String id) {
    	this.id = id;
    }
    
    @Override
    public boolean equals(Object o) {
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(id, user.id);
    }
    
    @Override
    public int hashCode() {
    	return Objects.hashCode(id);
    }
}

위의 예제는 id를 기반으로 체크하고 있음

해시 함수

해시 함수는 임의의 길이의 데이터를 입력으로 받아, 고정된 길이의 해시값을 출력하는 함수이다.
같은 데이터를 입력하면 항상 같은 해시 코드가 출력된다.
다른 데이터를 입력해도 같은 해시코드가 출력될 수 있다. 이 것을 해시 충돌이라 한다.

해시 코드

해시 코드는 데이터를 대표하는 값을 뜻한다. 보통 해시 함수를 통해 만들어진다.
- 데이터 A의 해시코드는 65
- 데이터 B의 해시코드는 66

해시 인덱스

HashSet 에 값을 저장할때 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스라 한다.

해시 인덱스는 데이터의 저장 위치를 결정하는데, 주로 해시 코드를 사용해서 만들어진다.
보통 해시 코드의 결과에 배열의 크기를 나누어 구한다.

주의
이해하기 쉽게 설명한것이며 실제 자바의 해시 인덱스 계산 방식은 다릅니다.

private int hashIndex() {
	// Objects.hashCode() 는 음수 값을 가질 수 있어서 절댓값을 사용했음
	return Math.abs(Objects.hashCode()) % 배열의 크기;
}

요약
해시 코드: 데이터를 대표하는 값
해시 함수: 해시 코드를 생성해주는 함수
해시 인덱스: 해시 코드를 사용해서 데이터의 저장 위치를 결정하는 값

해시 충돌

위의 해시 인덱스에서 배열에 값을 저장할때 해시 인덱스를 통해 저장한다고 했다.
그리고 다른 데이터여도 같은 해시 코드가 나올 수 있다고 했다.

이 해시 코드를 배열의 크기로 나머지 연산을 하면 똑같은 해시 인덱스가 나오는데 이 때 같은 인덱스에 값을 저장하는 것을 해시 충돌이라고 한다.

충돌 결과 예시

arr = [null, 1, null, 3, 4, null, null, null, null, [9, 99]];

실제 HashSet 은 위처럼 데이터 저장이 되지 않습니다. 예시입니다.

위를 보면 배열의 크기는 10이고 값으로는 9, 99 를 입력했더니 같은 인덱스인 9에 값이 두 개가 저장된 것이 보인다.

HashSet을 예시로 처음에는 1차원 배열 상태로 값을 저장하다가 해시 충돌이 나는 경우에는 내부에 LinkedList를 새로 생성하여 값을 위처럼 저장하게 된다.

이 때 해당 인덱스의 값을 조회할때는 O(n) 의 성능이 나온다.
만약 해당 인덱스에 값이 8개 이상이 저장되는 경우에는 LinkedList 에서 레드-블랙 트리로 전환되어 검색 기능을 O(log n) 으로 최적화 한다.

충돌 최적화

만약 데이터의 수가 배열 크기의 75% 를 넘게되면 해시 충돌이 자주 일어나게 된다.
자바는 이 충돌을 최소화 하기 위해서 배열 크기가 75%를 넘게되면 배열의 크기를 2배로 늘리고, 해시 인덱스를 재측정하여 새 인덱스에 데이터 들을 저장한다.

전지호

백엔드로 전향하기 위해서 공부중인 3년차 프론트엔드 개발자입니다.