說來慚愧酪惭，本人在幾年前就接觸了數(shù)據(jù)結(jié)構(gòu)汉买，對(duì)哈希表的認(rèn)識(shí)一直都比較模糊，在日常的學(xué)習(xí)工作中沒少用到這一數(shù)據(jù)結(jié)構(gòu)邻悬，比如像是python語言中的dict症昏，或者是C++中的STL map，這段時(shí)間父丰，我自己又重新學(xué)習(xí)了哈希表的一些設(shè)計(jì)原理肝谭，總結(jié)了一下，現(xiàn)在記錄在這里蛾扇，就當(dāng)是幫助自己加深對(duì)hash的了解攘烛。
什么是哈希（Hash）表
Hash表也稱散列表，也有直接譯作哈希表镀首，Hash表是一種特殊的數(shù)據(jù)結(jié)構(gòu)坟漱，它同數(shù)組、鏈表以及二叉排序樹等相比較有很明顯的區(qū)別更哄，它能夠快速定位到想要查找的記錄芋齿，而不是與表中存在的記錄的關(guān)鍵字進(jìn)行比較來進(jìn)行查找。這個(gè)源于Hash表設(shè)計(jì)的特殊性成翩，它采用了函數(shù)映射的思想將記錄的存儲(chǔ)位置與記錄的關(guān)鍵字關(guān)聯(lián)起來觅捆，從而能夠很快速地進(jìn)行查找。
哈希表的使用
在這里給出來一組數(shù)據(jù)麻敌，這組數(shù)據(jù)對(duì)應(yīng)有兩列（名字/號(hào)碼）栅炒，正常情況下，如果我們想要對(duì)這種類型的數(shù)據(jù)進(jìn)行存儲(chǔ)术羔，像是int赢赊，string，char等數(shù)據(jù)類型是無法對(duì)這些數(shù)據(jù)進(jìn)行存儲(chǔ)的级历，
張三 13980593357
李四 15828662334
王五 13409821234
張帥 13890583472
在C語言中有一種數(shù)據(jù)類型叫做結(jié)構(gòu)體（struct）释移，我們首先考慮的是定義一個(gè)結(jié)構(gòu)體，在結(jié)構(gòu)體中對(duì)這兩種數(shù)據(jù)進(jìn)行定義鱼喉，然后再將這些聯(lián)系人的數(shù)據(jù)信息存儲(chǔ)在一個(gè)鏈表中秀鞭，通過遍歷鏈表的方式趋观，對(duì)每一個(gè)數(shù)據(jù)存儲(chǔ)單元（struct）進(jìn)行訪問和讀寫。不過這樣的一個(gè)劣勢(shì)就是锋边，時(shí)間復(fù)雜度為O(n)皱坛，因?yàn)槲覀冃枰獙?duì)鏈表進(jìn)行從頭到尾的遍歷，即便是通過二分查找的方式進(jìn)行訪問查找豆巨，也只能夠?qū)r(shí)間復(fù)雜度降為O(log n).
那么有沒有一種數(shù)據(jù)結(jié)構(gòu)能夠?qū)⒉檎业臅r(shí)間復(fù)雜度進(jìn)一步降低呢剩辟？這里我們可以考慮使用哈希表（hash table）。
Hash表采用一個(gè)映射函數(shù)f :key -> address 將關(guān)鍵字映射到該記錄在表中的存儲(chǔ)位置往扔，從而在想要查找該記錄時(shí)贩猎，可以直接根據(jù)關(guān)鍵字和映射關(guān)系計(jì)算出該記錄在表中的存儲(chǔ)位置，通常情況下萍膛，這種映射關(guān)系稱作為Hash函數(shù)吭服，而通過Hash函數(shù)和關(guān)鍵字計(jì)算出來的存儲(chǔ)位置(注意這里的存儲(chǔ)位置只是表中的存儲(chǔ)位置，并不是實(shí)際的物理地址)稱作為Hash地址蝗罗。比如上述例子中艇棕，假如聯(lián)系人信息采用Hash表存儲(chǔ)，則當(dāng)想要找到“李四”的信息時(shí)串塑，直接根據(jù)“李四”和Hash函數(shù)計(jì)算出Hash地址即可沼琉。下面討論一下Hash表設(shè)計(jì)中的幾個(gè)關(guān)鍵問題。
哈希函數(shù)的設(shè)計(jì)
Hash函數(shù)設(shè)計(jì)的好壞直接影響到對(duì)Hash表的操作效率桩匪。
例如對(duì)上述的聯(lián)系人信息進(jìn)行存儲(chǔ)時(shí)打瘪，采用的Hash函數(shù)為：姓名的每個(gè)字的拼音開頭大寫字母的ASCII碼之和。
address(張三)=ASCII(Z)+ASCII(S)=90+83=173;
address(李四)=ASCII(L)+ASCII(S)=76+83=159;
address(王五)=ASCII(W)+ASCII(W)=87+87=174;
address(張帥)=ASCII(Z)+ASCII(S)=90+83=173;
假如只有這4個(gè)聯(lián)系人信息需要進(jìn)行存儲(chǔ)傻昙，這個(gè)Hash函數(shù)設(shè)計(jì)的很糟糕闺骚。
首先，它浪費(fèi)了大量的存儲(chǔ)空間妆档。因?yàn)榧偃绮捎胏har型數(shù)組存儲(chǔ)聯(lián)系人信息的話葛碧，每個(gè)人的信息需要12個(gè)字節(jié)來存儲(chǔ)（手機(jī)號(hào)為11位，數(shù)值上為100多億过吻，2^64 =1.844674407371 * 10^19，2^32 = 4294967296蔗衡，所以需要64位也就是8個(gè)字節(jié)來存儲(chǔ)手機(jī)號(hào)纤虽。每個(gè)漢字占兩個(gè)字節(jié)，兩個(gè)漢字占四個(gè)字節(jié)绞惦。所以總共需要8 + 4 = 12Byte）這樣的話逼纸，至少需要開辟174*12字節(jié)的空間。然而空間利用率只有4/174济蝉，不到3%杰刽。
另外菠发，根據(jù)Hash函數(shù)計(jì)算結(jié)果之后，address(張三)和address(張帥)具有相同的地址贺嫂，這種現(xiàn)象稱作沖突滓鸠，對(duì)于174個(gè)存儲(chǔ)空間中只需要存儲(chǔ)4條記錄就發(fā)生了沖突，這樣的Hash函數(shù)設(shè)計(jì)是很不合理的第喳。所以在構(gòu)造Hash函數(shù)時(shí)應(yīng)盡量考慮關(guān)鍵字的分布特點(diǎn)來設(shè)計(jì)函數(shù)使得Hash地址隨機(jī)均勻地分布在整個(gè)地址空間當(dāng)中糜俗。
通常有以下幾種構(gòu)造Hash函數(shù)的方法：
直接定址法
取關(guān)鍵字或者關(guān)鍵字的某個(gè)線性函數(shù)作為Hash地址，即address(key) = a*key + b; 如果知道學(xué)生的學(xué)號(hào)是從2000開始曲饱，最大為4000悠抹，則可以將address(key) =key-2000作為Hash地址。
平方取中法
對(duì)關(guān)鍵字進(jìn)行平方計(jì)算扩淀，然后取結(jié)果的中間幾位作為Hash地址楔敌，假如有以下關(guān)鍵字序列{421，423驻谆，436}卵凑，平方之后的結(jié)果為{177241，178929旺韭，190096}氛谜，那么可以取中間的兩位數(shù){72，89区端，00}作為Hash地址值漫。
折疊法
將關(guān)鍵字拆分成幾個(gè)部分，然后將這幾個(gè)部分組合在一起织盼，以特定的方式進(jìn)行轉(zhuǎn)化形成Hash地址杨何。例如假如知道某圖書的SBN號(hào)為：8903-241-23，可以將address(key)=89+03+24+12+3作為Hash地址沥邻。
除留取余法
如果知道Hash表的最大長(zhǎng)度為m危虱，可以取不大于m的最大質(zhì)數(shù)p，然后對(duì)關(guān)鍵字進(jìn)行取余運(yùn)算唐全，address(key)=key % p埃跷。
在這里p的選取非常關(guān)鍵，p選擇的好的話邮利，能夠最大程度地減少?zèng)_突弥雹，p一般取不大于m的最大質(zhì)數(shù)。
Hash表大小的確定
Hash表大小的確定非常關(guān)鍵延届，如果Hash表的空間遠(yuǎn)遠(yuǎn)大于最后實(shí)際存儲(chǔ)的記錄個(gè)數(shù)剪勿，就會(huì)造成較大的空間浪費(fèi)。如果選取小了的話方庭，則容易造成沖突厕吉。在實(shí)際情況中酱固，一般需要根據(jù)最終記錄存儲(chǔ)個(gè)數(shù)和關(guān)鍵字的分布特點(diǎn)來確定Hash表的大小。還有一種情況時(shí)可能事先不知道最終需要存儲(chǔ)的記錄個(gè)數(shù)头朱，則需要?jiǎng)討B(tài)維護(hù)Hash表的容量运悲，此時(shí)可能需要重新計(jì)算Hash地址。
沖突的解決
如果產(chǎn)生了Hash沖突髓窜，就需要辦法來解決扇苞，通常有如下兩種方法：
開放定址法
即當(dāng)一個(gè)關(guān)鍵字和另一個(gè)關(guān)鍵字發(fā)生沖突時(shí)，使用某種探測(cè)技術(shù)在Hash表中形成一個(gè)探測(cè)序列寄纵，然后沿著這個(gè)探測(cè)序列依次查找下去鳖敷，當(dāng)碰到一個(gè)空的單元時(shí)，則插入其中程拭。比較常用的探測(cè)方法有線性探測(cè)法定踱，比如有一組關(guān)鍵字 {12，13恃鞋，25崖媚，23，38恤浪，34畅哑，6，84水由，91}荠呐，Hash表長(zhǎng)為14，Hash函數(shù)為address(key)=key%11 砂客，當(dāng)插入12泥张，13，25時(shí)可以直接插入鞠值，而當(dāng)插入23時(shí)媚创，地址1被占用了，因此沿著地址1依次往下探測(cè)(探測(cè)步長(zhǎng)可以根據(jù)情況而定)彤恶，直到探測(cè)到地址4钞钙，發(fā)現(xiàn)為空，則將23插入其中声离。
鏈地址法
采用數(shù)組和鏈表相結(jié)合的辦法歇竟，將Hash地址相同的記錄存儲(chǔ)在一張線性表中，而每張表的表頭的序號(hào)即為計(jì)算得到的Hash地址抵恋。如上述例子中，采用鏈地址法形成的Hash表存儲(chǔ)表示為：
Hash表的平均查找長(zhǎng)度
Hash表的平均查找長(zhǎng)度包括查找成功時(shí)候的平均查找長(zhǎng)度和查找失敗時(shí)候的平均查找長(zhǎng)度宝磨。
查找不成功時(shí)的平均查找長(zhǎng)度相當(dāng)于在表中查找元素不成功時(shí)的平均比較次數(shù)弧关，可以理解為向表中插入某個(gè)元素盅安，該元素在每個(gè)位置都有可能，然后計(jì)算出在每個(gè)位置能夠插入時(shí)需要比較的次數(shù)世囊，再除以表長(zhǎng)即為查找不成功時(shí)的平均查找長(zhǎng)度别瞭。
例
這里我們將關(guān)鍵字序列{7,8,30,11,18,9,14}散列存儲(chǔ)到散列表中。散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一維數(shù)組株憾，長(zhǎng)度為10蝙寨，即{0,1,2,3,4,5,6,7,8,9}.散列函數(shù)為：H(key) = (key * 3) % 7，處理沖突采用了線性探測(cè)再散列法嗤瞎。
Step 1 求散列表
H(7) = (7*3)%7 = 0
H(8) = (8*3)%7 = 0
H(30) = (30*3)%7 = 6
H(11) = (11*3)%7 = 5
H(18) = (18*3)%7 = 5
H(9) = (9*3)%7 = 6
H(14) = (14*3)%7 = 0
按關(guān)鍵字序列順序依次向哈希表中填入墙歪，發(fā)生沖突后按照“線性探測(cè)”探測(cè)到第一個(gè)空位置填入。
H(7) = 0贝奇，key = 7應(yīng)插在第0個(gè)位置虹菲，因?yàn)榈?個(gè)位置為空，可以直接插入掉瞳。
H(8) = 3毕源，key = 8應(yīng)插在第3個(gè)位置，因?yàn)榈?個(gè)位置為空陕习，可以直接插入霎褐。
H(30) = 6，key = 30應(yīng)插在第6個(gè)位置该镣，因?yàn)榈?個(gè)位置為空冻璃，可以直接插入。
H(11) = 5拌牲，key = 11應(yīng)插在第5個(gè)位置俱饿，因?yàn)榈?個(gè)位置為空，可以直接插入塌忽。
H(18) = 5拍埠，key = 18應(yīng)插在第5個(gè)位置，但是第5個(gè)位置已經(jīng)被key=11占據(jù)了土居，所以往后挪一位到第6個(gè)位置枣购，但是第6個(gè)位置被key=30占據(jù)了，再往后挪一位到第7個(gè)位置擦耀，這個(gè)位置是空的棉圈，所以key=18就插到這個(gè)位置
H(9) = 6，key = 9應(yīng)插在第6個(gè)位置眷蜓，但是第6個(gè)位置已經(jīng)被key = 30占據(jù)分瘾，所以需要往后挪一位到第7個(gè)位置，但是第7個(gè)位置已經(jīng)被key = 18占據(jù)吁系，所以再往后挪移到第8個(gè)位置德召，這個(gè)位置是空的白魂，所以key = 9就插到這個(gè)位置。
H(14) = 0上岗，key = 14應(yīng)插在第0個(gè)位置福荸，但第0個(gè)位置已被key=7占據(jù)，所以往后挪移一位到第1個(gè)位置肴掷，這個(gè)位置是空的敬锐，所以key=14就插到這個(gè)位置。
最終的插入結(jié)果如下表所示：
address 0 1 2 3 4 5 6 7 8 9
key 7 14 8 11 30 18 9
Step2 求查找成功的平均長(zhǎng)度
查找7呆瞻，H(7) = 0台夺，在0的位置，一下子就找到了7栋烤，查找長(zhǎng)度為1谒养。
查找8，H(8) = 3明郭，在3的位置买窟，一下子就找到了8，查找長(zhǎng)度為1薯定。
查找30始绍，H(30) = 6，在6的位置话侄，一下子就找到了30亏推，查找長(zhǎng)度為1。
查找11年堆，H(11) = 5吞杭，在5的位置，一下子就找到了11变丧，查找長(zhǎng)度為1芽狗。
查找18，H(18) = 5痒蓬，第一次在5的位置沒有找到18童擎，第二次往后挪移一位到6的位置，仍沒有找到攻晒，第三次再往后挪移一位到7的位置顾复，找到了，查找長(zhǎng)度為3鲁捏。
查找9芯砸，H(9) = 6，第一次在6的位置沒找到9，第二次往后挪移一位到7的位置乙嘀，仍沒有找到末购，第三次再往后挪移一位到8的位置，找到了虎谢，查找長(zhǎng)度為3.
查找14，H(14) = 0曹质，第一次在0的位置沒找到14婴噩，第二次往后挪移一位到1的位置，找到了羽德，查找長(zhǎng)度為2几莽。
所以，查找成功的平均查找長(zhǎng)度為(1 + 1 + 1 + 1 + 3 + 3 + 2) / 7 = 12 / 7
Step3 求查找不成功的平均查找長(zhǎng)度
查找不成功宅静，說明要查找的數(shù)字肯定不在上述的散列表中章蚣。
因?yàn)檫@里哈希函數(shù)的模為7，所以要查找的數(shù)的初始地址只可能位于0~6的位置上姨夹。
地址0纤垂，到第一個(gè)關(guān)鍵字為空的地址2需要比較3次，因此查找不成功的次數(shù)為3磷账。比如要查找的數(shù)為28峭沦，H(28) = (28 * 3) % 7 = 0。即28對(duì)應(yīng)的地址是0逃糟，由于存放在0位置的數(shù)是7吼鱼，所以往后挪移一位，發(fā)現(xiàn)在1位置存放的數(shù)是14绰咽，繼續(xù)往后挪一位菇肃，發(fā)現(xiàn)位置2上沒有數(shù)。至此就知道28不在這個(gè)哈希表里取募，即查找28失敗琐谤。
地址1，到第一個(gè)關(guān)鍵字為空的地址2需要比較2次矛辕，因此查找不成功的次數(shù)為2笑跛。
地址2，到第一個(gè)關(guān)鍵字為空的地址2需要比較1次聊品，因此查找不成功的次數(shù)為1飞蹂。
地址3，到第一個(gè)關(guān)鍵字為空的地址4需要比較2次翻屈，因此查找不成功的次數(shù)為2陈哑。
地址4，到第一個(gè)關(guān)鍵字為空的地址4需要比較1次，因此查找不成功的次數(shù)為1惊窖。
地址5刽宪，到第一個(gè)關(guān)鍵字為空的地址9需要比較5次，因此查找不成功的次數(shù)為5界酒。
比如要查找的數(shù)為4圣拄，H(4) = (4 * 3) % 7 = 5，所以從地址5開始查找毁欣，最終發(fā)現(xiàn)地址5庇谆、地址6、地址7凭疮、地址8上存放的數(shù)都不是5饭耳，并且地址9的位置上沒放數(shù)據(jù)，至此可知5不在這個(gè)哈希表里执解。
地址6寞肖，到第一個(gè)關(guān)鍵字為空的地址9需要比較4次，因此查找不成功的次數(shù)為4衰腌。
所以新蟆，查找不成功的平均查找長(zhǎng)度為（3 + 2 + 1 + 2 + 1 + 5 + 4）/ 7 = 18 / 7
作者：Paul 5/28/2019
