真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

什么是Python中的哈希表

什么是Python中的哈希表?相信很多沒有經(jīng)驗(yàn)的人對此束手無策,為此本文總結(jié)了問題出現(xiàn)的原因和解決方法,通過這篇文章希望你能解決這個問題。

新沂網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,新沂網(wǎng)站設(shè)計(jì)制作,有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為新沂1000多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\成都外貿(mào)網(wǎng)站建設(shè)公司要多少錢,請找那個售后服務(wù)好的新沂做網(wǎng)站的公司定做!

散列表(哈希表)

散列表:所有的元素之間沒有任何關(guān)系。元素的存儲位置,是利用元素的關(guān)鍵字通過某個函數(shù)直接計(jì)算出來的。這個一一對應(yīng)的關(guān)系函數(shù)稱為散列函數(shù)或Hash函數(shù)。
采用散列技術(shù)將記錄存儲在一塊連續(xù)的存儲空間中,稱為散列表或哈希表(Hash Table)。關(guān)鍵字對應(yīng)的存儲位置,稱為散列地址。

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

因此,散列表通常用于關(guān)鍵字不重復(fù)的數(shù)據(jù)結(jié)構(gòu)。比如python的字典數(shù)據(jù)類型。

設(shè)計(jì)出一個簡單、均勻、存儲利用率高的散列函數(shù)是散列技術(shù)中最關(guān)鍵的問題。
但是,一般散列函數(shù)都面臨著沖突的問題。
沖突:兩個不同的關(guān)鍵字,通過散列函數(shù)計(jì)算后結(jié)果卻相同的現(xiàn)象。collision。

散列函數(shù)的構(gòu)造方法

好的散列函數(shù):計(jì)算簡單、散列地址分布均勻

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

f(key) = key mod p (p<=m)
mod:取模(求余數(shù))
該方法最關(guān)鍵的是p的選擇,而且數(shù)據(jù)量較大的時(shí)候,沖突是必然的。一般會選擇接近m的質(zhì)數(shù)。隨機(jī)數(shù)法
選擇一個隨機(jī)數(shù),取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。
f(key) = random(key)

總結(jié),實(shí)際情況下根據(jù)不同的數(shù)據(jù)特性采用不同的散列方法,考慮下面一些主要問題:

計(jì)算散列地址所需的時(shí)間關(guān)鍵字的長度散列表的大小關(guān)鍵字的分布情況記錄查找的頻率

處理散列沖突

開放定址法

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

公式是:

什么是Python中的哈希表

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

改進(jìn)的辦法有二次方探測法和隨機(jī)數(shù)探測法。

再散列函數(shù)法
發(fā)生沖突時(shí)就換一個散列函數(shù)計(jì)算,總會有一個可以把沖突解決掉,它能夠使得關(guān)鍵字不產(chǎn)生聚集,但相應(yīng)地增加了計(jì)算的時(shí)間。

鏈接地址法

碰到?jīng)_突時(shí),不更換地址,而是將所有關(guān)鍵字為同義詞的記錄存儲在一個鏈表里,在散列表中只存儲同義詞子表的頭指針,如下圖:

什么是Python中的哈希表

這樣的好處是,不怕沖突多;缺點(diǎn)是降低了散列結(jié)構(gòu)的隨機(jī)存儲性能。本質(zhì)是用單鏈表結(jié)構(gòu)輔助散列結(jié)構(gòu)的不足。

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

什么是Python中的哈希表

散列表查找實(shí)現(xiàn)

下面是一段簡單的實(shí)現(xiàn)代碼:

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

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

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

    def search_hash(self, key):
        """查找關(guān)鍵字,返回布爾值"""
        star = address = self.hash(key)        
while self.elem[address] != key:
            address = (address + 1) % self.count            
if not self.elem[address] or address == star:  # 說明沒找到或者循環(huán)到了開始的位置
                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))

散列表查找性能分析

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

散列函數(shù)是否均勻處理沖突的辦法散列表的裝填因子(表內(nèi)數(shù)據(jù)裝滿的程度)

看完上述內(nèi)容,你們掌握什么是Python中的哈希表的方法了嗎?如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容,歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道,感謝各位的閱讀!


名稱欄目:什么是Python中的哈希表
本文路徑:http://weahome.cn/article/jghcsg.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220(工作日)

18980820575(7×24)

提交需求

返回頂部