HashTable在C++中的实现

Question

我做了一个简单的哈希表，我想知道是否有任何方法来提高搜索时间的效率。我的表类名为Dictionary，因为C#污染了我。

我设置它的方式是，Dictionary有一个Buckets数组，这是一个修改过的链表，它的Nodes存储字符串键以及任何其他数据。

我使用一个模块化的散列函数来获取Dictionary应该访问的数组的索引，然后在该索引处使用Bucket搜索/插入。

Dictionary类：

#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_

#include <iostream>
#include <string>

#include "bucket.h"

using namespace std;

template <class T>
class Dictionary
{
private:

    Bucket<T>* mBuckets;

    // Number of buckets
    int mCount;

    int hash(string key)
    {
        // Modular hashing algorithm

        int value = 0;

        for (int i = 0; i < key.length(); i++)
            value += key[i];

        return value % mCount;
    }

public:
    Dictionary();
    Dictionary(int mCount);
    ~Dictionary();

    bool containsKey(string key);
    void display();
    int getCount();
    T getData(string key);
    bool insert(string key, T value);
    bool isEmpty();
};

// ********************************************************
//                Constructor / Destructor
// ********************************************************

template <class T>
Dictionary<T>::Dictionary()
{
    // Default mCount to 16
    this->mCount = 16;

    // Define mBins
    mBuckets = new Bucket<Item<T>>[mCount];
}

template <class T>
Dictionary<T>::Dictionary(int mCount)
{
    // Default mCount to 16 if invalid
    this->mCount = (mCount >= 0 ? mCount : 16);

    // Define mBins
    mBuckets = new Bucket<T>[mCount];
}

template <class T>
Dictionary<T>::~Dictionary()
{
    delete[] mBuckets;
}


// ********************************************************
//                       Functions
// ********************************************************

template <class T>
bool Dictionary<T>::containsKey(string key)
{
    int bin = hash(key);

    return mBuckets[bin].isExist(key);
}

template <class T>
void Dictionary<T>::display()
{
    cout
        << " Dictionary - Items:" << getCount() << "\n"
        << "*********************** \n";

    for (int i = 0; i < mCount; i++)
    {
        cout << left << i << ": ";

        mBuckets[i].display();

        cout << "\n\n";
    }
}

template <class T>
void Dictionary<T>::displayDistribution()
{
    cout
        << " Dictionary - Distribution:" << getCount() << "\n"
        << "*********************** \n";

    for (int i = 0; i < mCount; i++)
    {
        cout 
            << left 
            << i << ": " << mBuckets[i].getCount();

        cout << "\n";
    }
}

template <class T>
int Dictionary<T>::getCount()
{
    int count = 0;
    for (int i = 0; i < mCount; i++)
    {
        count += mBuckets[i].getCount();
    }

    return count;
}

template <class T>
T Dictionary<T>::getData(string key)
{
    int bin = hash(key);

    return mBuckets[bin].getData(key);
}

template <class T>
bool Dictionary<T>::insert(string key, T value)
{
    int bin = hash(key);

    mBuckets[bin].insert(key, value);

    return true;
}

template <class T>
bool Dictionary<T>::isEmpty()
{
    return getCount() == 0;
}

#endif

Bucket类：

#ifndef _BUCKET_H_
#define _BUCKET_H_

#include <iostream>

using namespace std;

template <class T>
class Bucket
{
private:
    template <class T>
    struct Node
    {
        string mKey;
        T mData;
        Node<T> *mNext, *mPrevious;

        Node()
        {
            mKey = "";
            mData = T();
            mNext = NULL;
            mPrevious = NULL;
        }

        Node(string key, T data)
        {
            mKey = key;
            mData = data;
            mNext = NULL;
            mPrevious = NULL;
        }
    };

    Node<T> *mHead, *mTail;
    int mCount;

public:
    Bucket();
    ~Bucket();


    int getCount();
    bool isEmpty();
    bool isExist(string searchKey);
    bool remove(string searchKey);

    void display();
    void insert(string key, T data);

    T getData(string key);
};

// ********************************************************
//                Constructor / Destructor
// ********************************************************

template <class T>
Bucket<T>::Bucket()
{
    mHead = NULL;
    mTail = NULL;
    mCount = 0;
}

