Hashing

해싱(Hashing)은 현대 컴퓨터 과학과 프로그래밍에서 가장 중요한 데이터 처리 기법 중 하나이다.
효율적인 데이터 검색과 저장을 가능하게 하는 이 기술은 다양한 애플리케이션에서 핵심적인 역할을 한다.

실제 프로젝트에서는 대부분 언어나 라이브러리에서 제공하는 최적화된 해시 테이블 구현체(파이썬의 딕셔너리나 집합 등)를 사용하게 되지만, 그 내부 동작 원리를 이해하는 것은 여전히 중요하다. 이러한 이해를 바탕으로 더 효율적인 코드를 작성하고, 필요에 따라 커스텀 해싱 솔루션을 개발할 수 있을 것이다.

해싱은 단순한 데이터 구조를 넘어 암호화, 데이터 무결성 검증, 분산 시스템 등 다양한 분야에서 핵심적인 역할을 한다.

해싱이란 무엇인가?

해싱은 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환하는 과정이다.
이 변환을 수행하는 함수를 해시 함수(Hash Function)라고 하며, 이 함수가 반환하는 값을 해시 값(Hash Value) 또는 해시 코드(Hash Code)라고 한다.

쉽게 이해하기 위해 실생활 예시를 생각해보면,
도서관에서 책을 찾을 때, 우리는 도서 분류 번호를 사용한다. 이 번호는 책의 제목, 저자, 내용 등 다양한 정보를 바탕으로 생성된 고유한 식별자이다.
이처럼 해시 함수는 데이터의 특성을 바탕으로 고유한 ‘주소’를 생성하여 데이터를 빠르게 찾을 수 있게 해준다.

해싱의 주요 구성 요소

해싱 시스템의 핵심 구성 요소는 다음과 같다:

  1. 해시 함수(Hash Function)
    해시 함수는 입력 데이터(키)를 고정된 크기의 해시 값으로 변환하는 함수이다.
    좋은 해시 함수는 다음 특성을 가져야 한다:
    1. 결정적(Deterministic): 같은 입력에 대해 항상 같은 해시 값을 반환해야 한다.
    2. 균일 분포(Uniform Distribution): 서로 다른 입력이 동일한 해시 값을 가질 확률을 최소화해야 한다.
    3. 효율적(Efficient): 계산이 빠르고 간단해야 한다.
    4. 충돌 저항성(Collision Resistance): 서로 다른 입력이 같은 해시 값을 가지는 충돌을 최소화해야 한다.
  2. 해시 테이블(Hash Table)
    해시 테이블은 키-값 쌍을 저장하는 데이터 구조로, 해시 함수를 사용하여 키를 배열의 인덱스로 변환한다.
    이 인덱스는 값을 저장하거나, 값이 저장된 위치를 가리키는 포인터가 될 수 있다.
    해시 테이블의 구조는 다음과 같다:
    • 버킷(Bucket): 데이터가 저장되는 배열의 각 요소를 버킷이라고 한다.
    • 슬롯(Slot): 각 버킷에 저장될 수 있는 키-값 쌍의 공간을 슬롯이라고 한다.

해싱의 작동 원리

해싱의 기본 작동 원리는 다음과 같다:

  1. 키 생성: 저장하거나 검색하려는 데이터의 키를 결정한다.
  2. 해시 계산: 해시 함수에 키를 입력하여 해시 값을 계산한다.
  3. 인덱스 매핑: 해시 값을 해시 테이블의 크기에 맞게 조정하여 인덱스를 생성한다(일반적으로 나머지 연산 사용).
  4. 데이터 저장/검색: 계산된 인덱스 위치에 데이터를 저장하거나 검색한다.

예를 들어, 문자열 “apple"을 해싱한다고 가정해보면:

  1. 키: “apple”
  2. 간단한 해시 함수: 각 문자의 ASCII 값을 더하기
    • a (97) + p (112) + p (112) + l (108) + e (101) = 530
  3. 테이블 크기가 100인 경우, 인덱스 = 530 % 100 = 30
  4. “apple” 관련 데이터는 해시 테이블의 30번 위치에 저장된다.

해시 충돌(Hash Collision)과 해결 방법

