散列
基礎定義
1、 散列：由資料項的值來確定資料存放的位置，散串列中的存盤位置被成為槽，
2、散列函式：實作從資料項到存盤槽的轉換的函式稱為散列函式，
3、 槽號：散列函式回傳的資料項的存盤位置，
幾種常用的散列函式：
求余散列：
- 方法：
將資料項除以散串列的大小，得到的余數作 為槽號，
實際上“求余數”方法會以不同形式出現在所有 散列函式里 因為散列函式回傳的槽號必須在散串列大小范圍 之內，所以一般會對散串列大小求余， - 資料的查找：
只需要使用同一個散列函式，對查找項進行計算，測驗下回傳的槽號所對應的槽中是否有 資料項即可 - 不足：
可能會出現”沖突“現象，即：兩個不同的資料項通過求余數后得到相同的槽號，
完美散列函式：
1. 方法：
給定一組資料項，如果一個散列函式能把 每個資料項映射到不同的槽中，對于固定的一組資料，總是能想方設法設計出完美散列函式，
2. 不足：
但是如果這組資料經常變動的話，很難有一個完美的散列函式（即會出現些許的沖突，但！沖突其實也不致命的，我們可以妥善的處理他們！）
3. 設計完美散列函式的方法：
①設計出一個足夠大的散串列（即：擴大散串列的容量）使得所有可能出現的資料項都能夠占據不同的槽，（不實用）
②退而求其次，好的散列函式需要具備特性 ：
沖突最少（近似完美）、
計算難度低（額外開銷小）、
充分分散資料項（節約空間）
散列的應用之一
區域鏈
區域鏈介紹：區域鏈是一種分布式資料庫，通過網路連接的節點 每個節點都保存著整個資料庫所有資料 任何地點存入的資料都會完成同步，
其本質特征：去中心化，即不存在任何控制中心，協調中心節點，所有節點都是平等的 ，無法被控制，
區塊鏈由一個個區塊（block）組成，區 塊分為頭（head）和體（body）
區塊頭記錄了一些元資料和鏈接到前一個區塊的資訊，
生成時間、前一個區塊(head+body)的散列值
區域鏈具有不可修改性：
由于散列值具有抗修改性，任何對某個區 塊資料的改動必然引起散列值的變化，為了不導致這個區塊脫離鏈條，就需要修改所有 后續的區塊，
由于有“作業量證明”的機制，這種大規模修改 不可能實作的，除非掌握了全網51%以的計算力，
散列函式設計
1.折疊法：
將資料項按照位數分為若干段，再將幾段數字相加， 最后對散串列大小求余，得到散列值，
有時候折疊法還會包括一個隔數反轉的步驟
2.平方取中（計算量稍大）：
首先將資料項做平方運算，然后取平方數的中間兩位，再對散串列的大小求余，
3.非數項：
也可以對非數字的資料項進行散列， 把字串中的每個字符看作ASCII碼即可，再將這些整數累加，對散串列大小求余，
注意：
這樣的散列函式對所有的變位詞都 回傳相同的散列值 為了防止這一點，可以將字串所在的位置作為 權重因子，乘以ord值，
4.數字分析法：
對于給定的關鍵碼集合，分析所有關鍵碼中各位數字出現的頻率，從中選出分布情況較好的若干數字作為散列函式的值，
散列函式設計基本法則
1.
散列函式不能太復雜，否則將成為存盤程序和查找程序的計算負擔，
2.
散列值應盡可能地均勻分布
沖突的解決方案：
1.解決沖突：
一個系統化的方法在散串列中保存發生沖突資料中的第二個資料項，
2.解決方法
開放定址：即 再找一個開放的空槽來保存 最簡單的就是從沖突的槽開始往后掃描，直到碰 到一個空槽 如果到散串列尾部還未找到，則從首部接著掃描 ，
向后逐個槽尋找的方法則是開放定址技術 中的“線性探測，
3.缺點：
容易有聚集趨勢，
4.改進：
將逐個探測改為跳躍式探測（再散列），
參考資料：
北京大學 陳斌老師的資料結構與演算法（python）網課課件
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/96944.html
標籤：其他
下一篇：撰寫OpenCL程式的流程