c++ - 调整大小的 C++ HashTable 二次探测插入方法不起作用?
问题描述
一旦阈值超过预定量 0.65,此方法应该调整数组的大小。问题是在调整大小后,析构函数会删除包含所有新复制信息的数组。我不知道如何解决它。
关于那里的一些评论只是我集思广益可能是什么问题。
void Hashtable::insert(int value)
{
int i = 0;
int key = hash(value); // hash(value) % N?
//check load factor to see if it needs to be resized
double q = ((double)(currsize+1) / (double)currcapacity); //calculate current threshold
if ( q >= threshhold) { //if current threshold is >= to 0.65
int newSize = nextPrime(currcapacity * 2); //get new size at the next prime number
Hashtable newtable(newSize); //create a new table; HOW DO I CREATE THIS ON THE HEAP?
for (int j = 0; j < currcapacity; j++) { //runs through table calling insert to insert new items into table
if (htable[j] != EmptyBeforeStart && htable[j] != EmptyAfterRemoval) {
newtable.insert(htable[j]);
}
}
delete[] htable; //delete old table
this->htable = newtable.htable; //re-assign address of htbale to be newtable.htable //THIS ASSINGMENTS GETS DELETED BY THE DESTRUCTOR
this->currcapacity = newSize; //update capacity
this->insert(value);
//THE PROBLEM IS THAT THE DESTRUCTOR GETS CALLED AND DELETES THE htable BECAUSE THE NEWTABLE HTABLE WAS DECLARED AUTOMAITCALLY NOT ON THE HEAP.
}
else {
while (i < currcapacity) {
if (htable[key] == EmptyBeforeStart || htable[key] == EmptyAfterRemoval) {
htable[key] = value;
currsize++;
return;
}
i++;
key = (hash(value) + 0 * i + 1 * i * i) % (int)currcapacity;
}
}
}
解决方案
您的析构函数被调用是因为您Hashtable
使用以下行在堆栈上创建了一个对象:
Hashtable newtable(newSize);
这创建了一个临时表,您填充了该表,然后在函数返回之前将其丢弃(销毁)。但在那之前,你偷走了它的指针并将它存储在当前的哈希表中。这是个大问题,因为当那个表被销毁时,它会尝试删除一个已经被删除的指针。
我想你的意思是:
int *newtable = new int[newSize];
std::fill(newtable, newtable + newSize, EmptyBeforeStart);
但是,您将需要更改将现有值复制到其中的重新散列部分。现在,我并不是说以下是一个很棒的设计,但无需重新设计任何其他内容,您就可以这样做:
// Store information about current table before replacing it
int *oldtable = htable;
int oldcapacity = currcapacity;
// Replace the hash table with new empty one
htable = newtable;
currcapacity = newSize;
// Rehash old values
for (int j = 0; j < oldcapacity ; j++) {
if (oldtable[j] != EmptyBeforeStart && oldtable[j] != EmptyAfterRemoval) {
insert(oldtable[j]);
}
}
// Clean up
delete[] oldtable;
看看上面实际上是如何用新的空表替换表的,但保留一个指向旧数据的指针。然后它调用insert
将所有旧值散列到新表中。然后当它完成时,可以释放旧内存。
推荐阅读
- ios - 在开头快速添加标签并在按下按钮后将其删除
- c++ - 为什么使用 C++ 容器“数组”而不是传统的 C 数组?
- java - 如何在java中故意创建随机浮点/小数精度错误?
- javascript - Datetime 似乎破坏了 Google Apps Script 客户端反序列化
- c# - 使视频缓冲更多,暂停下载整个视频
- reactjs - RSocket 错误 0x201 (APPLICATION_ERROR): readerIndex(1) + length(102) 超过 writerIndex(8): UnpooledSlicedByteBu
- python - Luigi 任务没有将 pandas df 写入 csv
- python - 我尝试制作评论通知
- php - Wordpress 5.7 没有为我上传的图片创建多个尺寸的版本
- python - 从文本文件中提取两行之间的数据