c++ - 实现 Resize 函数的哈希表

Question

我接到一项任务，要调整哈希表实现以允许动态调整大小。虽然我四处寻找线索和信息，但我仍然对哈希表的行为方式以及我应该如何调整大小感到困惑。有人告诉我我需要添加一个调整大小的函数，在插入中调用它并修改构造函数。我认为我已经正确地完成了插入，看起来很简单，但调整大小本身和构造函数是我正在努力解决的问题。

编辑:所以我已经研究了 resize 函数、插入和构造函数，但是我在 resize() 中的 for 循环中遇到错误，无法将旧数据插入到更大的表中，我不确定是什么现在出问题了。有什么想法吗？

这是标题:

#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib>    // Provides size_t
#include <cassert>  // Provides assert

namespace main_savitch_12A
{
template <class RecordType>
class table
{
public:
size_t CAPACITY; 
    // CONSTRUCTOR
    table( );
    // MODIFICATION MEMBER FUNCTIONS
    void insert(const RecordType& entry);
    void remove(int key);
void resize( );
    // CONSTANT MEMBER FUNCTIONS
    bool is_present(int key) const;
    void find(int key, bool& found, RecordType& result) const;
    size_t size( ) const { return used; }
private:
    // MEMBER CONSTANTS -- These are used in the key field of special records.
    enum { NEVER_USED = -1 };
    enum { PREVIOUSLY_USED = -2 };
    // MEMBER VARIABLES
    RecordType *data; //[CAPACITY];
    size_t used;
    // HELPER FUNCTIONS
    size_t hash(int key) const;
    size_t next_index(size_t index) const;
    void find_index(int key, bool& found, size_t& index) const;
    bool never_used(size_t index) const;
    bool is_vacant(size_t index) const;
};

构造函数实现:

template <class RecordType>
table<RecordType>::table( )
{
    CAPACITY = 30;
    data = new RecordType[CAPACITY];

size_t i;

used = 0;
for (i = 0; i < CAPACITY; ++i)
    data[i].key = NEVER_USED;

}

调整大小实现:

template <class RecordType>
void table<RecordType>::resize( )
{

    RecordType *oldData = data;
    int oldSize = CAPACITY;
    CAPACITY *= CAPACITY;

    //create a new table
    RecordType *newData;
    newData = new RecordType[CAPACITY];

    size_t i;
    used = 0;
    for (i = 0; i < CAPACITY; i++)
        newData[i].key = NEVER_USED;

    //place data from old table to new, larger table.
    for (int i = 0; i < oldSize; i++)
    {
        insert(newData[hash(i)]); //this is where I'm having trouble.
    }

    data = newData;
    delete[] oldData;
}

插入实现:

template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
// Library facilities used: cassert
{
    bool already_present;   // True if entry.key is already in the table
    size_t index;        // data[index] is location for the new entry

    assert(entry.key >= 0);

    // Set index so that data[index] is the spot to place the new entry.
    find_index(entry.key, already_present, index);

    // If the key wasn't already there, then find the location for the new entry.
    if (!already_present)
    {
        if (size( ) >= CAPACITY)
        {
            resize( ); // resize the table.

            insert(entry); // reinsert entry into new table.
        }
        else if (size( ) < CAPACITY)
        {
            index = hash(entry.key);

            while (!is_vacant(index))
                index = next_index(index);
            ++used;
        }
    }

    data[index] = entry;
    size_t i;
    for (i=0; i<CAPACITY; i++) cout << data[i].key << ' ';
    cout << endl;
}

感谢您的帮助!

Answer 1

目前，data 是一个固定大小的数组。你需要一个可变大小的存储

RecordType data[CAPACITY];

所以，data需要是一个指针而不是一个固定的数组，需要在构造函数中动态分配。

当然，还要将 CAPACITY 从常量更改为变量(每个表，所以不是 static - 我会将其名称更改为看起来不像的名称也像宏/常量。

这一点“差不多了”:

table *newT;
newT = new table(newSize);

类型不应该是哈希表，而是RecordType。

而且，正如评论所说，需要将当前数据转移到新数据中，然后将新表作为当前数据。最后，删除现在的旧数据。

编辑:我故意不为您编写代码。你的任务是学习。大约 20 多年前，我编写了可动态调整大小的哈希表，但我认为我现在不需要练习它。你是那个学习如何去做的人。