时间戳

首页 > 解决方案 > hashtable：如何理解这种基于STL中List的hashtable实现

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

问题描述

我正在学习用 C++ 构建一个哈希表。并找到这篇文章：https ://www.geeksforgeeks.org/c-program-hashing-chaining/ 。

它实现了一个简单且基本的哈希表版本（不是生产级别），带有链接以解决哈希冲突问题。

我关注了帖子并在本地运行它，它按预期工作。实现如下：

#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; 
}

关于这个实现，我有两个令人困惑的地方：

标签： c++listhashtable

解决方案

list<int> *table: table 应该是 buckets 数组。正确的？list<int>*应该是列表类型指针吧？它是如何在这里工作的？

在这个糟糕的代码中，table是一个指向 a 的指针list<int>，但是当你有一个指向一个项目的指针并且碰巧知道那里有一个连续元素的数组时，你可以像数组一样索引它，所以和,table[0]一样是下一个在内存之后等等。*tabletable[1]list<int>table[0]

table = new list<int>[BUCKET]: 我查了很多清单相关的文件。但没有找到 [] 的工作原理？

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

代码还需要一个析构函数，否则当对象的默认析构函数不做任何清理运行delete[] table时，所有内存都会泄漏。Hash

您还应该知道，它允许您插入同一个密钥的多个副本——该功能的正确且完整的实现是 be 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);
    }
};

推荐阅读