해시 함수와 그 응용

10.1 해시 함수와 해시 테이블 소개

해시 함수와 해시 테이블에 대한 이해를 다시 한 번 다지고 깊이 파헤쳐 보자. 해시 함수는 입력 데이터를 일정 길이의 문자열로 변환하는 알고리즘이야. 해시 함수의 주요 특성:

• 결정론: 동일한 입력은 항상 동일한 결과를 줘야 해.
• 빠른 계산: 해시는 충분히 빠르게 계산되어야 해.
• 비가역성 (암호화 해시 함수의 경우): 해시로부터 원본 데이터를 복원하는 것은 불가능하거나 매우 어려워야 해.
• 균등 분포: 입력 데이터의 작은 변화가 해시에 큰 변화를 가져와야 해.

간단히 말해서, 동일한 객체는 동일한 해시를 가진다. 하지만 두 객체가 같은 해시를 가졌다고 해서 반드시 같은 객체는 아니야. 수학에서는 이것을 필요하지만 충분하지 않은 조건이라고 부르지.

해시 테이블은 데이터를 효율적으로 저장하고 검색하기 위해 해시 함수를 사용하는 데이터 구조야. 해시 테이블은 다음으로 구성돼:

• 데이터를 저장하기 위한 "버킷" 배열.
• 데이터를 어떤 버킷에 넣을지 결정하는 해시 함수.

해시 테이블은 평균적으로 O(1) 시간 복잡도로 데이터를 빠르게 액세스할 수 있어.

실생활에서의 해시 함수 활용

예: 블록체인 기술

블록체인에서 해시 함수는 블록의 고유 식별자를 생성하고 데이터의 무결성을 보장하는 데 사용돼. 각 블록은 이전 블록의 해시를 포함하고 있어, 이로 인해 체인이 생성되고 시스템은 변경에 강해져.

import hashlib
import time

class Block:
    def __init__(self, data, previous_hash):
        self.timestamp = time.time()
        self.data = data
        self.previous_hash = previous_hash
        self.hash = self.calculate_hash()

    def calculate_hash(self):
        hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
        return hashlib.sha256(hash_string.encode()).hexdigest()

# 사용 예시
block1 = Block("트랜잭션 1", "0")
block2 = Block("트랜잭션 2", block1.hash)
print(f"블록 1의 해시: {block1.hash}")
print(f"블록 2의 해시: {block2.hash}")

성능 비교

배열에서 중복을 찾는 문제를 살펴보자. 해시 테이블 사용과 미사용 솔루션을 비교해 보자:

import time

def find_duplicates_with_hash(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

def find_duplicates_without_hash(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

# 성능 테스트
arr = list(range(10000)) + list(range(5000))  # 중복이 있는 배열

start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"해시 테이블 사용시 실행 시간: {end - start} 초")

start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"해시 테이블 미사용시 실행 시간: {end - start} 초")

프로그램을 실행하고 해시 테이블 사용이 특히 큰 배열에서 중복 찾기를 얼마나 가속하는지 확인해 봐.

10.2 실제 문제에서 해시 함수의 응용 예시

1. 비밀번호 해싱

해시 함수는 비밀번호를 안전하게 저장하는 데 사용돼. 비밀번호를 평문으로 저장하는 대신, 시스템은 비밀번호의 해시를 저장해. 사용자가 비밀번호를 입력하면 시스템은 입력된 비밀번호를 해싱하고 데이터베이스에 저장된 해시와 비교해.

구현 예시:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

# 사용 예시:
password = "securepassword"
hashed_password = hash_password(password)
print(f"비밀번호의 해시: {hashed_password}")

2. 데이터 무결성 검사

해시 함수는 파일 및 데이터의 무결성을 검사하는 데 사용돼. 예를 들어 파일이 전송 중에 변경되거나 손상되지 않았는지 확인하는 데 사용돼.

구현 예시:

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

# 사용 예시:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 파일 해시: {file_hash}")

3. 검색 엔진 및 인덱싱

검색 엔진은 인덱스를 만들기 위해 해시 함수를 사용해 정보를 빠르게 검색해. 각 문서는 키워드로 인덱스화되며, 해시 함수는 지정된 단어를 포함하는 문서를 빠르게 찾는 데 도움 준다.

구현 예시:

def create_index(text):
    index = {}
    words = text.split()
    for word in words:
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

# 사용 예시:
text = "This is an example text for indexing"
index = create_index(text)
print(f"인덱스: {index}")

10.3 해시 함수를 사용한 검색 최적화

1. 중복 검색을 위한 해시 테이블 사용

해시 테이블은 요소의 해시 값을 비교해 배열에서 중복을 빠르게 찾을 수 있게 해.

구현 예시:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 사용 예시:
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 출력: [2, 4]

2. 특정 합계를 가지는 쌍 검색 최적화

해시 테이블은 배열에서 주어진 값의 합계가 되는 쌍을 효율적으로 찾을 수 있게 해.

구현 예시:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# 사용 예시:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 출력: [(4, 2), (8, -2)]

10.4 다양한 알고리즘에서 해시 함수의 사용 예시

1. 텍스트에서 단어 수 세기

텍스트에서 각 단어의 출현 횟수를 세기 위해 해시 테이블을 사용해봐.

구현 예시:

def count_words(text):
    word_count = {}
    words = text.split()

    for word in words:
        if word in word_count:
            word_count[word] += 1
        else:
            word_count[word] = 1

    return word_count

# 사용 예시:
text = "this is a test this is only a test"
print(count_words(text))  # 출력: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}

2. 두 배열의 교차점 확인

두 배열이 교차하는지 (공통 요소가 하나라도 있는지) 확인해봐.

구현 예시:

def has_intersection(arr1, arr2):
    set1 = set(arr1)
    for item in arr2:
        if item in set1:
            return True
    return False

# 사용 예시:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2))  # 출력: True
print(has_intersection(arr1, arr3))  # 출력: False

3. 배열 내 요소의 고유성 확인

배열에 고유한 요소만 포함되어 있는지 확인해봐.

구현 예시:

def all_unique(arr):
    seen = set()
    for item in arr:
        if item in seen:
            return False
        seen.add(item)
    return True

# 사용 예시:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1))  # 출력: True
print(all_unique(arr2))  # 출력: False

1

Опрос

해싱,  54 уровень,  5 лекция

недоступен

해싱

해싱

Открыть