哈希表開散列法（拉鏈法）

開散列法又叫鏈地址法(開鏈法)。
開散列法：首先對關鍵碼集合用散列函數計算散列地址，具有相同地址的關鍵碼歸於同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈錶鏈接起來，各鏈表的頭結點存儲在哈希表中。

設元素的關鍵碼為37, 25, 14, 36, 49, 68, 57, 11, 散列表為HT[12]，表的大小為12，散列函數為Hash(x) = x % 11
Hash(37)=4
Hash(25)=3
Hash(14)=3
Hash(36)=3
Hash(49)=5
Hash(68)=2
Hash(57)=2
Hash(11)=0
使用哈希函數計算出每個元素所在的桶號，同一個桶的鏈表中存放哈希衝突的元素。

通常，每個桶對應的鏈表結點都很少，將n個關鍵碼通過某一個散列函數，存放到散列表中的m個桶中，那麼每一個桶中鏈表的平均長度為。以搜索平均長度為的鏈表代替了搜索長度為 n 的順序表，搜索效率快的多。
應用鏈地址法處理溢出，需要增設鏈接指針，似乎增加了存儲開銷。事實上：
由於開地址法必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因數a <= 0.7，而表項所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節省存儲空間。

哈希拉鏈相關代碼如下：

使用素數表對齊做哈希表的容量，降低哈希衝突。

size_t HashTableKPrime(size_t N) //獲取素數
{
  int i = 0;
  const int _PrimeSize = 28;
  static const unsigned long _PrimeList [] =
  {
      53ul, 97ul, 193ul, 389ul, 769ul,
      1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
      49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
      1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
      50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
      1610612741ul, 3221225473ul, 4294967291ul
  };
  for (i=0; i<_PrimeSize; i++)
  {
      if (_PrimeList[i] > N)
          return _PrimeList[i];
  }

  return _PrimeList[_PrimeSize-1];
}

開闢拉鏈的鏈式節點

HashNode* BuyHashKNode(KeyType key,ValueType value) //開闢新節點
{
  HashNode *tmp = (HashNode *)malloc(sizeof(HashNode));
  assert(tmp);
  tmp->_key = key;
  tmp->_value = value;
  tmp->_next = NULL;
  return tmp;
}

哈希函數

KeyType HashKFunc(KeyType key,size_t n)
{
    return key%n;
}

哈希拉鏈表的初始化

void HashTableKInit(HashTable *ht,size_t N)//初始化
{
  assert(ht);
  ht->_N = N;
  ht->_size = 0;
  **這裡要特別註意開闢空間是給指針數組**
  ht->_tables = (HashNode **)malloc(sizeof(HashNode*)*ht->_N);
  assert(ht->_tables);
  memset(ht->_tables,0,sizeof(HashNode*)*ht->_N);
}

插入時擴容這塊很關鍵，要重新開闢一塊數組空間，把原先的表中數據映射過來，但是拉鏈節點不用重新開闢，直接把原先的節點拿過來。

int HashTableKInsert(HashTable* ht, KeyType key, ValueType value) //插入
{
    KeyType index;
    HashNode *node = BuyHashKNode(key,value);
    assert(ht);

    if (ht->_N == ht->_size) //擴容
    {
     size_t i = 0;
     HashTable newht;
     HashTableKInit(&newht,HashTableKPrime(ht->_N));
     for (i=0; i<ht->_N; i++)
     {
         if (ht->_tables[i])
         {
             KeyType index;
             HashNode *cur = ht->_tables[i];
             while (cur)
             {
                 HashNode *next = cur->_next;
                 index = HashKFunc(cur->_key,newht._N);

                 cur->_next = newht._tables[index];
                 newht._tables[index] = cur;

                 cur = next;
             }
         }
     }
     free(ht->_tables);
     ht->_tables = newht._tables;
     ht->_N = newht._N;
    }

    index = HashKFunc(key,ht->_N);
    if (ht->_tables[index])
    {
        HashNode *cur = ht->_tables[index];
        while (cur)
        {
            if (cur->_key == key)
                return -1;
            cur = cur->_next;
        }
    }

    node->_next = ht->_tables[index];
    ht->_tables[index] = node;
    ht->_size++;
    return 0;
}

查找函數

HashNode* HashTableKFind(HashTable* ht, KeyType key) //查找
{
    ValueType index = HashKFunc(key,ht->_N);
    assert(ht);

    if (ht->_tables[index])
    {
        if (ht->_tables[index]->_key == key)
            return ht->_tables[index];
        else
        {
            HashNode *cur = ht->_tables[index];
            while (cur)
            {
                if (cur->_key == key)
                    return cur;
                cur = cur->_next;
            }
            return NULL;
        }
    }
    else
        return NULL;
    
}

刪除函數

int HashTableKRemove(HashTable* ht, KeyType key) //刪除
{
    KeyType index = HashKFunc(key,ht->_N);
    assert(ht);
    
    if (ht->_tables[index])
    {
        HashNode *prev = ht->_tables[index];
        HashNode *cur = ht->_tables[index];
        while (cur)
        {
            if (cur == prev && cur->_key == key)
            {
                ht->_tables[index] = cur->_next;
                free(cur);
                cur = NULL;
                ht->_size--;
                return 0;
            }
            else if(cur->_key == key)
            {
                prev-> = cur->_next;
                free(cur);
                cur = NULL;
                ht->_size--;
                return 0;
            }

            prev = cur;
            cur = cur->_next;
        }
        return -1;
    }
    else
        return -1;
}

void HashTableKDestory(HashTable* ht) //銷毀
{
    size_t i = 0;
    assert(ht);
    for (i=0; i<ht->_N;++i)
    {
        if (ht->_tables[i])
        {
            HashNode *cur = ht->_tables[i];
            while (cur)
            {
                HashNode *tmp = cur;
                cur = cur->_next;
                free(tmp);
                tmp = NULL;
            }
        }
    }
    free(ht->_tables);
    ht->_tables = NULL;
    ht->_size = 0;
    ht->_N = 0;
}

測試函數

void TestHashTableK()
{
    HashTable ht;
    HashTableKInit(&ht,3);

    HashTableKInsert(&ht,10,0);
    HashTableKInsert(&ht,11,0);
    HashTableKInsert(&ht,12,0);
    HashTableKInsert(&ht,106,0);
    HashTableKInsert(&ht,53,0);
    HashTableKInsert(&ht,1,0);
    HashTableKInsert(&ht,15,0);
    HashTableKInsert(&ht,0,0);
    HashTableKInsert(&ht,53,0);
    HashTableKInsert(&ht,52,0);
    HashTableKInsert(&ht,104,0);
    HashTableKInsert(&ht,2,0);
    HashTableKInsert(&ht,54,0);
    HashTableKInsert(&ht,108,0);
    HashTableKPrint(&ht);
    printf("\n");


    printf("%d ",HashTableKFind(&ht,2)->_key);
    printf("%d ",HashTableKFind(&ht,53)->_key);
    printf("%d ",HashTableKFind(&ht,0)->_key);
    printf("%d ",HashTableKFind(&ht,12)->_key);
    printf("%p ",HashTableKFind(&ht,156));
    printf("\n\n");


    HashTableKRemove(&ht,2);
    HashTableKRemove(&ht,53);
    HashTableKRemove(&ht,1);
    HashTableKRemove(&ht,54);
    HashTableKRemove(&ht,89);
    HashTableKPrint(&ht);

    HashTableKDestory(&ht);
    HashTableKPrint(&ht);


}

測試結果：

相關哈希表概念請看哈希表詳解：這裡寫鏈接內容