一破托、關(guān)于哈希表

1.哈希表的定義

散列表（Hash table霍比，也叫哈希表）擂红，是根據(jù)關(guān)鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說祝谚，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄宪迟，以加快查找的速度。把關(guān)鍵碼值轉(zhuǎn)化為數(shù)組下標的映射函數(shù)叫做散列函數(shù)（“Hash 函數(shù)”）交惯，存放記錄的數(shù)組叫做散列表次泽，散列函數(shù)計算得到的值叫做散列值。（散列表用的是數(shù)組支持按照下標隨機訪問數(shù)據(jù)的特性席爽，所以散列表其實就是數(shù)組的一種擴展意荤，由數(shù)組演化而來。）
如下圖

2.散列函數(shù)

從定義里只锻，可以看出散列函數(shù)十分關(guān)鍵玖像，一般我們定義散列函數(shù)為 hash(key)，其中 key是關(guān)鍵碼值 (Key value)齐饮，hash(key) 的值表示經(jīng)過散列函數(shù)計算得到的散列值捐寥。

散列函數(shù)設(shè)計的基本要求：
1. 散列值是一個非負整數(shù)笤昨；
2. 如果 key1 = key2，那么 hash(key1) == hash(key2)握恳；
3. 如果 key1 ≠ key2咬腋，那么 hash(key1) ≠ hash(key2)。
工業(yè)界著名哈希算法：MD5睡互、SHA根竿、CRC

構(gòu)建哈希函數(shù)的幾種方法：
1.直接定址法
取關(guān)鍵字或者關(guān)鍵字的某個線性函數(shù)為Hash地址。

2.平方取中法
對關(guān)鍵字進行平方運算就珠，然后取結(jié)果的中間幾位作為Hash地址寇壳。假如有以下關(guān)鍵字序列{421，423妻怎，436}壳炎，平方之后的結(jié)果為{177241，178929逼侦，190096}匿辩，那么可以取{72，89榛丢，00}作為Hash地址铲球。

3.折疊法
將關(guān)鍵字拆分成幾部分，然后將這幾部分組合在一起晰赞，以特定的方式進行轉(zhuǎn)化形成Hash地址稼病。假如知道圖書的ISBN號為8903-241-23，可以將address(key)=89+03+24+12+3作為Hash地址掖鱼。

4.除留取余法
如果知道Hash表的最大長度為m然走，可以取不大于m的最大質(zhì)數(shù)p，然后對關(guān)鍵字進行取余運算戏挡，address(key)=key%p芍瑞。在這里p的選取非常關(guān)鍵，p選擇的好的話褐墅，能夠最大程度地減少沖突拆檬，p一般取不大于m的最大質(zhì)數(shù)。

5.數(shù)字分析法
假設(shè)關(guān)鍵字是以r為基的數(shù)掌栅，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的秩仆，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。

6.隨機數(shù)法
選擇一個隨機函數(shù)猾封，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址澄耍。通常用于關(guān)鍵字長度不等時采用此法。

3.散列沖突（哈希沖突）

在上面的要求3里面，實際上只存在理論的可能性齐莲，在真實的情況下痢站，要想找到一個不同的 key 對應(yīng)的散列值都不一樣的散列函數(shù)，幾乎是不存在的选酗。像上述三種工業(yè)界的算法阵难，也都無法避免這種情況，這種情況稱為散列沖突芒填。并且呜叫，數(shù)組存儲空間的有限，也會加大散列沖突的概率殿衰。

比如朱庆，在新華字典里，你本來查找的是“按”闷祥，但是卻找到“安”字娱颊，你又得向后翻一兩頁，才能找到“按”凯砍。在計算機里面同理箱硕。如果想要完全避開這種情況的出現(xiàn)，只能給每個字典去新開一頁悟衩，然后每個字在索引里面都有對應(yīng)的頁碼剧罩，這樣就可以完全避免沖突，但是其會導(dǎo)致空間增大局待，這與我們所說的存儲空間有限有些矛盾斑响。

因此，我們我們需要使用一些方法來解決散列沖突問題钳榨。解決方法主要有開放定址法(open addressing)、再哈希法纽门、鏈地址法（拉鏈法(Open Hashing)）和建立一個公共溢出區(qū)四種方法薛耻。

（1）開放定址法(open addressing)

核心思想是：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎(chǔ)赏陵，產(chǎn)生另一個哈希地址p1饼齿，如果p1仍然沖突，再以p為基礎(chǔ)蝙搔，產(chǎn)生另一個哈希地址p2缕溉，…，直到找出一個不沖突的哈希地址pi 吃型，將相應(yīng)元素存入其中证鸥。這種方法有一個通用的再散列函數(shù)形式：Hi=(H(key)+di)%m i=1，2，…枉层，n,其中H（key）為哈希函數(shù)泉褐，m 為表長，di稱為增量序列鸟蜡。增量序列的取值方式不同膜赃，相應(yīng)的再散列方式也不同。主要有以下三種：

