해싱(Hashing)과 일반 해시 함수(non-cryptographic hash function)

해싱

해싱(Hashing)은 가변 길이의 입력 데이터를 받아서 고정 길이의 출력 값으로 변환하는 과정을 의미한다. 이때 생성된 고정된 크기의 값은 해시 값 또는 다이제스트(digest)라고 불리며, 원본 데이터와는 크기나 형식이 다르다. 해싱은 데이터의 무결성 검증, 빠른 데이터 검색, 비밀번호 저장 등 다양한 목적으로 사용된다.

특징

단방향성: 해싱은 단방향 함수이다. 즉, 원본 데이터를 해시 값으로 변환할 수는 있지만, 반대로 해시 값에서 원본 데이터를 복원하는 것은 불가능하다. 이 때문에 해싱은 암호화와는 다르며, 주로 데이터의 무결성을 확인하는 데 사용된다.
고유성(충돌 저항성): 서로 다른 입력값이 동일한 해시 값을 생성할 확률은 매우 낮다. 이를 충돌 저항성이라고 하며, 이 특성 덕분에 해싱은 데이터의 무결성을 검증하는 데 유용하다. 이상적으로는 해시 함수는 서로 다른 두 개의 입력값이 동일한 해시 값을 생성하지 않도록 설계된다.
고정된 출력 크기: 해시 함수는 입력 데이터의 크기와 상관없이 항상 고정된 크기의 해시 값을 생성한다. 예를 들어, SHA-256 해시 함수는 256비트 크기의 해시 값을 생성한다.
빠른 계산: 해시 함수는 계산이 빠르고, 입력 데이터가 크더라도 해시 값을 빠르게 생성할 수 있다. 이 특징은 해싱이 대규모 데이터 처리나 빠른 검색 기능에 사용되는 이유 중 하나이다.

다음 해시 함수를 살펴보자.

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

Effective Java에서 Joshua Bloch는 값 31이 홀수와 소수이기 때문에 의도적으로 선택되었다고 설명한다.

해시와 홀수

해시 곱셈 상수를 짝수로 곱했을 경우와 홀수로 곱했을 경우의 차이를 비교해보자.

짝수를 곱할 때

숫자 5(이진수 101)를 짝수 2로 곱하면 10(이진수 1010)이 된다.
숫자 6(이진수 110)을 짝수 2로 곱하면 12(이진수 1100)이 된다.
짝수를 곱할 시 마지막 비트가 항상 0이 되므로, 표현 가능한 숫자 범위의 절반 밖에 사용하지 못한다. 그래서 같은 해시 값, 즉 해시 충돌이 일어날 가능성이 높아진다.

홀수를 곱할 때

숫자 5(이진수 101)를 홀수 3으로 곱하면 15(이진수 1111)가 된다.
숫자 6(이진수 110)을 홀수 3으로 곱하면 18(이진수 10010)이 된다.
마지막 비트까지 전부 사용할 수 있다. 그러므로 서로 다른 해시 값을 가질 가능성이 높아지고, 충돌이 줄어든다.

해시와 소수(prime number)

소수는 1과 자기 자신 외에는 나눌 수 없는 수. 소수는 약수가 적기 때문에 해시 코드 생성 시 충돌을 줄이는 데 도움이 된다. 즉, 해시 함수에서 소수를 사용하면 해시 값의 분포가 더 고르게 퍼지게 되어, 서로 다른 입력값이 같은 해시 값을 가질 확률이 낮아진다.

이외에 해쉬 곱셈 상수 31을 사용하는 이유 중 하나로 31이 2^5 - 1이어서 쉬프트 연산을 통해 (N << 5) - N과 같이 속도를 개선할 수 있다고 한다. 그렇다면 31(홀수 + 상수 + 쉬프트 연산)과 19(홀수 + 상수)사이에 실제로 속도 차이가 있을까? 1억번씩 호출하여 비교해보자.

해시 곱셈 상수 31 vs 19 속도 비교

package org.example;

public class HashTestMain {

  // 해시 상수 31을 사용하는 클래스
  static class HashWith31 {
    private String value;

    public HashWith31(String value) {
      this.value = value;
    }

    @Override
    public int hashCode() {
      int result = 1;
      result = 31 * result + (value != null ? value.hashCode() : 0);
      return result;
    }
  }

  // 해시 상수 19를 사용하는 클래스
  static class HashWith19 {
    private String value;

    public HashWith19(String value) {
      this.value = value;
    }

    @Override
    public int hashCode() {
      int result = 1;
      result = 19 * result + (value != null ? value.hashCode() : 0);
      return result;
    }
  }

