DotNet
자료구조
자료구조에서의 해시 함수

자료구조에서의 해시 함수

해시 함수란?

해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값(또는 해시 코드)으로 변환하는 함수입니다. 해시 함수는 데이터를 적절한 크기의 공간으로 매핑해주는 역할을 하며, 다음과 같은 특성을 가집니다.

  • 결정적 특성: 동일한 입력에 대해 항상 동일한 해시 값을 반환해야 합니다.
  • 효율성: 해시 함수는 계산이 빨라야 합니다.
  • 균등 분포: 가능한 한 해시 값이 고르게 분포되어야 합니다. 해시 코드란 해시 함수에 의해 반환되는 정수 값으로, 데이터의 저장 위치를 결정하는 데 사용됩니다. 하지만 서로 다른 두 개의 입력이 동일한 해시 코드를 가지는 경우도 있습니다. 이를 해시 충돌Hash Collision이라고 하며, 충돌이 많아지면 해시 테이블의 성능이 저하될 수 있으므로 이를 최소화하는 것이 중요합니다.

해시 함수와 해시 테이블

해시 테이블은 키-값 쌍을 저장하며, 해시 함수를 사용하여 키를 해시 코드로 변환하고, 이를 인덱스로 사용하여 데이터를 저장합니다. 주요 특징은 다음과 같습니다.

  • 빠른 검색, 삽입, 삭제: 평균적으로 O(1)의 시간 복잡도를 가집니다.
  • 유연성: 다양한 종류의 데이터에 대해 사용할 수 있습니다. 해시 함수의 품질은 해시 테이블의 성능에 직접적으로 영향을 미칩니다. 고품질의 해시 함수는 데이터를 고르게 분포시켜 충돌 가능성을 줄이고, 테이블 내에서 데이터 접근을 빠르게 합니다. 반면, 해시 함수가 좋지 않다면 특정 위치에 데이터가 몰리게 되어 성능이 급격히 저하될 수 있습니다.

해시 함수의 품질과 성능

해시 함수의 품질은 다음과 같은 요소들에 의해 결정됩니다.

균등 분포Uniformity

입력 데이터를 해시 코드 공간에 고르게 분포시켜야 합니다. 특정 해시 코드에 데이터가 몰리게 되면 충돌이 발생하고, 이는 해시 테이블의 성능을 저하시키는 원인이 됩니다.

효율성Efficiency

해시 함수는 계산이 빨라야 합니다. 만약 해시 함수의 계산이 느리다면, 해시 테이블의 빠른 접근 장점이 무색해집니다.

낮은 충돌률Low Collision Rate

서로 다른 입력이 동일한 해시 코드를 가질 확률을 최대한 낮추는 것이 중요합니다. 이를 위해 좋은 해시 알고리즘을 사용하고, 해시 테이블의 크기를 적절히 설정하는 등의 노력이 필요합니다.

해시 충돌 해결 방법

해시 충돌은 피할 수 없는 문제이기 때문에, 이를 효과적으로 해결할 수 있는 방법들이 필요합니다.

체이닝Chaining

같은 해시 코드를 가진 데이터를 연결 리스트로 연결하여 저장하는 방식입니다. 충돌이 발생하면 해당 슬롯에 연결 리스트를 추가하는 방식으로 저장합니다. 이 방법의 장점은 해시 테이블의 크기에 크게 구애받지 않는다는 것이지만, 연결 리스트를 순회해야 하므로 최악의 경우 O(n)의 시간 복잡도를 가집니다.

개방 주소법Open Addressing

충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장하는 방식입니다. 대표적인 탐사 기법으로는 선형 탐사Linear Probing, 이차 탐사Quadratic Probing, 이중 해싱Double Hashing 등이 있습니다. 개방 주소법의 장점은 추가적인 자료구조가 필요 없다는 것이지만, 클러스터링 현상이 발생할 수 있고 테이블의 부하율이 높아지면 성능이 급격히 저하될 수 있습니다.

완벽 해싱Perfect Hashing

충돌이 없는 해싱을 구현하는 방법으로, 모든 키에 대해 고유한 해시 코드를 생성하여 충돌을 완전히 방지합니다. 이러한 방법은 키의 집합이 고정되어 있고, 빠른 조회가 필요한 경우에 적합합니다.

Cuckoo 해싱

두 개의 해시 함수를 사용하여 충돌을 해결합니다. 충돌이 발생하면 기존 요소를 다른 위치로 옮기고, 새로운 요소를 삽입하는 방식입니다. 이 방식은 조회 속도가 매우 빠르고 충돌된 항목들이 연속된 메모리 슬롯에 모여 있는 클러스터링 현상이 적지만, 재해싱이 빈번하게 발생할 수 있다는 단점이 있습니다. 체이닝이나 개방 주소법은 이미 충돌이 발생한 상황에서 해당 충돌을 어떻게 해결할지에 초점을 맞춥니다. 반면에 완벽 해싱과 Cuckoo 해싱은 충돌을 미연에 방지하거나 충돌 해결 과정을 근본적으로 재설계하는 접근입니다.

