Python에서 해시 테이블을 구현하는 방법

해시 테이블은 컴퓨터 과학에서 널리 사용되는 중요한 데이터 구조입니다. 대량의 데이터에서 특정 요소를 빠르게 찾아 삽입하거나 삭제할 수 있습니다. Python을 사용하여 해시 테이블을 구현하면 해시 테이블의 내부 작업 메커니즘에 대한 깊은 이해를 제공할 뿐만 아니라 프로그래밍 능력도 향상시킬 수 있습니다. 이 기사에서는 Python에서 해시 테이블을 구현하는 방법을 자세히 설명합니다.

1. 해시 테이블이란

해시 테이블은 해시 테이블이라고도 하며 키-값 저장 방식입니다. 키를 값의 인덱스 위치에 매핑하여 데이터에 액세스합니다. 기본 작업에는 삽입, 삭제 및 검색이 포함됩니다.

해시 테이블의 핵심 아이디어는 해시 함수를 사용하여 각 키를 고정 크기 테이블에 매핑하는 것입니다. 해시 함수는 임의 길이의 입력 메시지를 고정 길이 출력으로 변환하는 함수입니다. 일반적인 해시 함수에는 MD5, SHA1, SHA256 등이 포함됩니다.

2. 해시 테이블 구현

삽입, 삭제, 검색 등 해시 테이블의 기본 연산을 포함한 간단한 해시 테이블을 Python을 사용하여 구현합니다.

먼저 해시 테이블의 노드를 나타내는 Node 클래스를 정의합니다. 각 노드에는 키와 값이 포함되어 있습니다.

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

다음으로 HashTable 클래스를 정의합니다. Python의 목록을 사용하여 기본 데이터 구조를 구현합니다. 키-값 쌍을 삽입할 때 키를 기반으로 해시 값을 계산하고 해시 테이블의 해당 위치에 키-값 쌍을 저장해야 합니다.

class HashTable:
    def __init__(self):
        self.size = 100
        self.table = [None] * self.size
        
    def hash_func(self, key):
        return sum([ord(c) for c in key]) % self.size
    
    def insert(self, key, value):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            self.table[hash_value] = Node(key, value)
        else:
            cur = self.table[hash_value]
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(key, value)
    
    def search(self, key):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            return None
        else:
            cur = self.table[hash_value]
            while cur is not None:
                if cur.key == key:
                    return cur.val
                else:
                    cur = cur.next
            return None
    
    def delete(self, key):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            return
        elif self.table[hash_value].key == key:
            self.table[hash_value] = self.table[hash_value].next
        else:
            cur = self.table[hash_value]
            while cur.next is not None:
                if cur.next.key == key:
                    cur.next = cur.next.next
                    return
                else:
                    cur = cur.next

위 코드에서 hash_func 메소드는 키를 기준으로 해시값을 계산하고, insert 메소드는 키-값 쌍을 해시 테이블의 해당 위치에 삽입하고, search 메소드는 키를 기준으로 값을 찾아내고, delete 메소드는 키 -값 쌍을 기반으로 해당 키를 삭제합니다.

3. 해시 테이블 테스트

다음으로 위에서 구현한 해시 테이블을 테스트합니다.

ht = HashTable()
ht.insert('apple', 2.5)
ht.insert('banana', 1.3)
ht.insert('orange', 0.7)

print(ht.search('apple')) # 2.5
print(ht.search('banana')) # 1.3
print(ht.search('orange')) # 0.7
print(ht.search('lemon')) # None

ht.delete('apple')
print(ht.search('apple')) # None

위 코드에서는 HashTable 객체 ht를 생성하고 3개의 키-값 쌍을 ht에 삽입합니다. 그런 다음 검색 방법을 사용하여 'apple', 'banana' 및 'orange' 키가 있는 값을 찾고, 'apple' 키가 있는 키-값 쌍을 삭제합니다. 마지막으로 None을 반환해야 하는 'apple' 키가 있는 값을 찾습니다.

4. 요약

이 글에서는 Python으로 해시 테이블을 구현하는 방법을 소개합니다. 해시 테이블의 노드를 표현하기 위해 Node 클래스를 정의하고, 해시 테이블을 표현하기 위해 HashTable 클래스를 정의하고, 삽입, 삭제, 검색 등 해시 테이블의 기본 연산을 구현했습니다. 해시 테이블을 구현함으로써 해시 테이블의 내부 작동 메커니즘을 깊이 이해하고 프로그래밍 능력을 향상시킬 수 있습니다.

위 내용은 Python에서 해시 테이블을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!