当前位置：首页 > article >正文

用C++使用带头单向非循环链表，实现一个哈西桶

article 2025/1/7 4:15:26

用C++使用带头单向非循环链表，实现一个哈西桶
在C++中使用带头单向非循环链表来实现哈希桶是一种常见的做法，特别是在实现哈希表时。哈希桶是哈希表的基本存储单元，用于存储具有相同哈希值的元素。以下是一个简单的示例，展示了如何使用带头单向非循环链表来实现哈希桶。

首先，我们定义一个节点结构来表示链表中的每个节点：


 #include <iostream>
#include <list>

template <typename K, typename V>
struct Node {
    K key;
    V value;
    Node* next;

    Node(const K& k, const V& v) : key(k), value(v), next(nullptr) {}
};

然而，为了简化实现并利用C++标准库的功能，我们可以直接使用std::list来代替手动实现的链表。std::list是一个双向链表，但在这里我们只会用到它单向遍历的能力，并且它会处理节点的内存管理。为了模拟带头单向非循环链表的行为，我们可以在每个哈希桶内部维护一个空的哨兵节点（头节点），其next指针指向第一个实际存储数据的节点。

接下来，我们定义哈希桶结构：

 template <typename K, typename V>
class HashBucket {
private:
    Node<K, V>* head; // 哨兵节点（头节点）

public:
    HashBucket() {
        head = new Node<K, V>(K(), V()); // 创建一个空的哨兵节点
        head->next = nullptr;
    }

    ~HashBucket() {
        Node<K, V>* current = head->next;
        while (current != nullptr) {
            Node<K, V>* next = current->next;
            delete current;
            current = next;
        }
        delete head;
    }

    void insert(const K& key, const V& value) {
        Node<K, V>* newNode = new Node<K, V>(key, value);
        
        // 插入到链表头部（为了简化，这里不保持顺序）
        newNode->next = head->next;
        head->next = newNode;
    }

    bool search(const K& key, V& result) {
        Node<K, V>* current = head->next;
        while (current != nullptr) {
            if (current->key == key) {
                result = current->value;
                return true;
            }
            current = current->next;
        }
        return false;
    }

    bool remove(const K& key) {
        Node<K, V>* current = head;
        while (current->next != nullptr) {
            if (current->next->key == key) {
                Node<K, V>* toDelete = current->next;
                current->next = toDelete->next;
                delete toDelete;
                return true;
            }
            current = current->next;
        }
        return false;
    }
};

注意：上面的remove函数有一个逻辑错误，因为current应该从head->next开始遍历，而不是从head开始（因为head是哨兵节点）。此外，为了更贴近带头单向非循环链表的概念，我们通常不会在链表中删除节点时释放头节点，因为头节点是固定存在的。下面是修正后的remove函数：

 bool remove(const K& key) {
        Node<K, V>* current = head->next;
        Node<K, V>* prev = head;
        while (current != nullptr) {
            if (current->key == key) {
                prev->next = current->next;
                delete current;
                return true;
            }
            prev = current;
            current = current->next;
        }
        return false;
    }

最后，我们可以定义一个哈希表来使用这些哈希桶：
使用类模板，传入函数作为函数的参数

 template <typename K, typename V>
class HashTable {
private:
    HashBucket<K, V>* buckets;
    size_t bucketCount;
    size_t (*hashFunction)(const K&);

public:
    HashTable(size_t bucketCount, size_t (*hashFunction)(const K&))
        : bucketCount(bucketCount), hashFunction(hashFunction) {
        buckets = new HashBucket<K, V>[bucketCount];
    }

    ~HashTable() {
        delete[] buckets;
    }

    void insert(const K& key, const V& value) {
        size_t bucketIndex = hashFunction(key) % bucketCount;
        buckets[bucketIndex].insert(key, value);
    }

    bool search(const K& key, V& result) {
        size_t bucketIndex = hashFunction(key) % bucketCount;
        return buckets[bucketIndex].search(key, result);
    }

    bool remove(const K& key) {
        size_t bucketIndex = hashFunction(key) % bucketCount;
        return buckets[bucketIndex].remove(key);
    }
};

为了使用这个哈希表，你需要提供一个哈希函数，例如：

 size_t stringHashFunction(const std::string& str) {
    size_t hash = 0;
    for (char c : str) {
        hash = hash * 31 + c;
    }
    return hash;
}

然后你可以这样创建和使用哈希表：

 int main() {
    HashTable<std::string, int> hashTable(10, stringHashFunction);
    hashTable.insert("one", 1);
    hashTable.insert("two", 2);

    int value;
    if (hashTable.search("one", value)) {
        std::cout << "Found 'one' with value " << value << std::endl;
    } else {
        std::cout << "'one' not found" << std::endl;
    }

    hashTable.remove("one");
    if (!hashTable.search("one", value)) {
        std::cout << "'one' has been removed" << std::endl;
    }

    return 0;
}