template <class T>
Bucket<T>::~Bucket()
{
    Node<T> *tmp, *toBeDeleted;

    tmp = mHead;

    // removing node by node
    while (tmp != NULL)
    {
        toBeDeleted = tmp;
        tmp = tmp->mNext;
        toBeDeleted->mNext = NULL;

        delete toBeDeleted;
    }

    // reinitialize the pointers
    mHead = NULL;
    mTail = NULL;
    mCount = 0;
}


// ********************************************************
//                       Functions
// ********************************************************

template <class T>
int Bucket<T>::getCount()
{
    return mCount;
}


template <class T>
bool Bucket<T>::isEmpty()
{
    return mCount == 0;
}


template <class T>
bool Bucket<T>::isExist(string searchKey)
{
    Node<T> *tmp = mHead;

    while (tmp != NULL)
    {
        if (tmp->mKey == searchKey)
            return true;

        tmp = tmp->mNext;
    }

    return false;
}


template <class T>
bool Bucket<T>::remove(string searchKey)
{
    Node<T> *tmp, *prev;

    if (mHead == NULL)
        return false;
    else if (searchKey < mHead->mKey || searchKey > mTail->mKey)
        return false;

    tmp = mHead;
    prev = NULL;

    for (int i = 0; i < mCount; i++)
    {
        if (searchKey == tmp->mKey)
            break;

        prev = tmp;
        tmp = tmp->mNext;
    }

    if (tmp != NULL)
    {
        if (tmp == mHead)
        {
            tmp = mHead;

            mHead = mHead->mNext;
            if (mHead == NULL)
                mTail = NULL;

            tmp->mNext = NULL;
        }
        else if (tmp == mTail)
        {
            prev->mNext = NULL;
            mTail = prev;
        }
        else
        {
            prev->mNext = tmp->mNext;
            tmp->mNext = NULL;
        }

        delete tmp;
        mCount--;

        return true;
    }

    return false;
}


template <class T>
void Bucket<T>::display()
{
    Node<T> *tmp;

    if (mHead == NULL)
    {
        cout << "{ }\n";
        return;
    }

    cout << "{ ";
    tmp = mHead;
    while (tmp != NULL)
    {
        cout
            << "["
            << tmp->mKey
            << ", "
            << tmp->mData
            << "]"
            << (tmp != mTail ? ", " : " }");

        tmp = tmp->mNext;
    }
    cout << "\n";
}


template <class T>
void Bucket<T>::insert(string key, T data)
{
    Node<T> *tmp, *oneBefore, *newNode;

    newNode = new Node<T>(key, data);
    if (newNode == NULL)
        return;

    if (mHead == NULL)
    {
        mHead = newNode;
        mTail = newNode;
    }
    else
    {
        if (key < mHead->mKey) // Put at head
        {
            newNode->mNext = mHead;

            newNode->mPrevious = NULL;

            mHead = newNode;
        }
        else if (key > mTail->mKey) // Put at tail
        {
            mTail->mNext = newNode;

            newNode->mPrevious = mTail;

            mTail = newNode;
        }
        else if (key == mHead->mKey || key == mTail->mKey) // Dont insert if already added
        {
            delete newNode;
            return;
        }
        else
        {
            tmp = mHead;
            oneBefore = mHead;

            // Iterate through list to find position
            while (tmp->mKey < key)
            {
                oneBefore = tmp;

                tmp = tmp->mNext;
            }

            if (tmp->mKey != key)
            {
                newNode->mNext = tmp;
                tmp->mPrevious = newNode;

                oneBefore->mNext = newNode;
                newNode->mPrevious = oneBefore;
            }
            else
            {
                delete newNode;
                return;
            }
        }
    }

    mCount++;
}


template <class T>
T Bucket<T>::getData(string key)
{
    Node<T> *tmp = mHead;

    while (tmp != NULL)
    {
        if (tmp->mKey == key)
            return tmp->mData;

        tmp = tmp->mNext;
    }

    return T();
}

#endif

我一直在测试我的搜索函数的运行时间，方法是从一个包含398484个唯一条目的文件中加载对，这些条目都是按字母顺序排列的。这是文件的链接。

