hash_table

C++系列
約 34 分鐘閱讀

雜湊的概念

雜湊，也稱「散列」是一種用來進行高效查找的資料結構，查找的時間複雜度平均為O(1)，其本質就是依賴雜湊函數這個演演算法來將 key和該key儲存位置建立一個映射關係。而因為是有著映射關係，所以雜湊的時間複雜度為O(1)。

key => hash function => position

採用雜湊處理時，一般所需空間都會比元素個數多，否則產生衝突的機率就比較大，影響雜湊的效能 => 因此雜湊是以空間的代價換取較高的效率。

相關名詞解釋

  1. 雜湊衝突：也稱雜湊碰撞，也就是不同的key映射到了同一個位置
    實際上任何雜湊函數都可能發生雜湊衝突，我們能做的就是設計出一個好的雜湊函數盡可能的減少雜湊衝突發生的機率
  2. 負載因子：假設雜湊表中已經映射儲存了N個值，雜湊表的⼤⼩為M，則負載因子為 ${\frac{N}{M}}$
    負載因子的值越大，意味著雜湊衝突的發生率越高，空間使用率高。反之負載因子越小，雜湊衝突的發生率越低，空間使用率低。因此負載因子也是後續模擬實現當中用來判斷是否要擴容的一個標準。

雜湊函數的定義

直接定址法

直接定址法適用於key(或稱關鍵字 => 非C++中定義的關鍵字)範圍較集中的情況。
直接定址法本質就是⽤ key 計算出⼀個絕對位置或者相對位置。

leetcode-387
題目描述如下
leetcode387_description.png
我們就可以利用手動模擬雜湊

class Solution {
public:
int firstUniqChar(string s) {
 int hash[26] = {0}; // 26 對應26個字母

 for(int i = 0;i<s.size();++i){
   hash[s[i] - 'a']++; // 直接通過 s 中每一個字符的值 去映射一個位置
 }
 for(int i = 0;i<s.size();++i){
   if(hash[s[i] - 'a'] == 1){
     return i;
   }
 }
 return -1;
}
};

除法散列法

除法散列法也叫做除留餘數法，假設雜湊表的⼤⼩為M，那麼通過key除以M的餘數作為映射位置的下標。
也就是雜湊函數為：h(key) = key % M。
在使用除法散列法時應避免M的大小取2的冪次或10的冪次

如果M取的大小是2的x次方，那麼key % M本質相當於保留key的後X位，那麼後x位相同的值，計算出的雜湊值都是⼀樣的就衝突了。
如：{63,31}看起來沒有關聯的值，如果M是16，那麼計算出的雜湊值都是15。
因為63的⼆進制後4位是 1111，31的⼆進制後4位是 1111。如果是10的x次方，就更明顯了，保留的都是10進制的後x位，如：{112, 12312}，如果M是100，那麼計算出的雜湊值都是12。
為了避免前面提到的問題，當使用除法散列法時建議M取不太接近2的整數次冪的⼀個質數。

散列函數有一個共同性質，即函數值應按同等概率取其值域的每一個值。

雜湊碰撞的解決方法

開放定址法

在開放定址法中所有的元素都放到雜湊表⾥，當⼀個關鍵字key⽤雜湊函式計算出的位置衝突了，則按照某種規則找到⼀個沒有存儲數據的位置進⾏存儲，開放定址法中負載因⼦⼀定是⼩於的。

這⾥有三種：線性探測、⼆次探測、雙重探測

線性探測

從發⽣衝突的位置開始，依次線性向後探測，直到尋找到下⼀個沒有存儲數據的位置為⽌，如果⾛到雜湊表尾，則回繞到雜湊表頭的位置。

採用線性探測法處理散列時的衝突,當從雜湊表刪除一個記錄時,不應將這個記錄的所在位置置空,因為這會影響以後的查找。

二次探測

從發⽣衝突的位置開始，依次左右按⼆次⽅跳躍式探測，直到尋找到下⼀個沒有存儲數據的位置為⽌，如果往右⾛到雜湊表尾，則回繞到雜湊表頭的位置；如果往左⾛到雜湊表頭，則回繞到雜湊表尾的位置。

開放定址法程式碼實現

開放定址法在實踐中，不如鏈地址法，因為開放定址法解決衝突不管使⽤哪種⽅法，佔⽤的都是雜湊表中的空間始終存在互相影響的問題。所以開放定址法，我們簡單選擇線性探測進行實現。

#include <iostream>
using namespace std;

