一、hash表的基本概念和優缺點比較hash表又稱哈希表 ，是一種數據結構，與鏈表、二叉樹有很大區別。1、hash表優缺點優點：能夠在常數級的時間復雜度上進行查找，并且插入數據和刪除數據簡單。（Hash未滿的時候速度很快）缺點：不支持排序，一般比用線性表存儲需要更多時間，并且記錄的關鍵字不能重復2、與鏈表比較鏈表：查詢上表中的數據從頭開始遍歷，直到查到或者查找失敗。hash：根據存儲數據特定關鍵字，然后根據關鍵字直接查詢想要得到數據。hash存儲位置通常稱作Hash地址。Hash地址是由關鍵字經過特定的 hash函數運算得到。3、當關鍵字重復就會產生數據沖突。二、hash表的構造方法１、直接定址法例如：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。但這種方法效率不高,時間復雜度是O(1),空間復雜度是O(n),n是關鍵字的個數eg:f(x) = 5x+10x代表的就是年齡，而f(x)獲取到的就是對應地址，是取Hash地址與關鍵字構成的線性函數。2、平方取中法適用關鍵字是數字的情況，將關鍵字平方然后取其中間的幾位作為Hash地址。3、數字分析法比如同齡人的出生年月，由于前幾位數字的重復幾率較大，所以造成沖突的幾率較高，所以盡量不取前幾位。4、折疊法將關鍵字分割成相同的幾段數字（最后一部分可以不同），然后將得到的幾段數字疊加（進位舍去）作為Hash地址，折疊法eg：每一種西文圖書都有一個國際標準圖書編號，它是一個10位的十進制數字，若要以它作關鍵字建立一個哈希表，如果一本書的編號為1234-5678-321,可以將其分為{12,34,56,78,32,1}。而Hash地址則是這幾個數之和。5、除留取余法如果知道Hash表的最大長度為m，可以取不大于m的最大質數p，然后對關鍵字進行取余運算，f(x) = x%p。在這里p的選取非常關鍵，p選擇的好的話，能夠最大程度地減少沖突，p一般取不大于m的最大質數。6、隨機數法選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即f(x)=random(x) ,其中random為隨機函數。通常用于關鍵字長度不等時采用此法。三、沖突處理1、開放定址法關鍵字沖突時，使用某種探測技術在Hash表中形成一個探測序列，然后沿著這個探測序列依次查找下去，當碰到一個空的單元時，則插入其中。eg：一組關鍵字{13，25，23，38，34，6，84，91}，Hash表長為14，Hash函數為f(x)=x%11，當插入13，25時可以直接插入，而當插入23時，地址1被占用了，因此沿著地址1依次往下探測(探測步長可以根據情況而定)，直到探測到地址3，發現為空，則將23插入其中。2、再哈希法當發生沖突時，使用第二個、第三個、哈希函數計算地址，直到無沖突時。缺點：計算時間增加。3、鏈地址法采用數組和鏈表結合的方式，HashMap中就是采用這種方式存儲Hash地址，原理是將Hash地址（經過關鍵字計算的值）相同的記錄存在同一個鏈表中，而每張表的表頭序號就是新的Hash地址。４、建立一個公共溢出區假設哈希函數的值域為[0,m-1],則設向量HashTable[0..m-1]為基本表，另外設立存儲空間向量OverTable[0..v]用以存儲發生沖突的記錄。參考博文：http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html

總結

以上是生活随笔為你收集整理的hash表学习笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

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