摘要：分段求和法根據當前哈希表的位數把所要插入的數值分成若干段，把若干段進行相加，舍去調最高位結果就是這個值的哈希值。而二次探測再散列只有在哈希表長為形如為整數的素數時才可能。數據為數據的哈希值與更大素數求模后存儲到線性表中沖突的個數。

其實javascript的對象就是一個哈希表，為了學習真正的數據結構，我們還是有必要自己重新實現一下。

哈希表（hash table ）是一種根據關鍵字直接訪問內存存儲位置的數據結構，通過哈希表，數據元素的存放位置和數據元素的關鍵字之間建立起某種對應關系，建立這種對應關系的函數稱為哈希函數

假設要存儲的數據元素個數是n，設置一個長度為m(m > n)的連續存儲單元，分別以每個數據元素的關鍵字Ki(0<=i<=n-1)為自變量，通過哈希函數hash(Ki)，把Ki映射為內存單元的某個地址hash(Ki),并將數據元素存儲在內存單元中

從數學的角度看，哈希函數實際上是關鍵字到內存單元的映射，因此我們希望通過哈希函數通過盡量簡單的運算使得哈希函數計算出的花溪地址盡量均勻的背影射到一系列的內存單元中，構造哈希函數有三個要點：（1）運算過程要盡量簡單高效，以提高哈希表的插入和檢索效率；（2）哈希函數應該具有較好的散列型，以降低哈希沖突的概率；第三，哈希函數應具有較大的壓縮性，以節省內存。

以下有三種常用方法：

直接地址法：以關鍵字的某個線性函數值為哈希地址，可以表示為hash(K)=aK+C;優點是不會產生沖突，缺點是空間復雜度可能會較高，適用于元素較少的情況

除留余數法：它是由數據元素關鍵字除以某個常數所留的余數為哈希地址，該方法計算簡單，適用范圍廣，是經常使用的一種哈希函數，可以表示為：

hash(K=K mod C;該方法的關鍵是常數的選取，一般要求是接近或等于哈希表本身的長度，研究理論表明，該常數選素數時效果最好

數字分析法：該方法是取數據元素關鍵字中某些取值較均勻的數字來作為哈希地址的方法，這樣可以盡量避免沖突，但是該方法只適合于所有關鍵字已知的情況，對于想要設計出更加通用的哈希表并不適用

平方求和法：對當前字串轉化為Unicode值，并求出這個值的平方，去平方值中間的幾位為當前數字的hash值，具體取幾位要取決于當前哈希表的大小。

分段求和法：根據當前哈希表的位數把所要插入的數值分成若干段，把若干段進行相加，舍去調最高位結果就是這個值的哈希值。

在構造哈希表時，存在這樣的問題：對于兩個不同的關鍵字，通過我們的哈希函數計算哈希地址時卻得到了相同的哈希地址，我們將這種現象稱為哈希沖突

哈希沖突主要與兩個因素有關，（1）填裝因子，填裝因子是指哈希表中已存入的數據元素個數與哈希地址空間的大小的比值，a=n/m ; a越小，沖突的可能性就越小，相反則沖突可能性較大；但是a越小空間利用率也就越小，a越大，空間利用率越高，為了兼顧哈希沖突和存儲空間利用率，通常將a控制在0.6-0.9之間，而.net中的HashTable則直接將a的最大值定義為0.72 （雖然微軟官方MSDN中聲明HashTable默認填裝因子為1.0，但實際上都是0.72的倍數），（2）與所用的哈希函數有關，如果哈希函數得當，就可以使哈希地址盡可能的均勻分布在哈希地址空間上，從而減少沖突的產生，但一個良好的哈希函數的得來很大程度上取決于大量的實踐，不過幸好前人已經總結實踐了很多高效的哈希函數，可以參考大神Lucifer文章：數據結構：HahTable： http://www.cnblogs.com/lucife...

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)鏈地址法（拉鏈法）

將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。

優點:

①拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
②由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
④在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點

缺點：
拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度

