數據結構哈希演算法

⑴ hash演算法是怎麼樣的

hash演算法是一種散列演算法，是把任意的長度的輸入，轉換成固定的額輸出，福鼎的輸出，輸出的是散列值。在空間的比較中，輸入的空間是遠大於輸出的散列值的空間，不同輸入散列成同樣的輸出，一般很難從輸出的散列值獲取輸入值的。

常用的hash函數有直接取余法、乘法取整法，平方取中法。在直接取余法中，質數用到的比較多，在乘法取整法中，主要用於實數，在平方取中法裡面，平方後取中間的，每位包含的信息比較多些。

Hash在管理數據結構中的應用

在用到hash進行管理的數據結構中，就對速度比較重視，對抗碰撞不太看中，只要保證hash均勻分布就可以。比如hashmap，hash值（key）存在的目的是加速鍵值對的查找，key的作用是為了將元素適當地放在各個桶里，對於抗碰撞的要求沒有那麼高。

換句話說，hash出來的key，只要保證value大致均勻的放在不同的桶里就可以了。但整個演算法的set性能，直接與hash值產生的速度有關，所以這時候的hash值的產生速度就尤為重要。

⑵ 什麼是哈希演算法，公式是什麼

哈希演算法將任意長度的二進制值映射為固定長度的較小二進制值，這個小的二進制值稱為哈希值。哈希值是一段數據唯一且極其緊湊的數值表示形式。如果散列一段明文而且哪怕只更改該段落的一個字母，隨後的哈希都將產生不同的值。要找到散列為同一個值的兩個不同的輸入，在計算上是不可能的，所以數據的哈希值可以檢驗數據的完整性。哈希表是根據設定的哈希函數H(key)和處理沖突方法將一組關鍵字映象到一個有限的地址區間上，並以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比，哈希表無疑是查找速度比較快的一種。通過將單向數學函數（有時稱為「哈希演算法」）應用到任意數量的數據所得到的固定大小的結果。如果輸入數據中有變化，則哈希也會發生變化。哈希可用於許多操作，包括身份驗證和數字簽名。也稱為「消息摘要」。 小紅和小明可按下面的方式使用哈希函數以確保數據完整性: 如果小紅對小明編寫一條消息並創建該消息的哈希，則小明可以在稍後散列該消息並將他的哈希與原始哈希進行比較。如果兩個哈希值相同，則該消息沒有被更改；但是，如果值不相同，則該消息在小紅編寫它之後已被更改。為了使此系統運行，小紅必須對除小明外的所有人保密原始的哈希值。

⑶ 朋友老說哈希演算法，請問到底什麼是哈希演算法

首先，一般哈希演算法不是大學里數據結構課里那個HASH表的演算法。一般哈希演算法是密碼學的基礎，比較常用的有MD5和SHA，最重要的兩條性質，就是不可逆和無沖突。
所謂不可逆，就是當你知道x的HASH值，無法求出x；
所謂無沖突，就是當你知道x，無法求出一個y， 使x與y的HASH值相同。

這兩條性質在數學上都是不成立的。因為一個函數必然可逆，且由於HASH函數的值域有限，理論上會有無窮多個不同的原始值，它們的hash值都相同。MD5和SHA做到的，是求逆和求沖突在計算上不可能，也就是正向計算很容易，而反向計算即使窮盡人類所有的計算資源都做不到。

我覺得密碼學的幾個演算法（HASH、對稱加密、公私鑰）是計算機科學領域最偉大的發明之一，它授予了弱小的個人在強權面前信息的安全（而且是絕對的安全）。舉個例子，只要你一直使用https與國外站點通訊，並注意對方的公鑰沒有被篡改，G**W可以斷開你的連接，但它永遠不可能知道你們的傳輸內容是什麼。

順便說一下，王小雲教授曾經成功製造出MD5的碰撞，即md5(a) = md5(b)。這樣的碰撞只能隨機生成，並不能根據一個已知的a求出b（即並沒有破壞MD5的無沖突特性）。但這已經讓他聲名大噪了。

⑷ 數據結構哈希演算法

1，直接定址法：
函數公式：f(key)=a*key+b (a,b為常數)
這種方法的優點是：簡單，均勻，不會產生沖突。但是需要事先知道關鍵字的分布情況，適合查找表較小並且連續的情況。
2，數字分析法：
比如我們的11位手機號碼「136XXXX7887」，其中前三位是接入號，一般對應不同運營公司的子品牌，如130是聯通如意通，136是移動神州行，153是電信等。中間四們是HLR識別號，表示用戶歸屬地。最後四們才是真正的用戶號。
若我們現在要存儲某家公司員工登記表，如果用手機號碼作為關鍵字，那麼極有可能前7位都是相同的，所以我們選擇後面的四們作為哈希地址就是不錯的選擇。
3，平方取中法：
故名思義，比如關鍵字是1234，那麼它的平方就是1522756，再抽取中間的3位就是227作為哈希地址。
4，折疊法：
折疊法是將關鍵字從左到右分割成位數相等的幾個部分(最後一部分位數不夠可以短些)，然後將這幾部分疊加求和，並按哈希表表長，取後幾位作為哈希地址。
比如我們的關鍵字是9876543210，哈希表表長三位，我們將它分為四組，987|654|321|0 ，然後將它們疊加求和987+654+321+0=1962，再求後3位即得到哈希地址為962，哈哈，是不是很有意思。
5，除留余數法：
函數公式：f(key)=key mod p (p<=m)m為哈希表表長。
這種方法是最常用的哈希函數構造方法。
6，隨機數法：
函數公式：f(key)= random(key)。
這里random是隨機函數，當關鍵字的長度不等是，採用這種方法比較合適。
兩種哈希函數沖突解決方法：
我們設計得最好的哈希函數也不可能完全避免沖突，當我們在使用哈希函數後發現兩個關鍵字key1!=key2，但是卻有f(key1)=f(key2)，即發生沖突。