자료구조와 해시 테이블

해시 테이블 활용 예시

해시 테이블은 다양한 용도로 활용되며, 대표적인 예로 HashSet과 Dictionary가 있습니다.

  • HashSet<T>: HashSet은 중복된 요소를 허용하지 않으며, 요소의 존재 여부를 빠르게 확인할 수 있는 자료구조입니다. 데이터의 중복 제거, 원소의 존재 여부 검사 등에 사용됩니다.
  • Dictionary<TKey, TValue>: Dictionary는 키-값 쌍으로 데이터를 저장하며, 키를 통해 값에 빠르게 접근할 수 있는 자료구조입니다. 데이터 매핑, 캐시 구현, 설정 값 저장 등 여러 용도로 사용됩니다. 해시 테이블 기반의 컬렉션에서는 해시 함수의 품질이 매우 중요합니다.

사용자 정의 타입의 해시 함수 구현

사용자 정의 클래스나 구조체를 해시 테이블의 키로 사용할 때는 GetHashCode()와 Equals() 메서드를 적절히 재정의하는 것이 중요합니다. 그렇지 않으면 동일한 객체임에도 불구하고 서로 다른 해시 코드가 생성되거나, 충돌이 빈번하게 발생하여 성능 저하가 생길 수 있습니다.

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
    public override int GetHashCode()
    {
        return HashCode.Combine(Name, Age);
    }
    public override bool Equals(object obj)
    {
        if (obj is Person other)
            return Name == other.Name && Age == other.Age;
        return false;
    }
}

위 예제에서는 Person 클래스의 GetHashCode와 Equals 메서드를 재정의하여, 같은 이름과 나이를 가진 객체가 동일하게 취급되도록 하고 있습니다.

해시 함수의 응용

블룸 필터

블룸 필터Bloom Filter는 공간 효율적인 확률적 자료구조로, 요소가 집합에 속하는지 여부를 빠르게 검사할 수 있으며, 주로 캐시 시스템에서 데이터가 존재하는지 여부를 확인하는 데 사용됩니다. 데이터베이스 접근 전 캐시에 존재하지 않는 데이터임을 빠르게 확인하거나 스팸 필터링 또는 네트워크 패킷 분석 등에서 많은 양의 데이터를 효율적으로 처리하는 경우에 사용합니다. 블룸 필터는 오탐false positive, 즉 어떤 요소가 실제로는 집합에 없는데 있다고 판단하는 경우가 있을 수 있지만, 누락false negative은 허용하지 않습니다. 이는 일정 정도의 메모리와 해시 함수를 사용하여 데이터의 존재 여부를 빠르게 판단할 수 있는 장점이 있습니다. 블룸 필터에서 사용하는 해시 함수의 품질은 필터의 성능에 큰 영향을 미칩니다. 여러 개의 독립적인 해시 함수를 사용하여 입력 값을 해시 공간 내에서 중복되지 않게 위치를 설정함으로써, 오탐률을 낮추고 필터의 효율을 높일 수 있습니다.

컨시스턴트 해싱

컨시스턴트 해싱Consistent Hashing은 분산 시스템에서 데이터의 위치를 결정하고 노드 간의 데이터를 균형 있게 분배하기 위해 사용되는 해시 방법입니다. 특히 분산 캐시 시스템이나 분산 데이터베이스에서 많이 사용됩니다.

컨시스턴트 해싱의 필요성

분산 시스템에서는 여러 서버(또는 노드) 간에 데이터를 분배해야 하며, 새로운 서버가 추가되거나 기존 서버가 제거될 때 데이터의 재분배가 필요합니다. 이때 일반적인 해시 방식은 많은 데이터를 재배치해야 하기 때문에 시스템에 큰 부담이 될 수 있습니다. 컨시스턴트 해싱은 노드의 추가나 제거 시 데이터의 재배치를 최소화하도록 설계된 해싱 방법입니다. 이를 통해 시스템의 확장성과 안정성을 높일 수 있습니다.

해시 함수의 종류

해시 함수는 다양한 응용 목적에 맞게 여러 종류가 있으며, 그 특성과 방식에 따라 다음과 같은 주요 해시 함수 유형이 있습니다.

비암호화 해시 함수

