C++链接哈希表复制

Question

我必须用链表实现哈希表。它几乎完成了（仍然缺少模板，会及时完成），但我被困在某事上。基本上，我想在负载因子达到给定值（比如 50%）时调整哈希表的大小。但我不知道我应该怎么做。我有一个基本的想法：

创建一个新大小的临时 HT
将每个列表中的所有数据从旧 HT 散列到临时 HT
删除旧的 HT
Return临时HT

虽然我想不出它的实现...

这是我目前的情况：

//List:
struct Node
{
  string data;
  Node *next;
};

class List
{
  private:
    Node *head, *tail;
    int length;
    friend class HashTable;
  public:
    List();
    List(const List &L);
    //~List() {delete this;};
    List& operator =(List L);
    int find(string);
    void insert(string value);
    void remove_head();
    void remove_poz(int);
    void remove_tail();
    void clear();
    void display();
};

List::List()
{
   head = NULL;
   tail = NULL;
   length = 0;
}

List::List(const List& L)
{
    Node** temp = &head;
    const Node* source = L.head;
    while(source)
    {
        *temp = new Node(*source);
        temp = &(*temp)->next;
        source = source->next;
    }
}

List& List::operator =(List L)
{
  swap(head, L.head);
  return *this;
}

void List::insert(string value)
{
  Node* temp = new Node;
  temp->data = value;
  temp->next = NULL;

  if (!head)
      head = temp;
  if (tail)
      tail->next = temp;
  tail = temp;
  length++;
}

void List::display()
{
  Node *temp = new Node;
  temp = head;
  while (temp != NULL)
  {
    cout<<temp->data<<" ";
    temp = temp->next;
  }
  delete temp;
}


//HashTable:
class HashTable
{
  private:
    List *table;
    float load, stored;
    int slots;
    friend class List;
  public:
    HashTable();
    HashTable(int);
    ~HashTable();
    int hashFunc(string key);
    int findTable(string);
    int findList(string);
    HashTable& operator =(const HashTable&);
    void resize();    //I need this one
    void insert(string);
    void remove(string);
    void clear(int);
    void clear();
    void display();
};

HashTable::HashTable()
{
  stored = 0;
  load = 0.00;
  slots = 15;
  table = new List[slots];
}

HashTable::HashTable(int size)
{
    stored = 0;
    load = 0.00;
    slots = size;
    table = new List[slots];
}

int HashTable::hashFunc(string key)
{
  unsigned int i, ind = 0;
  for (i = 0; i<key.length(); ++i)
      ind = ind + key[i];
  ind %= slots;
  return ind;
}

HashTable& HashTable::operator =(const HashTable& T) //I suppose it is incorrect
{
    int i;
    HashTable temp(T.slots);
    for (i = 0; i < slots; ++i)
    {
        temp.table[i] = T.table[i];
    }

    return temp;
}

void HashTable::insert(string value)
{
  int ind = hashFunc(value);

  table[ind].insert(value);

  if (!table[ind].head->next) stored++;

  load = stored / slots;
  if (load > 0.50) resize();
}

（注：此处仅展示可能需要的功能）

如有任何帮助、更正或建议，我们将不胜感激:)

更新：

设法完成这个：

void HashTable::resize()
{
  int i;
  int newSize = slots * 2;
  int newLoad = stored / newSize;
  HashTable HT(newSize);
  Node* temp;

  for (i = 0; i < slots; ++i)
  {
      temp = table[i].head;
      while (temp != NULL)
      {
          HT.insert(temp->data);
          temp = temp->next;
      }
  }
}

现在我有了一个新的HashTable，名为HT，它的大小是原来的两倍，并且所有元素都已正确插入。但是我不知道如何进行。

Answer 1

最简单的方法是将 swapContents() 方法添加到 HashTable class:

void HashTable::swapContents(HashTable & rhs)
{
   std::swap(table, rhs.table);
   std::swap(load, rhs.load);
   std::swap(stored, rhs.stored);
   std::swap(slots, rhs.slots);
   // any other member-variables of the HashTable class would get swapped here too
}

... 然后在 resize() 方法的末尾调用 swapContents(HT)，这样 HT 就变成了 older/smaller HashTable（并被丢弃），而 this 变成了newer/larger table.

C++链接哈希表复制

C++ linked hashtable copying

c++

hashtable