namespace OpenAddress {
  // 仿函式
  template <class K> struct HashFunc {
    size_t operator()(const K &key) {
      return (size_t)key; // 把 key 轉成整數 ( 爲了處理 key 非整的情況 =>
      // 因爲要取模，非整沒辦法取模 )
      // 如果是自定義類別型，也可以將賅仿函式進行特化 來處理自定義類別型轉整的問題
    }
  };
  // 特化 處理string
  template <> struct HashFunc<string> {
    size_t operator()(const string &key) {
      size_t hash = 0;
      for (auto ch : key) {
        hash = hash * 131 + ch;
      }
      return hash;
    }
  };
  enum State { EMPTY, EXISTED, DELETED };

  template <class K, class V> struct HashData {
    pair<K, V> _kv;
    State _state = EMPTY;
  };

  template <class K, class V, class Hash = HashFunc<K>> class HashTable {
    public:
    // 這裏提供sgi版本的雜湊表使⽤的⽅法，給了⼀個近似2倍的質數表，每次去質數表獲取擴容後的⼤⼩
    inline unsigned long __stl_next_prime(unsigned long n) {
      // Note: assumes long is at least 32 bits.
      static const int __stl_num_primes = 28;
      static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53,        97,         193,        389,       769,       1543,
        3079,      6151,       12289,      24593,     49157,     98317,
        196613,    393241,     786433,     1572869,   3145739,   6291469,
        12582917,  25165843,   50331653,   100663319, 201326611, 402653189,
        805306457, 1610612741, 3221225473, 4294967291};
      const unsigned long *first = __stl_prime_list;
      const unsigned long *last = __stl_prime_list + __stl_num_primes;
      const unsigned long *pos = lower_bound(first, last, n);
      // 如果 n 的值超出 [first,last) 的最大值 => return 最後一個元素的下一個位置;
      // 如果小於 return 第一個元素的位置
      return pos == last ? *(last - 1) : *pos;
    }
    HashTable() { _table.resize(__stl_next_prime(0)); }
    bool insert(const pair<K, V> &kv) {
      // 插入時先確定該值是否已存在表中
      if (find(kv.first)) {
        return false;
      }
      // 先判斷當前的負載因子大小( N(數據個數) / M(表大小) )
      if (_n * 10 / _table.size() >= 7) { // 這裏我們將負載因子控制在0.7
        // 擴容的邏輯就是先開空間 把元素 _table 中的元素插入到新開的空間中
        // 再將新的空間和舊的空間交換
        HashTable<K, V, Hash> newht;
        newht._table.resize(__stl_next_prime(_table.size() + 1));
        for (size_t i = 0; i < _table.size(); ++i) {
          if (_table[i]._state == EXISTED) {
            newht.insert(_table[i]._kv);
          }
        }
        _table.swap(newht._table);
      }
      // 如果負載因子小於0.7 則直接插入
      Hash hash;
      size_t hash0 = hash(kv.first) % _table.size();
      size_t hashi = hash0;
      size_t i = 1;
      while (_table[hashi]._state == EXISTED) {
        // 線性探測
        hashi = (hash0 + i) % _table.size();
        // 如果是二次探測 就改成 +- i^2

        ++i;
      }
      _table[hashi]._kv = kv;
      _table[hashi]._state = EXISTED;
      ++_n;
      return true;
    }
    HashData<K, V> *find(const K &key) {
      Hash hash;
      size_t hash0 = hash(key) % _table.size();
      size_t hashi = hash0;
      size_t i = 1;
      while (_table[hashi]._state != EMPTY) {
        // 如果找到
        if (_table[hashi]._state == EXISTED && _table[hashi]._kv.first == key) {
          return &_table[hashi];
        }
        // 如果當前的 index 不是目標值 ( 可能是原本就被佔用了，所以要往後找
        // 直到找完整個 _table) => 所以其實開放定址法的效率不及鏈定址法
        hashi = (hash0 + i) % _table.size();
        ++i;
      }
      // while 結束代表沒有找到目標值
      return nullptr;
    }
    bool erase(const K &key) {
      HashData<K, V> ret = find(key);
      if (ret == nullptr) {
        return false;
      }
      ret->_state = DELETED;
      --_n;
      return true;
    }

    private:
    vector<HashData<K, V>> _table;
    size_t _n = 0; // 雜湊表中存儲的數據個數
  };
  void HashTest1() {
    HashTable<int, int> ht;
    ht.insert(make_pair(1, 1));
    ht.insert(make_pair(2, 2));
    ht.insert(make_pair(3, 3));
    ht.insert(make_pair(4, 4));
    ht.insert(make_pair(5, 5));
    ht.insert(make_pair(6, 6));
    ht.erase(2);
    ht.erase(3);
  }
}

鏈定址法

鏈定址法的思想：開放定址法中所有的元素都放到雜湊表⾥，鏈地址法中所有的數據不再直接存儲在雜湊表中雜湊表中存儲⼀個指針，沒有數據映射這個位置時，這個指針爲空，有多個數據映射到這個位置時把這些衝突的數據鏈接成⼀個鏈表，掛在雜湊表這個位置下⾯，鏈地址法也叫做拉鍊法或者雜湊桶</font>。