해시 충돌은 서로 다른 두 개 이상의 키가 동일한 해시 값을 생성할 때 발생한다.
앞서 예시에서 다른 문자열 “mango"가 같은 해시 값 530을 생성한다면, 충돌이 발생하게 된다.

충돌 해결을 위한 주요 방법으로는 다음과 같은 것들이 있다:

개방 주소법(Open Addressing)

충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장하는 방식이다.
주요 기법으로는:

  1. 선형 탐사(Linear Probing)
    충돌 발생 시 순차적으로 다음 버킷을 확인하여 빈 공간을 찾는다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    def insert(key, value, table, hash_func, size):
    index = hash_func(key) % size

    # 충돌 발생 시 선형 탐사
    while table[index] is not None:
        # 이미 같은 키가 있으면 값만 업데이트
        if table[index][0] == key:
            table[index] = (key, value)
            return

        # 다음 버킷으로 이동
        index = (index + 1) % size

    # 빈 버킷에 키-값 쌍 저장
    table[index] = (key, value)

  2. 이차 탐사(Quadratic Probing)
    충돌 발생 시 제곱수만큼 떨어진 버킷을 확인한다.
    이는 선형 탐사에서 발생하는 밀집(clustering) 문제를 줄여준다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    def insert(key, value, table, hash_func, size):
    index = hash_func(key) % size
    i = 0

    # 충돌 발생 시 이차 탐사
    while table[index] is not None:
        if table[index][0] == key:
            table[index] = (key, value)
            return

        # 다음 위치로 이동 (이차 함수 사용)
        i += 1
        index = (hash_func(key) + i*i) % size

    table[index] = (key, value)

  3. 이중 해싱(Double Hashing)
    두 개의 해시 함수를 사용하여 충돌 시 두 번째 해시 함수로 계산한 값만큼 건너뛰며 탐색한다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    def insert(key, value, table, hash_func1, hash_func2, size):
    index = hash_func1(key) % size
    step = hash_func2(key) % (size - 1) + 1  # 0이 아닌 값 보장

    # 충돌 발생 시 이중 해싱
    while table[index] is not None:
        if table[index][0] == key:
            table[index] = (key, value)
            return

        # 두 번째 해시 함수로 계산한 간격만큼 이동
        index = (index + step) % size

    table[index] = (key, value)

체이닝(Chaining)

각 버킷에 연결 리스트(또는 다른 자료구조)를 사용하여 충돌이 발생한 여러 키-값 쌍을 저장하는 방식이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def insert(key, value, table, hash_func, size):
    index = hash_func(key) % size
    
    # 해당 인덱스에 아직 연결 리스트가 없으면 생성
    if table[index] is None:
        table[index] = []
    
    # 이미 같은 키가 있는지 확인
    for i, (k, v) in enumerate(table[index]):
        if k == key:
            # 키가 있으면 값만 업데이트
            table[index][i] = (key, value)
            return
    
    # 키가 없으면 리스트에 새 키-값 쌍 추가
    table[index].append((key, value))

일반적인 해시 함수들

다양한 데이터 유형에 대한 해시 함수가 있다.

몇 가지 대표적인 예를 살펴보면:

  1. 정수를 위한 해시 함수:
    정수 값을 해싱하는 가장 간단한 방법은 모듈로(modulo) 연산을 사용하는 것:

    1
2

    def hash_integer(key, size):
    return key % size

    하지만 이 방법은 크기가 2의 거듭제곱인 테이블에서 하위 비트만 사용하는 문제가 있다.
    이를 개선한 방법으로는:

    1
2
3
4

    def improved_hash_integer(key, size):
    # 곱셈 해시 방법
    A = (math.sqrt(5) - 1) / 2  # 황금 비율에 가까운 값
    return int(size * ((key * A) % 1))

  2. 문자열을 위한 해시 함수
    문자열 해싱의 기본 방법은 각 문자의 ASCII 값을 사용하는 것:

    1
2
3
4
5

    def hash_string_simple(key, size):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % size

    더 효과적인 방법은 다항식 롤링 해시(Polynomial Rolling Hash):

    1
2
3
4
5

    def hash_string_polynomial(key, size, prime=31):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * prime + ord(char)) % size
    return hash_value

해시 테이블 구현하기

