散 列-散列函數

散清單

散清單常常叫做散列，是一種以常數平均時間執行插入，删除和查找的技術，但是對于元素之間的任何排序資訊操作将不會得到有效支援。

一般想法

理想的散清單資料結構隻不過是一個包含有關鍵字的具有固定大小的數組，每個關鍵字被放到适當的單元中，這個映射叫做散列函數，理想狀态下函數要簡單并且沒有映射沖突，是以該函數要在單元格中均勻配置設定關鍵字。

散列函數

1.關鍵字為Int類型

如果是int類型關鍵字，則合理的辦法是傳回“Key mod TableSize”。除非不理想性質，如Key的個位都為0,而TableSize個位也為0，是以好的辦法是TableSize為一個素數。

typedef int Index;
Index
Hash(const int Key,int TableSize)
{
    return Key%TableSize;
}
           

2.關鍵字為字元串類型

對于字元串來說好的辦法是采用Horner法則。

typedef int Index;
Index
Hash(const char* Key,int TableSize)
{
    int HashVal=;

    while(*Key!='\0')
        HashVal=(HashVal<<)+*Key++;//這裡左移5位
    return HashVal%TableSize;
}
           

Horner法則

霍納法則：求多項式值的一個快速算法。

簡單介紹:

假設有n+2個數 , a0,a1,a2,a3,……an 和x組成的一個多項式，形式如下:

a0*x^0+a1*x^1+a2*x^2+a3*x^3+……an*x^n ，通常都是一項一項的求和然後累加，這樣的話要進行n* (n+1)/2 次乘法運算 和 n 次加法運算 ，

而霍納法則就是一個改進的一個算法。通過變換得到如下式子:

(((……(((an+an-1)*x+an-2)*x+an-3)*x)+……)*x+a1)*x+a0 ，

這種求值的方法便是霍納法則。(複雜度 為 O(n) )