Bagaimana untuk menulis algoritma carian hash dalam Python?

Bagaimana untuk menulis algoritma carian hash dalam Python?

Algoritma carian hash, juga dikenali sebagai algoritma carian hash, ialah kaedah carian data berdasarkan jadual hash. Berbanding dengan algoritma carian tradisional seperti carian linear dan carian binari, algoritma carian hash mempunyai kecekapan carian yang lebih tinggi. Dalam Python, kita boleh menggunakan kamus untuk melaksanakan jadual hash dan kemudian melaksanakan carian hash.

Idea asas algoritma carian cincang adalah untuk menukar kata kunci untuk dicari kepada nilai indeks melalui fungsi cincang, dan kemudian cari data yang sepadan dalam jadual cincang berdasarkan nilai indeks. Dalam jadual cincang, setiap nilai indeks sepadan dengan baldi dan setiap baldi menyimpan satu atau lebih kata kunci. Konflik berlaku apabila berbilang kata kunci dipetakan kepada nilai indeks yang sama. Untuk menyelesaikan konflik, kaedah biasa ialah menggunakan kaedah alamat rantaian untuk memautkan kata kunci yang bercanggah dalam senarai terpaut.

Berikut ialah contoh algoritma carian cincang mudah yang ditulis dalam Python:

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]  # 使用列表作为哈希表的桶
    
    def _hash_function(self, key):
        return key % self.size  # 哈希函数采用取余方式
    
    def insert(self, key, value):
        index = self._hash_function(key)
        self.table[index].append((key, value))  # 将关键字和值作为一个元组插入哈希表桶中
    
    def search(self, key):
        index = self._hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]  # 返回关键字对应的值
        return None  # 若关键字不存在，则返回None

# 示例用法
hash_table = HashTable()
hash_table.insert(1, 'apple')
hash_table.insert(2, 'banana')
hash_table.insert(11, 'orange')

print(hash_table.search(1))  # 输出: apple
print(hash_table.search(2))  # 输出: banana
print(hash_table.search(3))  # 输出: None
print(hash_table.search(11)) # 输出: orange

Dalam contoh di atas, kami mentakrifkan kelas jadual cincangHashTable, yang mengandungi fungsi cincang, sisipan dan operasi carian. Fungsi cincang menggunakan kaedah baki mudah untuk menukar kata kunci kepada nilai indeks yang sepadan. Operasi sisipan memasukkan kunci dan nilai sebagai tuple ke dalam baldi yang sepadan dengan indeks. Operasi carian merentasi baldi indeks yang sepadan, mencari tupel yang sepadan dengan kata kunci dan mengembalikan nilai yang sepadan. Jika kata kunci tidak wujud, Tiada dikembalikan.

Melalui contoh di atas, kita dapat melihat pelaksanaan mudah algoritma carian hash. Dalam amalan, fungsi cincang yang lebih kompleks dan kaedah penyelesaian konflik boleh dipilih berdasarkan keperluan khusus dan ciri data. Pada masa yang sama, operasi seperti pengembangan dinamik jadual cincang juga boleh dilakukan untuk meningkatkan kecekapan carian.

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