이제 앞서 배운 개념을 바탕으로 간단한 해시 테이블을 파이썬으로 구현해보면:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size
        self.count = 0  # 저장된 항목 수
        self.load_factor_threshold = 0.7  # 재해싱 임계값
    
    def _hash_function(self, key):
        # 문자열인 경우 다항식 롤링 해시 사용
        if isinstance(key, str):
            hash_value = 0
            for char in key:
                hash_value = (hash_value * 31 + ord(char)) % self.size
            return hash_value
        # 숫자인 경우 간단한 모듈로 해시 사용
        elif isinstance(key, (int, float)):
            return int(key) % self.size
        # 기타 객체는 파이썬의 내장 해시 함수 사용
        else:
            return hash(key) % self.size
    
    def _resize(self, new_size):
        # 테이블 크기를 조정하고 모든 항목 재해싱
        old_table = self.table
        self.size = new_size
        self.table = [None] * new_size
        self.count = 0
        
        # 기존 항목들을 새 테이블에 재삽입
        for bucket in old_table:
            if bucket:
                for key, value in bucket:
                    self.put(key, value)
    
    def put(self, key, value):
        # 해시 값을 계산하여 인덱스 결정
        index = self._hash_function(key)
        
        # 해당 버킷이 비어있으면 새 리스트 생성
        if self.table[index] is None:
            self.table[index] = []
        
        # 이미 같은 키가 있는지 확인
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                # 키가 있으면 값만 업데이트하고 종료
                self.table[index][i] = (key, value)
                return
        
        # 새 키-값 쌍 추가
        self.table[index].append((key, value))
        self.count += 1
        
        # 로드 팩터 확인 및 필요시 테이블 크기 조정
        load_factor = self.count / self.size
        if load_factor > self.load_factor_threshold:
            self._resize(self.size * 2)
    
    def get(self, key):
        # 해시 값을 계산하여 인덱스 결정
        index = self._hash_function(key)
        
        # 해당 버킷이 비어있으면 None 반환
        if self.table[index] is None:
            return None
        
        # 버킷에서 키를 찾아 값 반환
        for k, v in self.table[index]:
            if k == key:
                return v
        
        # 키를 찾지 못하면 None 반환
        return None
    
    def remove(self, key):
        # 해시 값을 계산하여 인덱스 결정
        index = self._hash_function(key)
        
        # 해당 버킷이 비어있으면 False 반환
        if self.table[index] is None:
            return False
        
        # 버킷에서 키를 찾아 제거
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                self.count -= 1
                
                # 버킷이 비어있으면 None으로 설정
                if not self.table[index]:
                    self.table[index] = None
                
                return True
        
        # 키를 찾지 못하면 False 반환
        return False
    
    def __contains__(self, key):
        return self.get(key) is not None
    
    def __str__(self):
        # 디버깅용 문자열 표현
        result = "{\n"
        for i, bucket in enumerate(self.table):
            if bucket:
                result += f"  {i}: {bucket}\n"
        result += "}"
        return result

이 구현은 체이닝 방식을 사용하고, 로드 팩터에 따라 테이블 크기를 동적으로 조정한.
사용 예시:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 해시 테이블 생성 및 사용 예시
hash_table = HashTable()
hash_table.put("apple", 5)
hash_table.put("banana", 10)
hash_table.put("orange", 15)

print(hash_table.get("apple"))  # 출력: 5
print("banana" in hash_table)   # 출력: True
hash_table.remove("orange")
print(hash_table.get("orange")) # 출력: None

print(hash_table)  # 테이블 내용 출력

해싱의 성능 분석

해시 테이블의 시간 복잡도는 다음과 같다:

  1. 평균 시간 복잡도 (좋은 해시 함수 가정)
    • 삽입(Insert): O(1)
    • 조회(Lookup): O(1)
    • 삭제(Delete): O(1)
  2. 최악의 시간 복잡도 (모든 키가 같은 버킷에 해싱되는 경우)
    • 삽입(Insert): O(n)
    • 조회(Lookup): O(n)
    • 삭제(Delete): O(n)
  3. 공간 복잡도
    • 체이닝: O(n) (n은 저장된 키-값 쌍의 수)
    • 개방 주소법: O(m) (m은 해시 테이블의 크기)