雜湊桶.png

namespace HashBucket {
// 仿函式
template <class K> struct HashFunc {
  size_t operator()(const K &key) { return (size_t)key; }
};
template <class K, class V> struct HashData {
  pair<K, V> _kv;
  HashData<K, V> *_next;

  HashData(const pair<K, V> &kv) : _kv(kv), _next(nullptr) {}
};

template <class K, class V, class Hash = HashFunc<K>> class HashTable {
  typedef HashData<K, V> Node;

public:
  inline unsigned long __stl_next_prime(unsigned long n) {
    // Note: assumes long is at least 32 bits.
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = {
        53,        97,         193,        389,       769,       1543,
        3079,      6151,       12289,      24593,     49157,     98317,
        196613,    393241,     786433,     1572869,   3145739,   6291469,
        12582917,  25165843,   50331653,   100663319, 201326611, 402653189,
        805306457, 1610612741, 3221225473, 4294967291};
    const unsigned long *first = __stl_prime_list;
    const unsigned long *last = __stl_prime_list + __stl_num_primes;
    const unsigned long *pos = lower_bound(first, last, n);
    // 如果 n 的值超出 [first,last) 的最大值 => return 最後一個元素的下一個位置;
    // 如果小於 return 第一個元素的位置
    return pos == last ? *(last - 1) : *pos;
  }
  // 初始化
  HashTable() { _table.resize(__stl_next_prime(0)); }
  ~HashTable() {
    for (size_t i = 0; i < _table.size(); ++i) {
      Node *cur = _table[i];
      while (cur) {
        Node *next = cur->_next;
        delete cur;
        cur = next;
      }
      _table[i] = nullptr;
    }
  }
  bool insert(const pair<K, V> &kv) {
    Hash hs;
    size_t hashi = hs(kv.first) % _table.size();
    // 擴容
    // 這路就不用判斷負載因子了，因爲相同的位置都會像鏈表一樣串接起來
    if (_n == _table.size()) {
      // 怎麼擴？
      vector<Node *> newht(__stl_next_prime(_table.size() + 1), nullptr);
      for (size_t i = 0; i < _table.size(); ++i) {
        // 挪動數據
        Node *cur = _table[i];
        while (cur) {
          // 先保留_next;
          Node *next = cur->_next;
          // 將舊錶的數據挪動到新表
          size_t hashi = hs(cur->_kv.first) % newht.size();
          cur->_next = newht[hashi];
          newht[hashi] = cur;

          cur = next;
        }
        _table[i] = nullptr;
      }
      _table.swap(newht);
    }
    // 如果有其他數據 => 直接頭插
    Node *newnode = new Node(kv);
    newnode->_next = _table[hashi];
    _table[hashi] = newnode;
    ++_n;
    return true;
  }

  Node *find(const K &key) {
    Hash hs;
    size_t hash0 = hs(key) % _table.size();
    Node *cur = _table[hash0];
    while (cur) {
      if (cur->_kv.first == key) {
        return cur;
      }
      cur = cur->_next;
    }
    return nullptr;
  }
  bool erase(const K &key) {
    Hash hs;
    size_t hash0 = hs(key) % _table.size();
    Node *cur = _table[hash0];
    Node *prev = nullptr;
    while (cur) {
      if (cur->_kv.first == key) {
        if (prev == nullptr) { // prev 爲空 代表刪除的是第一個數據
          _table[hash0] = cur->_next;
        } else {
          prev->_next = cur->_next;
        }
        delete cur;
        --_n;
        return true;
      }
      prev = cur;
      cur = cur->_next;
    }
    return false;
  }

private:
  vector<Node *> _table;
  size_t _n = 0; // 數據個數
};
void HashBucketTest1() {
  HashTable<int, int> ht;
  ht.insert(make_pair(1, 1));
  ht.insert(make_pair(2, 2));
  ht.insert(make_pair(3, 3));
  ht.insert(make_pair(4, 4));
  ht.insert(make_pair(5, 5));
  ht.insert(make_pair(6, 6));
  ht.insert(make_pair(7, 7));
  ht.insert(make_pair(8, 8));
  ht.insert(make_pair(9, 9));
  ht.insert(make_pair(10, 10));
}
void HashBucketTest2() {
  HashTable<int, int> ht;
  ht.insert(make_pair(1, 1));
  ht.insert(make_pair(2, 2));
  ht.insert(make_pair(3, 3));
  ht.insert(make_pair(4, 4));
  ht.insert(make_pair(5, 5));
  ht.erase(2);
  ht.erase(3);
  ht.erase(4);
  ht.erase(5);
  ht.erase(6);
  ht.erase(7);
  ht.erase(8);
  ht.erase(9);
}
} // namespace HashBucket