测试哈希表

Question

我需要测试我的哈希表是否工作正确，但它没有通过测试，因为我的哈希表似乎没有找到任何元素。在编译器中没有问题，在调试器中也没有问题，它在代码逻辑的某个地方。我认为这是因为insert()函数，但对我来说似乎还好，因为我试图再次改变它的时间，但没有任何帮助。你能检查一下代码并告诉我有什么问题吗?

控制台显示如下:

我的散列表:时间:0.610612，后插入:270717，后擦除:270717，发现:0STL unordered_map:时间:0.67032，后插入:316124，后擦除:115991，后发现:115884

:

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <unordered_map>

using namespace std;
const int M = 10000;
const double MAX_LOAD_FACTOR = 0.75;

long long generateRandLong() {
int numDigits = rand() % 19 + 10; // Random number of digits between 10 and 19
unsigned long long num = rand() % 9 + 1; // Random non-zero first digit
for (int i = 1; i < numDigits; i++) {
unsigned long long digit = rand() % 10;
num = num * 10 + digit;
}
return num % (unsigned long long)(pow(10, 18));
}


string generateRandColor() {
string colors[] = { "black", "white", "gold", "rose gold", "silver" };
return colors[rand() % 5];
}

struct Data {
long long key;
long long number;
string color;
bool is_charger;

Data() {
key = generateRandLong();
number = rand() % 10000 + 1;
color = generateRandColor();
is_charger = rand() % 2;
}
};

struct HashNode {
long long key;
Data data;
HashNode* next;
HashNode* prev; //doubly

// constructor
HashNode(Data data) {
this->key = data.key;
this->data = data;
next = nullptr;
prev = nullptr;
}

HashNode(long long k, Data v) : key(k), data(v), next(nullptr) {}
};

struct LinkedList {
HashNode* head = nullptr;
HashNode* tail = nullptr;
int size = 0;

~LinkedList() {
clear();
}

void push_front(HashNode* newHashNode) { 
//head->prev = newNode; //doubly
head = newHashNode; 
if (tail == nullptr) { 
tail = newHashNode; 
}
size++;
}

HashNode* getHead() {
return head;
}

void clear() {
HashNode* current = head;
while (current != nullptr) {
HashNode* next = current->next;
delete current;
current = next;
}
head = nullptr;
tail = nullptr;
size = 0;
}

bool remove(long long key) {
if (head == nullptr) {
return false;
}
if (head->data.key == key) {
HashNode* temp = head;
head = head->next;
delete temp;
size--;
return true;
}
HashNode* current = head;
while (current->next != nullptr && current->next->data.key != key) {
current = current->next;
}
if (current->next == nullptr) {
return false;
}
HashNode* temp = current->next;
current->next = temp->next;
if (temp == tail) {
tail = current;
}
delete temp;
size--;
return true;
}

bool search(long long key) {
HashNode* current = head;
while (current != nullptr) {
if (current->data.key == key) {
return true;
}
current = current->next;
}
return false;
}
};


struct HashTable {

LinkedList* bucketsArray;
int bucketCount;
bool isEmpty = true;
int uniqueKeyCount = 0;
float MAX_LOAD_FACTOR;

// Hash function for long long keys
int hash(long long key) {
return key % bucketCount;
}

HashTable(int initialBucketCount, float MAX_LOAD_FACTOR) {
bucketCount = initialBucketCount;
this->MAX_LOAD_FACTOR = MAX_LOAD_FACTOR;
bucketsArray = new LinkedList[bucketCount];
}

~HashTable() {
delete[] bucketsArray;
}

void rehash() {
int oldBucketCount = bucketCount;
bucketCount *= 2;
LinkedList* newBucketsArray = new LinkedList[bucketCount];
uniqueKeyCount = 0;
for (int i = 0; i < oldBucketCount; i++) {
HashNode* current = bucketsArray[i].getHead();
while (current != nullptr) {
HashNode* newNode = new HashNode(current->data);
int bucketIndex = hash(current->data.key);
newBucketsArray[bucketIndex].push_front(newNode);
uniqueKeyCount++;
current = current->next;
}
}
delete[] bucketsArray;
bucketsArray = newBucketsArray;
}


void insert(long long key, Data value) {
int bucketIndex = hash(key);
HashNode* current = bucketsArray[bucketIndex].getHead();
while (current != nullptr) {
if (current->data.key == key) {
current->data = value;
return;
}
current = current->next;
}
HashNode* newHashNode = new HashNode(key, value);
bucketsArray[bucketIndex].push_front(newHashNode);
uniqueKeyCount++;

double loadFactor = (double)uniqueKeyCount / bucketCount;
if (loadFactor > MAX_LOAD_FACTOR) {
rehash();
}
}


bool erase(long long key) {
int bucketIndex = hash(key);
bool found = bucketsArray[bucketIndex].remove(key);
if (found) {
uniqueKeyCount--;
float loadFactor = (float)uniqueKeyCount / bucketCount;
if (loadFactor < MAX_LOAD_FACTOR / 2) {
rehash();
}
}
return found;
}

bool find(long long key) {
int bucketIndex = hash(key);
return bucketsArray[bucketIndex].search(key);
}

int size() {
int count = 0;
for (int i = 0; i < bucketCount; i++) {
LinkedList& bucket = bucketsArray[i];
HashNode* current = bucket.getHead();
while (current != nullptr) {
count++;
current = current->next;
}
}
return count;
}

};

