什么是Python中的哈希表

什么是Python中的哈希表？相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

散列表（哈希表）

散列表：所有的元素之間沒有任何關系。元素的存儲位置，是利用元素的關鍵字通過某個函數直接計算出來的。這個一一對應的關系函數稱為散列函數或Hash函數。
采用散列技術將記錄存儲在一塊連續的存儲空間中，稱為散列表或哈希表（Hash Table）。關鍵字對應的存儲位置，稱為散列地址。

散列表是一種面向查找的存儲結構。它最適合求解的問題是查找與給定值相等的記錄。但是對于某個關鍵字能對應很多記錄的情況就不適用，比如查找所有的“男”性。也不適合范圍查找，比如查找年齡20~30之間的人。排序、最大、最小等也不合適。

因此，散列表通常用于關鍵字不重復的數據結構。比如python的字典數據類型。

設計出一個簡單、均勻、存儲利用率高的散列函數是散列技術中最關鍵的問題。
但是，一般散列函數都面臨著沖突的問題。
沖突：兩個不同的關鍵字，通過散列函數計算后結果卻相同的現象。collision。

散列函數的構造方法

好的散列函數：計算簡單、散列地址分布均勻

直接定址法
例如取關鍵字的某個線性函數為散列函數：
f(key) = a*key + b (a,b為常數）數字分析法
抽取關鍵字里的數字，根據數字的特點進行地址分配平方取中法
將關鍵字的數字求平方，再截取部分折疊法
將關鍵字的數字分割后分別計算，再合并計算，一種玩弄數字的手段。除留余數法
最為常見的方法之一。
對于表長為m的數據集合，散列公式為：

f(key) = key mod p (p<=m)
mod：取模（求余數）
該方法最關鍵的是p的選擇，而且數據量較大的時候，沖突是必然的。一般會選擇接近m的質數。隨機數法
選擇一個隨機數，取關鍵字的隨機函數值為它的散列地址。
f(key) = random(key)

總結，實際情況下根據不同的數據特性采用不同的散列方法，考慮下面一些主要問題：

計算散列地址所需的時間關鍵字的長度散列表的大小關鍵字的分布情況記錄查找的頻率

處理散列沖突

開放定址法

就是一旦發生沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。

公式是：

這種簡單的沖突解決辦法被稱為線性探測，無非就是自家的坑被占了，就逐個拜訪后面的坑，有空的就進，也不管這個坑是不是后面有人預定了的。
線性探測帶來的最大問題就是沖突的堆積，你把別人預定的坑占了，別人也就要像你一樣去找坑。

改進的辦法有二次方探測法和隨機數探測法。

再散列函數法
發生沖突時就換一個散列函數計算，總會有一個可以把沖突解決掉，它能夠使得關鍵字不產生聚集，但相應地增加了計算的時間。

鏈接地址法

碰到沖突時，不更換地址，而是將所有關鍵字為同義詞的記錄存儲在一個鏈表里，在散列表中只存儲同義詞子表的頭指針，如下圖：

這樣的好處是，不怕沖突多；缺點是降低了散列結構的隨機存儲性能。本質是用單鏈表結構輔助散列結構的不足。

公共溢出區法
其實就是為所有的沖突，額外開辟一塊存儲空間。如果相對基本表而言，沖突的數據很少的時候，使用這種方法比較合適。

散列表查找實現

下面是一段簡單的實現代碼：

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: Liu Jiang
# Python 3.5
# 忽略了對數據類型，元素溢出等問題的判斷。
class HashTable:
    def __init__(self, size):
        self.elem = [None for i in range(size)]  # 使用list數據結構作為哈希表元素保存方法
        self.count = size  # 最大表長

    def hash(self, key):
        return key % self.count  # 散列函數采用除留余數法

    def insert_hash(self, key):
        """插入關鍵字到哈希表內"""
        address = self.hash(key)  # 求散列地址
        while self.elem[address]:  # 當前位置已經有數據了，發生沖突。
            address = (address+1) % self.count  # 線性探測下一地址是否可用
        self.elem[address] = key  # 沒有沖突則直接保存。

    def search_hash(self, key):
        """查找關鍵字，返回布爾值"""
        star = address = self.hash(key)        
while self.elem[address] != key:
            address = (address + 1) % self.count            
if not self.elem[address] or address == star:  # 說明沒找到或者循環到了開始的位置
                return False
        return True
if __name__ == '__main__':
    list_a = [12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    hash_table = HashTable(12)    
      for i in list_a:
        hash_table.insert_hash(i)    
      for i in hash_table.elem:        
          if i:
           print((i, hash_table.elem.index(i)), end=" ")
    print("\n")

    print(hash_table.search_hash(15))
    print(hash_table.search_hash(33))

散列表查找性能分析

如果沒發生沖突，則其查找時間復雜度為O(1)，屬于最極端的好了。
但是，現實中沖突可不可避免的，下面三個方面對查找性能影響較大：

散列函數是否均勻處理沖突的辦法散列表的裝填因子（表內數據裝滿的程度）

看完上述內容，你們掌握什么是Python中的哈希表的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！