我还有其他一些问题，主要是，这是一个正确的哈希表实现吗？听起来很奇怪，但我以前从未做过哈希表，所以我所知道的是从许多堆栈溢出和Google链接中派生出来的。

按照目前的实现方式，我的存储桶可以是任意大的，并且每个桶的项目数平均约为(numItems/numBuckets)。

在文件的开头、中间和结尾搜索键的结果：

搜索键:找到的搜索键。搜索时间: 2.82251898e-05秒。关键字:a值: 1411153搜索键:找到叶肉搜索键。搜索时间: 0.001279370876秒。关键词:叶肉值: 1418758搜索键: zyzzyvas搜索键找到。搜索时间: 0.001327610291秒。键: zyzzyvas值: 2223394

Answer 1

首先也是最重要的

有std::unordered_map。如果你只需要一个散列图，就用它。

怎么了，

1. 您的散列是一个int，如果您的字符串由负字符或溢出组成，则在末尾将得到一个负值。在C/C++中，模运算符(%)返回负输入的负值。
2. 这是如何编译的？什么东西？mBuckets = new Bucket<Item<T>>[mCount];

性能

1. 您的代码不支持再平衡。如果您想提供通用性能，这是非常必要的。见std::unordered_map::rehash。
2. 分析你的代码，找出花在哪里的时间。
3. 当以泛型参数作为参数并返回它们时，请避免不必要的副本。通常由const&和return (const)&采取。这既适用于std::string参数，也适用于泛型类型T。如果这确实是大量使用的库代码，请考虑使用完美的转发。

改进

点

1. 不要使用using std。尤其是在图书馆的代码里。
2. 你不提供const接口。你甚至不能在isEmpty上问const Dictionary
3. 您的哈希函数是错误的:仅仅添加这些值并不能很好地工作。"foo“的散列与"oof”相同。
4. 按照预期的语义实现标准操作符，例如用于元素访问的operator[]。
5. 使用nullptr而不是NULL。
6. 使用std::unique_ptr<>来拥有指针，而不是手动管理内存。
7. 使用初始化程序列表，而不是在构造函数中初始化成员。
8. 不要两次实现构造函数的所有方面，如果可能的话，从另一个方面依赖其中一个
9. 当您的new返回NULL时，简单地返回是一个非常糟糕的主意。
10. 为迭代器提供begin()/end()。
11. 不要在模板库代码中实现输出。
12. 为什么使用双链接节点？哈希表的全部要点是，无论如何，在一个桶中永远不应该有过多的节点。Bucket<T>::insert令人难以置信地难以阅读。
13. 使用算法而不是原始循环。
14. 您的手动new / delete可能会在异常发生时立即开始泄漏。

由于积分的数量，我不能详细介绍每一个人。大部分的点都是标准的项目，应该容易搜索。请问你是否有具体的问题。

Answer 2

在我看来，这很像我在1995年左右为这样一个任务编写的代码。这是合理的工作，但相当单一和不灵活。

例如，它基本上试图复制vector的大部分功能，但我并不认为它提供了很大的改进。它还将键类型限制为string，但是(同样)这样做的回报很小。

因此，我首先将存储类型和键类型指定为模板参数：

template <class Key, class T>
class Dictionary {
// ...

然后，它将使用(例如)一些外部hash(Key)来实际拥有密钥。或者，值得考虑更明确地指定哈希类型：

template <class Key, class T, class Hash = myHash<Key> >
class Dictionary {  
    Hash hasher;
public:
   Dictionary(Hash h = Hash()) : hasher(h) {}
   // ...

这使您可以为典型类型(如string )提供合理的哈希函数，但仍然允许用户使用不同的哈希方法覆盖它(例如，具有某些特定哈希函数的特定属性的字符串)。

至于实现细节，除非我有特定的理由不这样做，否则我可能会使用std::vector<std::forward_list<std::pair<Key, T>>>作为动态数组类型。如果你选择的话，你可以使用其他类型(做出这样的决定有很好的理由)--问题不在于具体的类型，而在于你不需要把你自己的代码直接滚到单个晶体管的水平(好吧，我有点夸张了，但你明白了)。如果你想要一个链接列表，有几百个已经写好了--你不需要再做一次了。同样，动态数组，等等。