⑸ 什麼是哈希演算法具體怎麼用啊有什麼用啊

哈希(Hash)演算法,即散列函數。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時,哈希函數可以將任意長度的輸入經過變化以後得到固定長度的輸出。哈希函數的這種單向特徵和輸出數據長度固定的特徵使得它可以生成消息或者數據。
計算方法：
用來產生一些數據片段（例如消息或會話項）的哈希值的演算法。使用好的哈希演算法，在輸入數據中所做的更改就可以更改結果哈希值中的所有位；因此，哈希對於檢測數據對象（例如消息）中的修改很有用。此外，好的哈希演算法使得構造兩個相互獨立且具有相同哈希的輸入不能通過計算方法實現。典型的哈希演算法包括 MD2、MD4、MD5 和 SHA-1。哈希演算法也稱為「哈希函數」。
另請參閱： 基於哈希的消息驗證模式 (HMAC), MD2, MD4, MD5,消息摘要, 安全哈希演算法 (SHA-1)
MD5一種符合工業標準的單向 128 位哈希方案，由 RSA Data Security, Inc. 開發。 各種「點對點協議(PPP)」供應商都將它用於加密的身份驗證。哈希方案是一種以結果唯一並且不能返回到其原始格式的方式來轉換數據（如密碼）的方法。質詢握手身份驗證協議(CHAP) 使用質詢響應並在響應時使用單向 MD5哈希法。按照此方式，您無須通過網路發送密碼就可以向伺服器證明您知道密碼。
質詢握手身份驗證協議(CHAP)「點對點協議(PPP)」連接的一種質詢響應驗證協議，在 RFC 1994 中有所描述。 該協議使用業界標准 MD5哈希演算法來哈希質詢串（由身份驗證伺服器所發布）和響應中的用戶密碼的組合。
點對點協議
用點對點鏈接來傳送多協議數據報的行業標准協議套件。RFC 1661 中有關於 PPP 的文檔。
另請參閱： 壓縮控制協議 (CCP)，遠程訪問，徵求意見文檔 (RFC)，傳輸控制協議/Internet 協議 (TCP/IP)，自主隧道。

⑹ 數據結構-哈希演算法

H(22)=(3*22)mod 11=0;
H(41)=2;
H(53)=5;
H(46)=6;
H(30)=2;沖突；H1=(H(key)+d1)MOD m = (2+1((7*30)MOD 10+1)) MOD 11=3;
H(13)=6;沖突；H1=(6+1(1+1))=8;
H(01)=3;沖突；H1=(3+1(7+1))mod 11=0;H2=(3+2(7+1))mod 11=8;
H3=(3+3*8)mod 11=5; H4=(3+4*8)mod 11=2;
H5=(3+5*8)mod 11=10;
H(67)=3;沖突；H1=(3+1*(7*67mod10+1))mod 11=2; H2=(3+2*10)mod 11=1；

⑺ 哈希演算法和哈希表的區別

哈希演算法將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值。哈希函數實現了哈希演算法,返回值就是 hash code。哈希表是一個數據結構,內部實現靠哈希函數。

⑻ hash 演算法

這么說吧，hash這東西啊，主要就是為了查找方便，你學過table，heap之類的么？就比方說1-20，你要查找15， 通常的方法是從1開始，1，2，3...一個一個對照過去看是不是15，然後最後15個查找時間，找到15，但是hash不同了，hash是直接找到， 比方說 『key』 存在 第15的位置，那麼首先通過一個hash方程對 文字進行映射，就比方說k=3,e=8,y=4, h(key)=3+8+4=15.然後算好了直接去15取這個數，一個查找時間就算出來了。而傳統的 查找方法很多，你自己可以去搜索，什麼merge sort 啊，quick sort啊，slection sort啊，排序查找都是一起的，搜一下就好了。。數據結構學透不易啊。慢慢來吧。。

⑼ 哈希演算法的基本特點

哈希表是根據設定的哈希函數H(key)和處理沖突方法將一組關鍵字映射到一個有限的地址區間上，並以關鍵字在地址區間中的象作為記錄在表中的存儲位置，這種表稱為哈希表或散列，所得存儲位置稱為哈希地址或散列地址。作為線性數據結構與表格和隊列等相比，哈希表無疑是查找速度比較快的一種。
通過將單向數學函數（有時稱為「哈希演算法」）應用到任意數量的數據所得到的固定大小的結果。如果輸入數據中有變化，則哈希也會發生變化。哈希可用於許多操作，包括身份驗證和數字簽名。也稱為「消息摘要」。
簡單解釋：哈希(Hash)演算法,即散列函數。它是一種單向密碼體制,即它是一個從明文到密文的不可逆的映射,只有加密過程,沒有解密過程。同時,哈希函數可以將任意長度的輸入經過變化以後得到固定長度的輸出。哈希函數的這種單向特徵和輸出數據長度固定的特徵使得它可以生成消息或者數據。