비암호화 해시 함수Non-Cryptographic Hash Functions는 보안보다는 빠른 계산과 균등한 분포에 중점을 둔 해시 함수입니다. 주로 데이터 검색, 데이터베이스 색인, 체크섬 등에 사용됩니다.

  • Modulus Hashing (나머지 연산 해싱): 단순히 키 값에 특정 정수를 나누어 나머지를 인덱스로 사용하는 방법입니다. 구현이 간단하지만, 특정 패턴의 키에 취약할 수 있습니다.
  • Division Hashing (나눗셈 해싱): 키 % 소수와 같이 소수(Prime Number)를 나머지로 사용하는 방식입니다. 데이터가 고르게 분포되기 때문에 일반적으로 균등한 해싱을 제공합니다.
  • Multiplicative Hashing (곱셈 해싱): 키에 일정한 상수를 곱한 후, 소수점 이하의 일부 비트를 선택하여 인덱스를 계산하는 방식입니다. 곱셈 해싱은 균등 분포를 잘 제공하지만, 상수를 신중하게 선택해야 효과적입니다.
  • FNV Hash: Fowler-Noll-Vo 해시라고도 하며, 빠르고 간단한 해싱을 제공하는 해시 함수입니다. 보통 짧은 문자열을 해싱할 때 성능이 좋으며, 고속 해싱이 요구되는 경우 유용합니다.
  • MurmurHash: 구글이 개발한 해시 함수로, 속도와 균등 분포에서 성능이 뛰어납니다. 암호화 요구사항이 없는 데이터베이스나 분산 시스템에서 자주 사용됩니다.
  • Jenkins Hash: 밥 젠킨스Bob Jenkins가 설계한 해시 함수로, 균일한 분포와 충돌 방지에 초점을 맞춰 설계되었습니다. 데이터베이스 색인이나 해시 테이블에서 자주 사용됩니다.
  • CityHash, FarmHash: 구글이 개발한 고속 해시 함수로, 특히 긴 문자열을 해싱할 때 효율적입니다. 문자열을 해싱하는 경우에 최적화되어 있으며, 매우 빠른 속도를 제공합니다.

암호화 해시 함수

암호화 해시 함수Cryptographic Hash Functions는 보안성이 강조된 해시 함수로, 해시 충돌이 발생할 확률이 낮고, 해시 값에서 원본 데이터를 역으로 계산하는 것이 불가능해야 합니다. 주로 데이터 무결성 검증, 디지털 서명, 암호화에 사용됩니다.

  • MD5Message Digest Algorithm 5: 128비트 해시를 생성하는 해시 함수로, 과거에는 많이 사용되었지만, 현재는 보안 취약점으로 인해 보안 용도로는 권장되지 않습니다.
  • SHA-1Secure Hash Algorithm 1: 160비트 해시를 생성하며, MD5보다 강력하지만, 충돌 공격이 발견되어 현재는 더 안전한 해시 알고리즘으로 대체되었습니다.
  • SHA-2SHA-224, SHA-256, SHA-384, SHA-512: SHA-1의 후속 알고리즘으로, 비트 크기를 선택할 수 있으며 현재 널리 사용됩니다. 특히 SHA-256은 데이터 무결성 검증과 디지털 서명 등에서 많이 사용됩니다.
  • SHA-3: SHA-2의 후속 알고리즘으로, 켁작Keccak 해시 함수 기반으로 설계되었습니다. SHA-2보다 복잡한 구조를 가지고 있으며, 보안성과 성능이 강화되었습니다.
  • Blake2: SHA-3의 대안으로 제안된 암호화 해시 함수로, SHA-2보다 더 빠르면서도 높은 보안을 제공합니다. 빠른 암호화가 필요한 환경에서 사용됩니다.

체크섬과 해싱 함수

체크섬Checksum Functions은 데이터 전송 중 오류 검출을 위해 사용되는 간단한 해시 함수입니다. 복잡한 보안 기능은 없으며, 데이터의 무결성만을 검증합니다.

  • CRCCyclic Redundancy Check: 주로 데이터 전송 중 오류 검출을 위해 사용됩니다. 복잡한 보안을 제공하지 않지만, 전송 데이터의 무결성을 확인하는 데 유용합니다.

  • Adler-32: 간단하고 빠른 체크섬 알고리즘으로, Fletcher 체크섬의 변형입니다. 주로 네트워크 데이터 전송에서 사용됩니다.

유니버설 해시 함수

유니버설 해시 함수Universal Hash Functions는 동적 프로그래밍과 무작위 해싱에 주로 사용됩니다. 해시 함수를 무작위로 선택하여 충돌을 줄이고, 악의적인 공격에 강한 성질을 제공합니다.

  • Carter-Wegman Hash: 무작위성을 보장해 충돌 가능성을 줄이기 위한 해시 함수입니다. 보안적 특성이 뛰어나며, 데이터 스트림과 암호화에 사용됩니다.

해시 함수의 선택 기준

해시 함수는 용도에 따라 선택 기준이 달라집니다.

  • 속도가 중요한 경우: FNV, MurmurHash, CityHash 등 비암호화 해시 함수가 적합합니다.
  • 보안이 중요한 경우: SHA-2, SHA-3, Blake2와 같은 암호화 해시 함수가 적합합니다.
  • 오류 검출: CRC, Adler-32와 같은 체크섬 해시 함수가 유용합니다.
  • 무작위성과 충돌 방지: 유니버설 해시 함수가 적합합니다.
Buy me a coffee Buy me a coffee
비제네릭 컬렉션LOH와 Chunking을 통한 메모리 최적화