hashtable：如何理解这种基于STL中List的hashtable的实现

Question

我正在学习使用 C++ 构建哈希table。并找到这个 post：https://www.geeksforgeeks.org/c-program-hashing-chaining/。

它实现了一个简单和基本的散列版本table（非生产级别），带有链接以修复散列冲突问题。

我在本地遵循了 post 和运行它并且按预期工作。实现如下：

#include <iostream>
#include <list>

using namespace std;

class Hash {
    int BUCKET;
    list<int> *table; // confusing point1 

    public:
        Hash(int V);

        void insertItem(int key);

        void deleteItem(int key);

        int hashFunction(int x) {
            return (x % BUCKET);
        }

        void displayHash();
};

Hash::Hash(int b) {
    this->BUCKET = b;
    table = new list<int>[BUCKET]; // confusing point2
}

void Hash::insertItem(int key) {
    int index = hashFunction(key);
    table[index].push_back(key);
}

void Hash::deleteItem(int key) {
    int index = hashFunction(key);
    list <int> :: iterator i;
    for (i = table[index].begin(); i != table[index].end(); i++) {
        if (*i ==  key) {
            break;
        }
    }

    if (i != table[index].end()) {
        table[index].erase(i);
    }
}

void Hash:: displayHash() {
    for (int i = 0; i < BUCKET; i++) {
        cout << i;
        for (auto x : table[i]) {
            cout << "-->" << x;
        }
        cout << endl;
    }
}

// Driver program  
int main() 
{ 
  // array that contains keys to be mapped 
  int a[] = {15, 11, 27, 8, 12}; 
  int n = sizeof(a)/sizeof(a[0]); 

  // insert the keys into the hash table 
  Hash h(7);   // 7 is count of buckets in 
               // hash table 
  for (int i = 0; i < n; i++)  
    h.insertItem(a[i]);   

  // delete 12 from hash table 
  h.deleteItem(12); 

  // display the Hash table 
  h.displayHash(); 

  return 0; 
}

关于这个实现我有两个困惑点：

list<int> *table : table 应该是 buckets 数组。正确的？ list<int> * 应该是列表类型的指针吧？它在这里如何运作？
table = new list<int>[BUCKET]: 我查了很多相关的列表
文件。但没有找到 [] 的工作原理？

Answer 1

list<int> *table : table should be buckets array. Right? list<int>* should be list type pointer, right? How it works here?

在这个糟糕的代码中，table 是一个指向 list<int> 的指针，但是当你有一个指向某个项目的指针并且 碰巧知道 时那里有一个连续元素的数组，您可以像数组一样对其进行索引，因此 table[0] 与 *table 相同，table[1] 将是 [= 之后内存中的下一个 list<int> 15=]等等。

table = new list<int>[BUCKET]: I checked many list related documents. but didn't find how the [] works?

这是创建一个 list<int> 对象数组并将它们的地址保存在 table 中的初始化，所以我们确实“碰巧知道”数组在那里并且可以索引 table 作为一个数组。例如，在 displayHash 函数中，您会看到 for (auto x : table[i]) - 这意味着 x 从存储桶 i 的 list<int> 中获取每个值，即 table[i].

该代码还需要 delete[] table 的析构函数，否则当 Hash 对象的默认析构函数在未进行任何清理的情况下运行时，所有内存将被泄漏。

您还应注意，它允许您插入同一密钥的多个副本 - 此功能的正确和完整实现是 std::unordered_multiset。

最低限度地清理它 - 无需采取后续步骤使用模板来让您将其用于其他类型、添加迭代器等：

class Hash {
    vector<list<int>> table_;

  public:
    Hash(size_t size) : table_{size} { }

    void insert(int key) {
        table_[bucket(key)].push_back(key);
    }

    void erase(int key) {
        auto& bucket_list = table_[bucket(key)];
        auto it = find(bucket_list.begin(), bucket_list.end(), key);
        if (it != bucket_list.end())
            bucket_list.erase(it);
    }

    int bucket(int key) const {
        return hash(key) % table_.size();
    }

    static int hash(int key) {
        return key;
    }

    // example usage: my_hash.display(std::cout);
    void display(std::ostream& os) const {
        for (size_t i = 0; i < table_.size_; ++i) {
            os << '[' << i << ']';
            for (auto x : table[i])
                 os << "-->" << x;
            os << '\n';
        }
    }

    // extensions ===================================
    bool contains(int key) const {
        auto& bucket_list = table_[bucket(key)];
        auto it = find(bucket_list.begin(), bucket_list.end(), key);
        return it != bucket_list.end();
    }

    // example usage:
    //   my_hash.visit([](auto key) { std::cout << key << '\n'; });
    template <typename Functor)
    void visit(Functor functor) const {
        for (size_t i = 0; i < table_.size_; ++i)
            for (auto x : table[i])
                 functor(x);
    }
};

hashtable：如何理解这种基于STL中List的hashtable的实现

hashtable: how to understand this implementation of hashtable based on List in STL

c++

hashtable

list