고급 해싱 기법

더 발전된 해싱 기법:

일관된 해싱(Consistent Hashing)

분산 시스템에서 데이터를 여러 서버에 고르게 분배하면서, 서버 추가/제거 시 데이터 재배치를 최소화하는 기법.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import hashlib
import bisect

class ConsistentHash:
    def __init__(self, nodes=None, replicas=100):
        self.replicas = replicas
        self.ring = {}  # 해시 값 -> 노드 매핑
        self.sorted_keys = []  # 정렬된 해시 값 목록
        
        if nodes:
            for node in nodes:
                self.add_node(node)
    
    def _hash(self, key):
        # MD5 해시 함수 사용
        key_str = str(key).encode()
        return int(hashlib.md5(key_str).hexdigest(), 16)
    
    def add_node(self, node):
        # 노드의 여러 복제본을 해시 링에 추가
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            self.ring[key] = node
            bisect.insort(self.sorted_keys, key)
    
    def remove_node(self, node):
        # 노드의 모든 복제본을 해시 링에서 제거
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            if key in self.ring:
                del self.ring[key]
                self.sorted_keys.remove(key)
    
    def get_node(self, key):
        # 키에 해당하는 노드 찾기
        if not self.ring:
            return None
        
        hash_key = self._hash(key)
        # 이진 검색으로 해시 링에서 위치 찾기
        idx = bisect.bisect(self.sorted_keys, hash_key)
        # 링의 끝에 도달하면 처음으로 돌아감
        if idx == len(self.sorted_keys):
            idx = 0
        
        return self.ring[self.sorted_keys[idx]]

# 사용 예시
ch = ConsistentHash(["server1", "server2", "server3"])
print(ch.get_node("user123"))  # 예: "server2"
print(ch.get_node("file456"))  # 예: "server1"

# 노드 추가
ch.add_node("server4")
# 대부분의 키는 여전히 같은 서버에 매핑됨

블룸 필터(Bloom Filter)

원소가 집합에 속하는지 빠르게 판단하는 확률적 자료구조로, 거짓 긍정(false positive)은 가능하지만 거짓 부정(false negative)은 발생하지 않는다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import math
import mmh3  # 설치 필요: pip install mmh3

class BloomFilter:
    def __init__(self, capacity, error_rate=0.001):
        # 최적의 비트 배열 크기와 해시 함수 수 계산
        self.size = self._optimal_size(capacity, error_rate)
        self.hash_count = self._optimal_hash_count(self.size, capacity)
        self.bit_array = [0] * self.size
    
    def _optimal_size(self, capacity, error_rate):
        # 최적의 비트 배열 크기 계산 공식
        size = -capacity * math.log(error_rate) / (math.log(2) ** 2)
        return math.ceil(size)
    
    def _optimal_hash_count(self, size, capacity):
        # 최적의 해시 함수 수 계산 공식
        return math.ceil((size / capacity) * math.log(2))
    
    def add(self, item):
        # 항목을 필터에 추가
        for i in range(self.hash_count):
            # 다양한 시드로 여러 해시 값 생성
            index = mmh3.hash(str(item), i) % self.size
            self.bit_array[index] = 1
    
    def contains(self, item):
        # 항목이 필터에 있는지 확인
        for i in range(self.hash_count):
            index = mmh3.hash(str(item), i) % self.size
            if self.bit_array[index] == 0:
                return False  # 확실히 존재하지 않음
        return True  # 아마도 존재함

# 사용 예시
bloom = BloomFilter(1000)  # 1000개 항목 저장 용량
bloom.add("apple")
bloom.add("banana")
bloom.add("orange")

print(bloom.contains("apple"))   # True
print(bloom.contains("banana"))  # True
print(bloom.contains("grape"))   # False (대부분의 경우)

쿠쿠 해싱(Cuckoo Hashing)

두 개 이상의 해시 함수를 사용하여 충돌을 해결하는 기법으로, 최악의 경우에도 O(1) 조회 시간을 보장한다.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105