  public static void main(String[] args) {
    // 테스트할 문자열
    String testString = "This is a test string for hashCode performance measurement.";

    // 반복 횟수
    int iterations = 100_000_000;

    // HashWith19 클래스의 속도 측정
    HashWith19 hash19 = new HashWith19(testString);
    long startTime19 = System.nanoTime();
    int hash19Result = 0;
    for (int i = 0; i < iterations; i++) {
      hash19Result = hash19.hashCode() + i; // 캐싱 방지를 위해 i를 더함
    }
    long endTime19 = System.nanoTime();
    long totalTime19 = endTime19 - startTime19;

    // HashWith31 클래스의 속도 측정
    HashWith31 hash31 = new HashWith31(testString);
    long startTime31 = System.nanoTime();
    int hash31Result = 0;
    for (int i = 0; i < iterations; i++) {
      hash31Result = hash31.hashCode() + i; // 캐싱 방지를 위해 i를 더함
    }
    long endTime31 = System.nanoTime();
    long totalTime31 = endTime31 - startTime31;

    System.out.println("Hash 곱셈 상수 19를 사용했을 때 총 시간: " + totalTime19 + " nanoseconds");
    System.out.println("Hash 곱셈 상수 31을 사용했을 때 총 시간: " + totalTime31 + " nanoseconds");
  }
}

실행 시에는 19와 31 각각 주석처리를 하고 독립적으로 실행하였다. 결과는 다음과 같다.

해쉬 곱셈 상수가 19일 때 오히려 더 빠르다. 여러 번 테스트해본 결과, 31이 더 빠를 때도 있지만 차이는 크지 않다. 컴퓨터의 성능이 향상된 덕분인지, 이제는 31을 사용한다고 속도가 개선된다는 것은 과거의 이야기인 것 같다.

HashCode()

hashCode() 메서드의 실제 동작을 살펴보자.

public static void main(String[] args) {
    String anotherTest = "java";
    String test = "test";
    String oneMoreTest = "dev";
    System.out.println(test.hashCode()); // output: 3556498
    System.out.println(test.hashCode()); // output: 3556498
    System.out.println(anotherTest.hashCode()); // output: 3254818
    System.out.println(oneMoreTest.hashCode()); // output: 99349
}

결과를 보면 해시 함수 특징을 알 수 있다.

hashCode() 호출은 단방향 연산으로, 생성된 해시 값만으로는 원래 문자열을 복구할 수 없다.
결정론적이다. 동일한 변수를 두 번 호출했을 때, 동일한 해시 값을 반환한다.
Java의 int는 32비트(4바이트)의 고정된 크기를 가진다. 즉 hashCode()메서드가 반환하는 해시 값(int 형태)도 항상 32비트의 고정된 길이다.

일반 해시 함수?

일반 해시 함수(Non-cryptographic hash function)는 보안 목적으로 설계되지 않은 해시 함수로, 주로 데이터 검색, 해시 테이블, 체크섬과 같은 용도에 사용된다. 일반 해시 함수는 빠른 계산 속도와 충돌을 적절히 처리할 수 있는 성능을 중시하지만, 암호화 수준의 보안성을 제공하지는 않는다.

특징

빠른 계산: 일반 해시 함수는 보안성을 고려하지 않기 때문에, 매우 빠르게 계산할 수 있다. 이는 대규모 데이터 집합에서 효율적으로 사용할 수 있도록 설계된 것이다.
충돌 허용: 일반 해시 함수는 보안보다는 성능에 중점을 두므로, 충돌이 발생할 가능성이 있을 수 있다. 그러나 이러한 충돌은 일반적으로 해시 테이블에서 적절히 처리될 수 있다.
용도: 일반 해시 함수는 데이터베이스 검색, 파일 무결성 확인, 분산 시스템에서의 데이터 균형 맞추기 등 비보안적인 용도로 주로 사용된다.

예시

MurmurHash: 매우 빠르고 충돌이 적은 해시 함수로, 주로 해시 테이블에서 사용된다.
CityHash: 구글에서 개발한 해시 함수로, 매우 빠르면서도 높은 성능을 제공한다.
DJB2: 단순하고 빠르며, 자주 사용되는 해시 함수 중 하나이다.

References

Java HashMap은 어떻게 동작하는가? - https://d2.naver.com/helloworld/831311

Deep Dive into Hasing - https://www.baeldung.com/cs/hashing

저작자표시 동일조건

해싱

특징

해시와 홀수

짝수를 곱할 때

홀수를 곱할 때

해시와 소수(prime number)

해시 곱셈 상수 31 vs 19 속도 비교

HashCode()

일반 해시 함수?

특징

예시

References

티스토리툴바