散列表(哈希表)

　　散列表：所有的元素之間沒(méi)有任何關(guān)系。元素的存儲(chǔ)位置，是利用元素的關(guān)鍵字通過(guò)某個(gè)函數(shù)直接計(jì)算出來(lái)的。這個(gè)一一對(duì)應(yīng)的關(guān)系函數(shù)稱(chēng)為散列函數(shù)或Hash函數(shù)。

　　采用散列技術(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中，稱(chēng)為散列表或哈希表(Hash Table)。關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)位置，稱(chēng)為散列地址。

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

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

　　設(shè)計(jì)出一個(gè)簡(jiǎn)單、均勻、存儲(chǔ)利用率高的散列函數(shù)是散列技術(shù)中最關(guān)鍵的問(wèn)題。

　　但是，一般散列函數(shù)都面臨著沖突的問(wèn)題。

　　沖突：兩個(gè)不同的關(guān)鍵字，通過(guò)散列函數(shù)計(jì)算后結(jié)果卻相同的現(xiàn)象。collision。

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

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

　　直接定址法

　　例如取關(guān)鍵字的某個(gè)線性函數(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ù)法

　　最為常見(jiàn)的方法之一。

　　對(duì)于表長(zhǎng)為m的數(shù)據(jù)集合，散列公式為：

　　f(key) = key mod p (p<=m)

　　mod：取模(求余數(shù))

　　該方法最關(guān)鍵的是p的選擇，而且數(shù)據(jù)量較大的時(shí)候，沖突是必然的。一般會(huì)選擇接近m的質(zhì)數(shù)。隨機(jī)數(shù)法

　　選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。

　　f(key) = random(key)

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

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

　　處理散列沖突

　　開(kāi)放定址法

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

　　公式是：

　　這種簡(jiǎn)單的沖突解決辦法被稱(chēng)為線性探測(cè)，無(wú)非就是自家的坑被占了，就逐個(gè)拜訪后面的坑，有空的就進(jìn)，也不管這個(gè)坑是不是后面有人預(yù)定了的。

　　線性探測(cè)帶來(lái)的最大問(wèn)題就是沖突的堆積，你把別人預(yù)定的坑占了，別人也就要像你一樣去找坑。

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

　　再散列函數(shù)法

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

　　鏈接地址法

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

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

　　相關(guān)推薦：《Python視頻教程》

　　公共溢出區(qū)法

　　其實(shí)就是為所有的沖突，額外開(kāi)辟一塊存儲(chǔ)空間。如果相對(duì)基本表而言，沖突的數(shù)據(jù)很少的時(shí)候，使用這種方法比較合適。

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

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

　　#!/usr/bin/env python

　　# -*- coding:utf-8 -*-

　　# Author: Liu Jiang

　　# Python 3.5

　　# 忽略了對(duì)數(shù)據(jù)類(lèi)型，元素溢出等問(wèn)題的判斷。

　　class HashTable:

　　def __init__(self, size):

　　self.elem = [None for i in range(size)] # 使用list數(shù)據(jù)結(jié)構(gòu)作為哈希表元素保存方法

　　self.count = size # 最大表長(zhǎng)

　　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 # 線性探測(cè)下一地址是否可用

　　self.elem[address] = key # 沒(méi)有沖突則直接保存。

　　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: # 說(shuō)明沒(méi)找到或者循環(huán)到了開(kāi)始的位置

　　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))

　　散列表查找性能分析

　　如果沒(méi)發(fā)生沖突，則其查找時(shí)間復(fù)雜度為O(1)，屬于最極端的好了。

　　但是，現(xiàn)實(shí)中沖突可不可避免的，下面三個(gè)方面對(duì)查找性能影響較大：

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