class CuckooHash:
    def __init__(self, size=16):
        self.size = size
        self.tables = [None] * size, [None] * size
        self.max_relocations = size  # 무한 루프 방지
    
    def _hash1(self, key):
        # 첫 번째 해시 함수
        return hash(key) % self.size
    
    def _hash2(self, key):
        # 두 번째 해시 함수 (첫 번째와 달라야 함)
        return (hash(key) // self.size) % self.size
    
    def insert(self, key, value):
        # 이미 키가 있는지 확인
        if self.contains(key):
            self.remove(key)
        
        # 키-값 쌍 삽입 시도
        return self._insert(key, value, 0)
    
    def _insert(self, key, value, count):
        # 최대 재배치 횟수 초과 시 재해싱
        if count >= self.max_relocations:
            self._rehash()
            return self.insert(key, value)
        
        # 첫 번째 테이블에 삽입
        pos = self._hash1(key)
        if self.tables[0][pos] is None:
            self.tables[0][pos] = (key, value)
            return True
        
        # 첫 번째 테이블에 있는 항목을 두 번째 테이블로 이동
        old_key, old_value = self.tables[0][pos]
        self.tables[0][pos] = (key, value)
        
		# 두 번째 테이블에 이전 항목 삽입 (재귀적)
		pos = self._hash2(old_key)
		if self.tables[1][pos] is None:
			self.tables[1][pos] = (old_key, old_value)
			return True
		# 두 번째 테이블의 항목을 방출하고 재귀적으로 다시 삽입
		old_key, old_value = self.tables[1][pos]
		self.tables[1][pos] = (old_key, old_value)
		
		# 방출된 항목을 다시 첫 번째 테이블에 삽입 (재귀)
		return self._insert(old_key, old_value, count + 1)
    
    def get(self, key):
        # 첫 번째 테이블에서 검색
        pos = self._hash1(key)
        if self.tables[0][pos] is not None and self.tables[0][pos][0] == key:
            return self.tables[0][pos][1]
        
        # 두 번째 테이블에서 검색
        pos = self._hash2(key)
        if self.tables[1][pos] is not None and self.tables[1][pos][0] == key:
            return self.tables[1][pos][1]
        
        # 키를 찾지 못함
        return None
    
    def contains(self, key):
        return self.get(key) is not None
    
    def remove(self, key):
        # 첫 번째 테이블에서 검색
        pos = self._hash1(key)
        if self.tables[0][pos] is not None and self.tables[0][pos][0] == key:
            self.tables[0][pos] = None
            return True
        
        # 두 번째 테이블에서 검색
        pos = self._hash2(key)
        if self.tables[1][pos] is not None and self.tables[1][pos][0] == key:
            self.tables[1][pos] = None
            return True
        
        # 키를 찾지 못함
        return False
    
    def _rehash(self):
        # 테이블 크기를 두 배로 늘리고 모든 항목 재삽입
        old_tables = self.tables
        self.size *= 2
        self.tables = [None] * self.size, [None] * self.size
        self.max_relocations = self.size
        
        # 모든 항목 재삽입
        for table in old_tables:
            for item in table:
                if item:
                    key, value = item
                    self.insert(key, value)

# 사용 예시
cuckoo = CuckooHash(8)
cuckoo.insert("apple", 5)
cuckoo.insert("banana", 10)
cuckoo.insert("orange", 15)

print(cuckoo.get("apple"))  # 5
print(cuckoo.get("grape"))  # None

해싱 관련 문제 및 해결 전략

해싱을 사용할 때 발생할 수 있는 주요 문제와 해결 전략을 살펴보면:

  1. 충돌 최소화
    충돌이 많이 발생하면 성능이 저하될 수 있다.
    해결 방법:

    • 좋은 해시 함수 선택
    • 적절한 테이블 크기 유지
    • 로드 팩터 관리(일반적으로 0.7 이하)

  2. 재해싱(Rehashing)
    테이블이 너무 꽉 차면 검색 성능이 저하된다.
    이를 해결하기 위해 테이블 크기를 조정하고 모든 항목을 재해싱하는 과정이 필요하다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    def _resize(self, new_size):
    old_table = self.table
    self.size = new_size
    self.table = [None] * new_size
    self.count = 0

    # 모든 항목 재삽입
    for bucket in old_table:
        if bucket:
            for key, value in bucket:
                self.put(key, value)

  3. 보안 관련 문제
    암호화 해시 함수를 사용할 때 다음 주의사항을 고려해야 한다:

    • 비밀번호 해싱 시 솔트(salt) 추가
    • 보안에 중요한 용도로는 SHA-256 이상의 강력한 해시 함수 사용
    • 해시 함수의 느린 버전(bcrypt, Argon2 등) 사용 고려
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

    import hashlib
import os

def hash_password_with_salt(password):
    # 랜덤 솔트 생성
    salt = os.urandom(16)

    # 비밀번호와 솔트 결합하여 해싱
    hash_obj = hashlib.pbkdf2_hmac(
        'sha256',
        password.encode(),
        salt,
        100000,  # 반복 횟수
    )

    # 솔트와 해시를 함께 저장
    return salt + hash_obj

def verify_password_with_salt(stored_data, password):
    # 저장된 데이터에서 솔트 추출
    salt = stored_data[:16]
    stored_hash = stored_data[16:]

    # 입력된 비밀번호의 해시 계산
    hash_obj = hashlib.pbkdf2_hmac(
        'sha256',
        password.encode(),
        salt,
        100000,  # 반복 횟수
    )

    # 해시 비교
    return stored_hash == hash_obj

해싱의 실제 응용 사례

해싱은 다양한 응용 분야에서 활용된다:

  1. 데이터베이스 인덱싱
    데이터베이스에서 해시 인덱스를 사용하여 레코드를 빠르게 검색한다.

    1
2
3
4
5
6
7

    -- MySQL에서 해시 인덱스 생성 예시
CREATE TABLE users (
    id INT PRIMARY KEY,
    username VARCHAR(50),
    email VARCHAR(100),
    INDEX hash_idx (username) USING HASH
);

  2. 캐싱 시스템
    웹 서버에서 자주 요청되는 데이터를 캐싱하는 데 해시 테이블을 사용한다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    # 간단한 캐시 구현 예시
class Cache:
    def __init__(self, capacity=100):
        self.capacity = capacity
        self.cache = {}  # 파이썬의 딕셔너리는 내부적으로 해시 테이블

    def get(self, key):
        return self.cache.get(key)

    def put(self, key, value):
        # 용량 초과 시 가장 오래된 항목 제거
        if len(self.cache) >= self.capacity:
            oldest_key = next(iter(self.cache))
            del self.cache[oldest_key]
        self.cache[key] = value

  3. 암호화 및 보안
    해시 함수는 암호화와 데이터 무결성 검증에 사용된다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    import hashlib

def hash_password(password):
    # SHA-256 해시 함수를 사용한 비밀번호 해싱
    return hashlib.sha256(password.encode()).hexdigest()

def verify_password(stored_hash, password):
    # 입력된 비밀번호의 해시와 저장된 해시 비교
    return stored_hash == hash_password(password)

# 사용 예시
hashed_pw = hash_password("mySecurePassword123")
print(hashed_pw)
print(verify_password(hashed_pw, "mySecurePassword123"))  # True
print(verify_password(hashed_pw, "wrongPassword"))        # False

  4. 중복 검출
    해싱을 사용하여 대용량 데이터에서 중복을 빠르게 찾아낸다.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    def find_duplicates(values):
    seen = set()  # 파이썬의 집합은 내부적으로 해시 테이블
    duplicates = []

    for value in values:
        if value in seen:
            duplicates.append(value)
        else:
            seen.add(value)

    return duplicates

# 사용 예시
data = [1, 2, 3, 2, 4, 5, 3, 6]
print(find_duplicates(data))  # [2, 3]

해싱의 미래와 발전 방향

  1. 양자 저항성 해시 함수
    양자 컴퓨팅의 발전으로 기존 해시 함수가 취약해질 수 있어, 양자 컴퓨터에도 안전한 해시 함수에 대한 연구가 진행 중이다.
  2. 기계 학습과 해싱
    기계 학습 기법을 적용하여 데이터 특성에 맞는 최적의 해시 함수를 자동으로 생성하는 연구가 활발히 진행 중이다.
  3. 분산 해싱 시스템
    대규모 분산 시스템에서 효율적인 데이터 분배와 접근을 위한 고급 해싱 기법이 계속 발전하고 있다.

참고 및 출처