旭說資料結構之散清單（哈希表）

對于線性表這種資料結構，當我們查找指定值的時候，隻能通過與表中各個元素進行比較的方法。因為線性表每個位置上存放的值與位置沒有關系，這個位置上想放什麼值就放什麼值。

而散清單（又稱哈希表）這種資料結構每個位置上放置的資料的值與位置是有關系的，換句話說，你的數值是A，就隻能放到 f(A) 這個位置上，你的數值是B，就隻能放到 f(B) 上，這樣當我想要知道數值A在不在散清單中的時候，我就計算一下f(A),然後看看f(A)這個位置的值是不是A，如果是A就說明我們找到了散清單中的A。這裡的 f() 是元素值與存儲位置的對應關系。

不難想到， f(x) 是建構散清單的關鍵，不同的 f(x) 會把相同的元素值映射到不同的存儲位置。我們稱 f(x) 為散列函數。

如何設計 f(x) 呢？最好就是我給了你一堆 n 個數字，和n個空間，你能把每個數字通過 f(x) 計算後，給它找到一個坑安置它，不會出現兩個數字争奪一個坑的情況。

常用的散列函數構造方法有：

1. 直接定址法

   把要存放的數值（關鍵字）作為位址或者是該數值的線性函數作為位址。

   f(x)=ax+b.(a、b為常數)

   一般用于事先知道了關鍵字集合，且關鍵字集合不大、連續性好。

2. 除留餘數法

   就是把要存放的數值除以某個數，把得到的餘數作為位址。

   f(x)=xmodp;(p為常數)

   對p的選擇很重要，一般取接近表容量的最小素數。

3. 平方取中法

   把關鍵字平方，取平方結果的中間幾位作為位址。

   比如，給你一個數值 111 ，平方後得到 12321 ，如果取中間 1 位作為位址，則3為 111 的散列位址。

   再給個數值 222 ，平方後得到 49284 ，如果取中間 1 位作為位址，則2為 111 的散列位址。

   想要完美的構造散列函數是不可能的，是以總會出現幾個數值搶坑的局面。比如：

   

   常用的處理搶坑（沖突）問題的方法有：

   1. 開放定址法。比如上圖中，我計算出 24 的位址為 0 ，然後我到位置 0 處發現位置0處存放的是 100 ，這時我就不能把 24 放在位置 0 處，我轉而尋找下一個空白的散列位址。我先計算(f(24)+d1)modn（其中 n 是散清單的長度，d1是序列 d1,d2,d3...dn−1 中的第一個值），看看計算所得的位址處有沒有值，如果沒有就把24存進去，如果有值，再計算 (f(24)+d2)modn ，如此這般，直到找到的位址處沒有值把 24 插入。

      序列一般有三種的取值方式,

      • 線性探測再散列， d=1,2...n−1
      • 二次探測再散列， d=12,−12,22,−22...v2,−v2(v≤n/2)

   2. 鍊位址法

      将所有具有相同散列位址的不同元素值放到一個單連結清單中，在散清單中存放這些單連結清單的頭指針。

   3. 建立一個公共溢出區

下面是一個利用開放位址法寫的例子：

template<typename DataType>class HashTable
{
public:
    HashTable(int capacity = )
    {
        _capacity = capacity;
        _datas = new DataType[capacity];
        _length = ;
        for (int i = ;i<capacity;i++)
        {
            _datas[i]=NULL;
        }
    }
    ~HashTable()
    {
        delete [] _datas;
    }
    //采用除留餘數法f(x)=data%p
    int hashFunc(DataType data,int p)
    {
        return data % p;
    }
    //傳回要查找元素的位址，利用開放定址法來解決沖突
    int searchData(DataType data)
    {
        int place = hashFunc(data,);
        if (_datas[place] == data)//如果該位址處的值等于我要找的值
        {
            return place;
        }
        //如果該位址的值不等于我要找的值,利用開放位址法
        int nextPlace = (place + )%_capacity;
        while(nextPlace != place){
            if (_datas[nextPlace] == data)//如果這個地方的值等于我們要找的data了
            {
                return nextPlace;
            }
            if (_datas[nextPlace] == NULL)//如果這個地方還沒有值，那就說明我們要找的data不在裡面
            {
                break;
            }
            nextPlace = (nextPlace +)%_capacity;
        }
        if (nextPlace == place)//如果循環了一圈，既沒有找到空白位址，也沒有找到存有data值的位址，則說明這個值不在該散清單中，同時也沒有地方給這個值用了
        {
            return -;
        }else{//找到了空白的區域

            cout<<"你要的值不在散清單中，我找到了一個空白區域，你可以把值插入進去了"<<endl;
            return nextPlace;
        }

    }
    bool insertData(DataType data)
    {
        int place = searchData(data);
        if (place < )  return false;
        //如果要插入的值已經在散清單中，傳回false
        if (_datas[place] == data)
        {
            return false;
        }
        //能到這一步，說明searchData傳回的是一個空白區域
        _datas[place]=data;
        return true;
    }

    void printDatas(){
        for (int i =;i<_capacity;i++)
        {
            cout<<_datas[i]<<endl;
        }
    }
private:
    int _capacity;
    int _length;
    DataType * _datas;
};