轉載請注明出處http://blog.csdn.net/yankai0219/article/details/8185796 零、學習方法 簡要學習理論篇，進入程序學習篇，再回頭學習理論篇和實踐篇 一、基本概念 1.Hash定義 Hash定義：將任意長度的輸入，通過散列算法，變成固定長度的輸出，該輸出就是散列值。 hash函數：就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。 Hash表：一種數據結構，既滿足了數據的查找方便，同時不占用太多的內容空間。 2.Hash用途 1）哈希主要用于信息安全領域中的加密算法，把一些不同長度的信息轉化成雜亂的128位的編碼。 2）在海量數據處理中有廣泛應用。 3.常見的Hash函數（散列算法） 1)除法散列法 2)平方散列法 3）斐波那契散列法 4.Hash表介紹 Hash表本質：歸類方法。 Hash表：一種新的數據結構，兼有數組的易尋址和鏈表的易插入和刪除的特點。 Hash表形象描述：如果有一堆書，就如同鏈表及線性表一樣，雜亂無序，查找起來十分麻煩； 如果進行編號，采用二分法，很快就可以查到 如果可以按照工科、理科、文科進行分類，就可以更快的查到。 Hash表的實現：有多種實現，最常用的是拉鏈法。 5.舉例說明Hash函數 在下面這一個字符串hash函數中，通過遍歷字符串，經過表達式hash = 31*hash +*p，循環計算得到Hash值。 很多hash函數都是如此操作，只是其表達式（散列算法）有所不同。

unsigned int yk_simple_hash(char *str,int str_len) { ??????? register unsigned int hash; ??????? register unsigned char *p; ??????? int i; ??????? for(hash = 0, i = 0, p = (unsigned char *)str; *p && i < str_len; p++,i++) ??????????????? hash = 31 * hash + *p; ??????? return (hash & 0x7FFFFFFF); }

二、沖突相關 1.沖突定義：假設哈希表的地址集為0~（n-1），沖突是指由關鍵字得到的哈希地址為j（0<=j<=n-1）的位置上已經有記錄。在關鍵字得到的哈希地址上已經有記錄，那么就稱之為沖突 2.處理沖突：就是為該關鍵字的記錄扎到另一個“空”的哈希地址。即在處理哈希地址的沖突時，若得到的另一個哈希地址H1仍然發生沖突，則再求下一個地址H2，若H2仍然沖突，再求的H3，直至Hk不發生沖突為止，則Hk為記錄在表中的地址。 處理沖突的方法： 1）開放定址法 Hi=(H(key) + di) MOD m i=1,2,...k(k<=m-1) 其中H(key)為哈希函數；m為哈希表表長；di為增量序列。有3中增量序列： 1）線性探測再散列：di=1,2,3,...,m-1 2）二次探測再散列：di=1^2,-1^2,2^2,-2^2,....+-k^2(k<=m/2) 3）偽隨機探測再散列：di=偽隨機數序列 缺點： 我們可以看到一個現象：當表中i,i+1,i+2位置上已經填有記錄時，下一個哈希地址為i,i+1,i+2和i+3的記錄都將填入i+3的位置，這種在處理沖突過程中發生的兩個第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現象稱為“二次聚集”，即在處理同義詞的沖突過程中又添加了非同義詞的沖突。但另一方面，用線性探測再散列處理沖突可以保證做到：只要哈希表未填滿，總能找到一個不發生沖突的地址Hk。而二次探測再散列只有在哈希表長m為形如4j+3（j為整數）的素數時才可能。 即開放定址法會造成二次聚集的現象，對查找不利。 ? ? ??2)再哈希法 Hi = RHi（key），i=1,2,...k RHi均是不同的哈希函數，即在同義詞產生地址沖突時計算另一個哈希函數地址，直到不發生沖突為止。這種方法不易產生聚集，但是增加了計算時間。 缺點：增加了計算時間。 3)鏈地址法（拉鏈法） 將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。 ? 4)建立一個公共溢出區 假設哈希函數的值域為[0,m-1]，則設向量HashTable[0...m-1]為基本表，每個分量存放一個記錄，另設立向量OverTable[0....v]為溢出表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管他們由哈希函數得到的哈希地址是什么，一旦發生沖突，都填入溢出表。 拉鏈法的優點: ①拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
②由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
④在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點 拉鏈法的缺點： 拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度 三.查找： 從哈希表的查找過程可見： 1）雖然哈希表在關鍵字與記錄的存儲位置直接建立了直接映像，但是由于“沖突”的產生，使得哈希表的查找過程仍然是一個給定值和關鍵字進行比較的過程。因此仍需以平均查找長度作為衡量哈希表的查找效率的量度。 2)查找過程中需和給定值進行比較的關鍵字的個數取決于下列三個因素：哈希函數，處理沖突的方法和哈希表的裝填因子。 在一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子。 裝填因子=（表中填入的記錄數）/(哈希表的長度). 裝填因子越小，發生沖突的可能性就越小；反之，裝填因子越大，表中已經填入的記錄越多，再填記錄時，發生沖突的可能性就越大，則查找時，給定值需與之進行比較的關鍵字的個數也就越多。 四 關于Hash使用與學習 首先一定要明白Hash表的拉鏈法。因為很多應用都是采用Hash表的拉鏈法。對于拉鏈法，我們可以理解為是一個鏈表的數組。1）數組的每一個元素都是一個鏈表。2）一個鏈表中的所有結點都具有相同的Hash值，其Hash值就是這個數組元素的下標。 其次，要學會Hash表初始化、插入元素、查找元素三大操作。
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的数据结构-Hash总结(一)：理论学习篇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。