我认为原点问题是在insert()中，因为它是第一个崩溃的。此外，这里是测试代码，但它应该是正确的，因为它是专门给我测试的。

bool testHashTable()
{
const int iters = 500000;
const int keysAmount = iters * 1;

// generate random keys:
long long* keys = new long long[keysAmount];

long long* keysToInsert = new long long[iters];
long long* keysToErase = new long long[iters];
long long* keysToFind = new long long[iters];

for (int i = 0; i < keysAmount; i++)
{
keys[i] = generateRandLong();
}
for (int i = 0; i < iters; i++)
{
keysToInsert[i] = keys[generateRandLong() % keysAmount];
keysToErase[i] = keys[generateRandLong() % keysAmount];
keysToFind[i] = keys[generateRandLong() % keysAmount];
}

// test my HashTable:
HashTable hashTable(500000, 0.75);

clock_t myStart = clock();
for (int i = 0; i < iters; i++)
{
hashTable.insert(keysToInsert[i], Data());
}
int myInsertSize = hashTable.size();
for (int i = 0; i < iters; i++)
{
hashTable.erase(keysToErase[i]);
}
int myEraseSize = hashTable.size();
int myFoundAmount = 0;
for (int i = 0; i < iters; i++)
{
if (hashTable.find(keysToFind[i]))
{   
myFoundAmount++;
}
}
clock_t myEnd = clock();
float myTime = (float(myEnd - myStart)) / CLOCKS_PER_SEC;

// test STL hash table:
unordered_map<long long, Data> unorderedMap;

clock_t stlStart = clock();
for (int i = 0; i < iters; i++)
{
unorderedMap.insert({keysToInsert[i], Data()});
}
int stlInsertSize = unorderedMap.size();
for (int i = 0; i < iters; i++)
{
unorderedMap.erase(keysToErase[i]);
}
int stlEraseSize = unorderedMap.size();
int stlFoundAmount = 0;
for (int i = 0; i < iters; i++)
{
if (unorderedMap.find(keysToFind[i]) != unorderedMap.end())
{
stlFoundAmount++;
}
}
clock_t stlEnd = clock();
float stlTime = (float(stlEnd - stlStart)) / CLOCKS_PER_SEC;

cout << "My HashTable:" << endl;
cout << "Time: " << myTime << ", after insert: " << myInsertSize << ", after erase: " << myEraseSize << ", found: " << myFoundAmount << endl;
cout << "STL unordered_map:" << endl;
cout << "Time: " << stlTime << ", after insert: " << stlInsertSize << ", after erase: " << stlEraseSize << ", found: " << stlFoundAmount << endl << endl;

delete[] keys;
delete[] keysToInsert;
delete[] keysToErase;
delete[] keysToFind;

if (myInsertSize == stlInsertSize && myEraseSize == stlEraseSize && myFoundAmount == stlFoundAmount)
{
cout << "The lab is completed" << endl;
return true;
}

cerr << ":(" << endl;
return false;
}

int main() {
srand(time(NULL));
testHashTable();
return 0;
}

Answer 1

您要做的是:编写一个函数来检查哈希表中的数据结构是否一致，并打印哈希表的完整内容。在每次修改哈希表的操作之后调用它。然后你再做测试

要么你找到打乱你的表的操作，要么你从正确的表->操作→崩溃。在这种情况下，使用调试器并在崩溃函数上设置断点。