我该如何添加与表的每个哈希地址相对应的计数器

Question

我正在使用链表创建一个哈希表，我让表运行良好，但我需要为表中的每个地址创建一个计数器。

程序必须跟踪表中每个地址的当前冲突计数。为此，每个地址都必须有一个计数器。地址为0。。tableSize-1.程序每次插入一个元素时，都必须递增该元素的哈希地址对应的计数器。类似地，每当从表中删除某个元素时，必须递减与该元素的哈希地址相对应的计数器。

我该怎么做？我应该在列表或哈希表中添加一个变量来跟踪吗。我不想包含太多的代码让事情变得混乱，所以我会包含我的linkedList.cpp和Hashtable.cpp中的片段。

哈希表.cpp

#include "HashTable.h"
// Constructs the empty Hash Table object.
// Array length is set to 13 by default.
HashTable::HashTable( int tableLength )
{
if (tableLength <= 0) tableLength = 13;
array = new LinkedList[ tableLength ];
length = tableLength;
}
// Returns an array location for a given item key.
int HashTable::hash( string itemKey )
{
int hashAddress=0;

for ( int i = 0; i < itemKey.length(); i++ )
   hashAddress= atoi(itemKey.c_str());
return (hashAddress  ) % length;
}
// Adds an item to the Hash Table.
void HashTable::insertItem( Item * newItem )
{
int index = hash( newItem -> key );
array[ index ].insertItem( newItem );
}
// Deletes an Item by key from the Hash Table.
// Returns true if the operation is successful.
bool HashTable::removeItem( string itemKey )
{
int index = hash( itemKey );
return array[ index ].removeItem( itemKey );
}
// Returns an item from the Hash Table by key.
// If the item isn't found, a null pointer is returned.
Item * HashTable::getItemByKey( string itemKey )
{

链接列表.cpp

#include "LinkedList.h"
// Constructs the empty linked list object.
// Creates the head node and sets length to zero.
LinkedList::LinkedList()
  {
   head = new Item;
   head -> next = NULL;
   length = 0;
}
// Inserts an item at the end of the list.
void LinkedList::insertItem( Item * newItem )
{
if (!head -> next)
{
    head -> next = newItem;
    length++;
    return;
}
Item * p = head;
Item * q = head;
while (q)
{
    p = q;
    q = p -> next;
}
p -> next = newItem;
newItem -> next = NULL;
length++;
}
// Removes an item from the list by item key.
// Returns true if the operation is successful.
bool LinkedList::removeItem( string itemKey )
{
if (!head -> next) return false;
Item * p = head;
Item * q = head;
while (q)
{
    if (q -> key == itemKey)
    {
        p -> next = q -> next;
        delete q;
        length--;
        return true;
    }
    p = q;
    q = p -> next;
}
return false;
}
// Searches for an item by its key.
// Returns a reference to first match.
// Returns a NULL pointer if no match is found.
Item * LinkedList::getItem( string itemKey )

Answer 1

试试这个：

class HashTable {
    private:
        std::vector<int>* m_collisionsTracker = nullptr;
        ...
}
HashTable::HashTable(int tableLength) {
    ...
    m_collisionsTracker = new std::vector<int>(length);
    std::fill(m_collisionsTracker.begin(), m_collisionsTracker.end(), 0);
}
HashTable::~HashTable() {
    ...
    delete m_collisionsTracker;
}
void HashTable::insertItem(Item * newItem) {
    int index = hash(newItem->key);
    array[index].insertItem(newItem);
    m_collisionsTracker[index] += 1; // If I right understand it's what you need.
}
...
void LinkedList::insertItem(Item* newItem) {
    Item* p = head;
    while (p->next) {
        p = p->next;
    }
    p->next = newItem;
    newItem->next = nullptr;
    length++;
}