4)建立一個公共溢出區
假設哈希函數的值域為[0,m-1]，則設向量HashTable[0...m-1]為基本表，每個分量存放一個記錄，另設立向量OverTable[0....v]為溢出表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管他們由哈希函數得到的哈希地址是什么，一旦發生沖突，都填入溢出表。

一個簡單哈希函數不做沖突處理的哈希表實現

// by 司徒正美
class Hash{
    constructor(){
        this.table = new Array(1024);
    }
    hash(data) {
    //就將字符串中的每個字符的ASCLL碼值相加起來，再對數組的長度取余
        var total = 0;
        for(var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        }
        console.log("Hash Value: " +data+ " -> " +total);
        return total % this.table.length;
    }
    insert(key, val){
        var pos = this.hash(key);
        this.table[pos] = val;
    }
    get(key){
        var pos = this.hash(key);
        return this.table[pos] 
    }
    show(){
        for(var i = 0; i < this.table.length; i++) {
            if(this.table[i] != undefined) {
                console.log(i + ":" +this.table[i]);
            }
        }
    }
    }
    var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];
    var hash = new Hash();
    for(var i = 0; i < someNames.length; ++i) {
    hash.insert(someNames[i],someNames[i]);
    }
    
    hash.show(); 

采用的是平方取中法構建哈希函數，開放地址法線性探測法進行解決沖突。

class Hash{
    constructor(){
        this.table = new Array(1000);
    }
    hash(data) {
        var total = 0;
        for(var i = 0; i < data.length; i++) {
            total += data.charCodeAt(i);
        }
            //把字符串轉化為字符用來求和之后進行平方運算
        var s = total * total + ""
            //保留中間2位
        var index = s.charAt( s.length/2 -1) *10 + s.charAt( s.length/2  ) * 1
        console.log("Hash Value: " +data+ " -> " +index);
        return index;
    }
    solveClash(index, value){
        var table = this.table
        //進行線性開放地址法解決沖突
        for(var i=0; index+i<1000;i++){
            if(table[index+i] == null){
                table[index+i] = value;
                break;
            }
        }
    }
    insert(key, val){
        var index = this.hash(key);
        //把取中當做哈希表中索引
        if(this.table[index] == null){
            this.table[index] = val;
        }else{
            this.solveClash(index, val);
        }
    }
    get(key){
        var pos = this.hash(key);
        return this.table[pos] 
    }
    show(){
        for(var i = 0; i < this.table.length; i++) {
            if(this.table[i] != undefined) {
                console.log(i + ":" +this.table[i]);
            }
        }
    }
}
var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];
var hash = new Hash();
for(var i = 0; i < someNames.length; ++i) {
    hash.insert(someNames[i],someNames[i]);
}

hash.show(); 

unsigned int DJBHash(char *str)    
{    
    unsigned int hash = 5381;    
     
    while (*str){    
        hash = ((hash << 5) + hash) + (*str++); /* times 33 */    
    }    
    hash &= ~(1 << 31); /* strip the highest bit */    
    return hash;    
}

javascript版

function DJBHash(str)    {    
    var hash = 5381;   
    var len = str.length , i = 0
     
    while (len--){    
        hash = (hash << 5) + hash + str.charCodeAt(i++); /* times 33 */    
    }    
    hash &= ~(1 << 31); /* strip the highest bit */    
    return hash;    
}

Justin Sobel寫的一個位操作的哈希函數。
原版

public long JSHash(String str)  
   {  
      long hash = 1315423911;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));  
      }  
      return hash;  
   }  

javascript版

function JSHash(str)  {  
      var hash = 1315423911;  
      for(var i = 0; i < str.length; i++)  {  
         hash ^= ((hash << 5) + str.charCodeAt(i) + (hash >> 2));  
      }  
      return hash;  
}  

該散列算法是基于貝爾實驗室的彼得J溫伯格的的研究。在Compilers一書中（原則，技術和工具），建議采用這個算法的散列函數的哈希方法。

