C ++ связанное копирование хеш-таблицы

Question

Я должен реализовать HashTable со связанными списками. Это почти сделано (все еще отсутствуют шаблоны, мы сделаем это вовремя), но я застрял в чем-то. По сути, я хочу изменить размер моей хеш-таблицы, когда коэффициент загрузки достигает заданного значения, скажем, 50%. Но я не знаю, как мне это сделать. У меня есть базовая c идея:

1. Создать временный HT с новым размером
2. Ха sh все данные в каждом списке от старого HT до временного
3. Удалить старый HT
4. Вернуть временный 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:

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
}

... и затем вызвать swapContents(HT) в конце метода resize(), чтобы HT становится более старой / меньшей HashTable (и удаляется), а this становится новой / большей таблицей.