1) 線性探測再散列

di=1揉忘，2跳座，3，…泣矛，m-1
這種方法的特點是：沖突發(fā)生時躺坟，順序查看表中下一單元觅彰，直到找出一個空單元或查遍全表啊终。

2) 二次探測再散列

di=1²扣甲，-1²轴脐，2²细诸，-2²园爷，…镜会，k²巾陕，-k² ( k<=m/2)
這種方法的特點是：沖突發(fā)生時魂奥，在表的左右進行跳躍式探測菠剩，比較靈活。

3) 偽隨機探測再散列

di=偽隨機數(shù)序列耻煤。
具體實現(xiàn)時具壮，應(yīng)建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m）哈蝇，并給定一個隨機數(shù)做起點棺妓。

線性探測再散列的優(yōu)點是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址炮赦，而二次探測再散列和偽隨機探測再散列則不一定怜跑。

(2) 再哈希法

這種方法是同時構(gòu)造多個不同的哈希函數(shù)：
Hi=RH1（key），i=1吠勘，2,3性芬，…,n.
當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……剧防，直到?jīng)_突不再產(chǎn)生植锉。這種方法不易產(chǎn)生聚集，但增加了計算時間峭拘。

(3) 拉鏈法

基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表俊庇，并將單鏈表的頭指針存在哈希表的第i個單元中狮暑，因而查找、插入和刪除主要在同義詞鏈中進行暇赤。若選定的散列表長度為m心例，則可將散列表定義為一個由m個頭指針組成的指針數(shù)組T[0..m-1]。凡是散列地址為i的結(jié)點鞋囊，均插入到以T[i]為頭指針的單鏈表中止后。T中各分量的初值均應(yīng)為空指針。鏈地址法適用于經(jīng)常進行插入和刪除的情況溜腐。

(4) 建立公共溢出區(qū)

基本思想是：將哈希表分為基本表和溢出表兩部分译株，凡是和基本表發(fā)生沖突的元素，一律填入溢出表.(注意：在這個方法里面是把元素分開兩個表來存儲)

4.關(guān)于哈希表的性能

由于哈希表高效的特性挺益，查找或者插入的情況在大多數(shù)情況下可以達到O(1)歉糜，時間主要花在計算hash上，當(dāng)然也有最壞的情況就是hash值全都映射到同一個地址上望众，這樣哈希表就會退化成鏈表匪补，查找的時間復(fù)雜度變成O(n)，但是這種情況比較少烂翰，只要不要把hash計算的公式外漏出去并且有人故意攻擊（有興趣的人可以搜一下基于哈希沖突的拒絕服務(wù)攻擊）夯缺，一般也不會出現(xiàn)這種情況。

哈希沖突攻擊導(dǎo)致退化成鏈表

二甘耿、leetcode編程練習(xí)

第一題（兩數(shù)之和（1））：
給定一個整數(shù)數(shù)組 nums 和一個目標值 target踊兜，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)，并返回他們的數(shù)組下標佳恬。

你可以假設(shè)每種輸入只會對應(yīng)一個答案捏境。但是，你不能重復(fù)利用這個數(shù)組中同樣的元素毁葱。

示例:
給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
代碼：

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """        
        dict1 = {}
        lengh = len(nums)
    #遍歷一遍列表其時間復(fù)雜度為O(n)
        for index in range(lengh):
            #目標值減去第一個值得到另一個數(shù)值
            num = target - nums[index]
            
             #如果在字典中則返回
            if num in dict1:
                return [dict1[num], index]
            
            #如果num不在字典中垫言，則將第一個數(shù)值及其索引添加在字典中
            else:
                dict1[nums[index]] = index

運行結(jié)果：

第二題（Happy number(202)）：
編寫一個算法來判斷一個數(shù)是不是“快樂數(shù)”。

一個“快樂數(shù)”定義為：對于一個正整數(shù)头谜，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和骏掀，然后重復(fù)這個過程直到這個數(shù)變?yōu)?1，也可能是無限循環(huán)但始終變不到 1柱告。如果可以變?yōu)?1，那么這個數(shù)就是快樂數(shù)笑陈。

示例:

輸入: 19
輸出: true
解釋: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

代碼：

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        dict1 = {}
        while True:
            l = list(map(int,list(str(n))))
            m = 0
            for i in l:
                m += i**2
            if m in dict1:
                print(dict1)
                return False
            if m == 1:
                print(dict1)
                return True
            dict1[m] = m
            n = m

運行結(jié)果：

參考內(nèi)容：
https://www.cnblogs.com/yangecnu/p/Introduce-Hashtable.html
http://www.reibang.com/p/dbe7a1ea5928
http://www.cnblogs.com/s-b-b/p/6208565.html
https://blog.csdn.net/My_heart_/article/details/52442573
https://time.geekbang.org/column/article/64233