public long PJWHash(String str)  
   {  
      long BitsInUnsignedInt = (long)(4 * 8);  
      long ThreeQuarters     = (long)((BitsInUnsignedInt  * 3) / 4);  
      long OneEighth         = (long)(BitsInUnsignedInt / 8);  
      long HighBits          = (long)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);  
      long hash              = 0;  
      long test              = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = (hash << OneEighth) + str.charAt(i);  
         if((test = hash & HighBits)  != 0)  
         {  
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));  
         }  
      }  
      return hash;  
   }  

javascript版

function PJWHash( str)  {  
      var BitsInUnsignedInt = 4 * 8;  
      var ThreeQuarters     =  (BitsInUnsignedInt  * 3) / 4;  
      var OneEighth         = (BitsInUnsignedInt / 8);  
      var HighBits          = (0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);  
      var hash              = 0;  
      var test              = 0;  
      for(var i = 0; i < str.length; i++)  {  
         hash = (hash << OneEighth) + str.charCodeAt(i);  
         if((test = hash & HighBits)  != 0)  
         {  
            hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));  
         }  
      }  
      return hash;  
} 

如果將上面的哈表的hash函數改成這個，打印如下：

性能會大幅下隆，因為這讓我們的table數組表得非常龐大。

和PJW很相似，在Unix系統中使用的較多。

public long ELFHash(String str)  
   {  
      long hash = 0;  
      long x    = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = (hash << 4) + str.charAt(i);  
         if((x = hash & 0xF0000000L) != 0)  
         {  
            hash ^= (x >> 24);  
         }  
         hash &= ~x;  
      }  
      return hash;  
   }  

這個算法來自Brian Kernighan 和 Dennis Ritchie的 The C Programming Language。這是一個很簡單的哈希算法,使用了一系列奇怪的數字,形式如31,3131,31...31,看上去和DJB算法很相似。

public long BKDRHash(String str)  
   {  
      long seed = 131; // 31 131 1313 13131 131313 etc..  
      long hash = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = (hash * seed) + str.charAt(i);  
      }  
      return hash;  
   }  

這個算法在開源的SDBM中使用，似乎對很多不同類型的數據都能得到不錯的分布。

public long SDBMHash(String str)  
   {  
      long hash = 0;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;  
      }  
      return hash;  
   }  

這個算法是Daniel J.Bernstein 教授發明的，是目前公布的最有效的哈希函數。

public long DJBHash(String str)  
   {  
      long hash = 5381;  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = ((hash << 5) + hash) + str.charAt(i);  
      }  
      return hash;  
   }  

由偉大的Knuth在《編程的藝術 第三卷》的第六章排序和搜索中給出。

public long DEKHash(String str)  
   {  
      long hash = str.length();  
      for(int i = 0; i < str.length(); i++)  
      {  
         hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);  
      }  
      return hash;  
   }  

由Arash Partow貢獻的一個哈希函數，繼承了上面以旋轉以為和加操作

public long APHash(String str)  
{  
      long hash = 0xAAAAAAAA;  
      for(int i = 0; i < str.length(); i++)  
      {  
         if ((i & 1) == 0)  
         {  
            hash ^= ((hash << 7) ^ str.charAt(i) * (hash >> 3));  
         }  
         else  
         {  
            hash ^= (~((hash << 11) + str.charAt(i) ^ (hash >> 5)));  
         }  
      }  
      return hash;  
   }   

其中數據1為100000個字母和數字組成的隨機串哈希沖突個數。數據2為100000個有意義的英文句子哈希沖突個數。數據3為數據1的哈希值與 1000003(大素數)求模后存儲到線性表中沖突的個數。數據4為數據1的哈希值與10000019(更大素數)求模后存儲到線性表中沖突的個數。

經過比較，得出以上平均得分。平均數為平方平均數。可以發現，BKDRHash無論是在實際效果還是編碼實現中，效果都是最突出的。APHash也是較為優秀的算法。DJBHash,JSHash,RSHash與SDBMHash各有千秋。PJWHash與ELFHash效果最差，但得分相似，其算法本質是相似的。