Bagaimana untuk melaksanakan jadual hash dalam Python

Jadual cincang ialah struktur data penting yang digunakan secara meluas dalam sains komputer. Ia boleh mencari, memasukkan atau memadam elemen tertentu dengan cepat dalam jumlah data yang besar. Menggunakan Python untuk melaksanakan jadual cincang bukan sahaja boleh memberikan anda pemahaman yang mendalam tentang mekanisme kerja dalaman jadual cincang, tetapi juga meningkatkan kebolehan pengaturcaraan anda. Dalam artikel ini, kami akan memperincikan cara melaksanakan jadual hash dalam Python.

1. Apakah itu jadual cincang

Jadual cincang juga dipanggil jadual cincang, ia ialah kaedah penyimpanan nilai kunci. Ia mengakses data dengan memetakan kunci kepada kedudukan indeks nilai. Operasi asasnya termasuk memasukkan, memadam dan mencari.

Idea teras jadual cincang ialah menggunakan fungsi cincang untuk memetakan setiap kunci kepada jadual bersaiz tetap. Fungsi cincang ialah fungsi yang menukarkan mesej input dengan panjang sewenang-wenangnya kepada output panjang tetap. Fungsi cincang biasa termasuk MD5, SHA1, SHA256, dsb.

2. Melaksanakan jadual cincang

Kami menggunakan Python untuk melaksanakan jadual cincang mudah, termasuk operasi asas jadual cincang, seperti sisipan, pemadaman dan carian.

Pertama tentukan kelas Nod untuk mewakili nod jadual cincang. Setiap nod mengandungi kunci dan nilai.

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

Seterusnya, tentukan kelas HashTable Kami menggunakan senarai Python untuk melaksanakan struktur data asas. Apabila memasukkan pasangan nilai kunci, kita perlu mengira nilai cincang berdasarkan kunci dan simpan pasangan nilai kunci di lokasi yang sepadan dalam jadual cincang.

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

Dalam kod di atas, kaedah hash_func mengira nilai cincang berdasarkan kekunci, kaedah sisipan memasukkan pasangan nilai kunci ke dalam kedudukan yang sepadan dalam jadual cincang, kaedah carian mencari nilai berdasarkan kunci, dan kaedah padam berdasarkan kekunci Padam pasangan nilai kunci yang sepadan.

3. Menguji jadual cincang

Seterusnya kami menguji jadual cincang yang dilaksanakan di atas.

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

Dalam kod di atas, kami mencipta objek HashTable ht dan memasukkan tiga pasangan nilai kunci ke dalam ht. Kemudian, kami menggunakan kaedah carian untuk mencari nilai dengan kunci 'epal', 'pisang' dan 'oren', dan memadamkan pasangan nilai kunci dengan kunci 'epal'. Akhir sekali, kami mencari nilai dengan kunci 'epal', yang sepatutnya mengembalikan Tiada.

4. Ringkasan

Artikel ini memperkenalkan cara melaksanakan jadual cincang dalam Python. Kami menentukan kelas Nod untuk mewakili nod jadual cincang, dan kemudian menentukan kelas HashTable untuk mewakili jadual cincang dan melaksanakan operasi asas jadual cincang, seperti sisipan, pemadaman dan carian. Dengan melaksanakan jadual cincang, kami dapat memahami dengan mendalam mekanisme kerja dalaman jadual cincang dan meningkatkan keupayaan pengaturcaraan kami.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan jadual hash dalam Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!