C语言 我如何修复这个大小调整功能

Question

我正在学习数据结构我需要创建一个哈希表(链/桶)的大小调整函数。我的代码可以编译，但表的大小从未改变。有人能看一下，给我一些提示，我在调整大小功能中缺少什么?谢谢你！

    struct hlink {
    TYPE value;
    struct hlink *next;
};
struct hashTable {
    struct hlink **table;
    int tableSize;
    int count;
};

void initHashTable (struct hashTable *ht, int size ) {
    assert (size > 0);
    //allocate memory for table 
    ht->table = (struct hlink **) malloc(size * sizeof(struct hlink *));
    assert(ht->table != 0);
    //initialize empty link list
    int i;
    for (i = 0; i < size; i++)
    {
        ht->table[i] = 0;
    }
    //set tableSize to be size
    ht->tableSize = size;
    ht->count = 0;
}

    void _resizeHashTable(struct hashTable *ht)
{
    //create and initialize new tablesize
    int new_tblSize = 2 * ht->tableSize;
    //old list
    struct hlink **oldList = ht->table;
    //new list
    struct hlink **newList = (struct hlink **) malloc(new_tblSize * sizeof(struct hlink*));
    //Copy old values to new table
    for (int i=0; i < new_tblSize; i++)
    {
        //compute hash value to find the new bucket
        int hashIndex = HASH(oldList[i]->value) % new_tblSize;
        if (hashIndex < 0)
            hashIndex += new_tblSize;
        newList[i]->value = oldList[i]->value;
        newList[i]->next = newList[hashIndex];
    }
    //Assign table and tablesize back to the old table
    free(ht->table);
    ht->table = newList;
    ht->tableSize = new_tblSize;
}

void hashTableAdd (struct hashTable *ht, TYPE newValue)
{
    // compute hash value to find the correct bucket
    int hashIndex = HASH(newValue) % ht->tableSize;
    if (hashIndex < 0)
        hashIndex += ht->tableSize;
    struct hlink * newLink = (struct hlink *) malloc(sizeof(struct hlink));
    assert(newLink != 0);
    newLink->value = newValue;
    newLink->next = ht->table[hashIndex];
    ht->table[hashIndex] = newLink;     //add to bucket 
    ht->count++;

    if ((ht->count / (double) ht->tableSize) > 8.0)
        _resizeHashTable(ht);
}

Answer 1

不能释放旧表。你正在释放刚刚分配的那个。而不是

ht->table = new_tbl;
...
free(new_tbl);

应该

free(ht->table);
ht->table = new_tbl;

你的

也有问题

//Copy old values to new table
for (int i=0; i < ht->tableSize; i++)
{
    new_tbl[i] = ht->table[i];
}

像上面那样复制表桶条目是不够的，但是桶链接列表中的每个条目都需要重新哈希，因为您有一个新的表大小，因此可能有一个新的哈希索引。

int hashIndex = HASH(newValue) % ht->tableSize;

我暂时建议您在调整大小时，先检查每个旧的存储桶，然后检查每个链接列表条目，并将其移动到新表中。请记住，对于每个表项，由于"% ht->tableSize"不同，旧表中的桶索引可能与新表中的桶条目不同。

在resize()期间，注意管理旧表的链表分配。它们可以在您的新表中重用，但是这里的正确编码可能具有挑战性。

下面是一些增强的想法…

p。S.也推荐

if (ht->count > (ht->tableSize * 8))

不是

if ((ht->count / (double) ht->tableSize) > 8.0)

p。也建议不要把桌子的大小增加一倍，而是增加四倍。此外，将表大小设置为素数也是一个不错的选择。使用素数执行"%ht->tableSize"有助于提高弱散列函数的分散性。

当您添加hashTableDelete()时，

翻倍有一个很好的触点。对于delete函数，您可以再次调用resize函数，但这一次，表正在缩小。重要的是你的增长阈值(例如tablesize*8)和收缩阈值是不同的。如果存在相同的情况，那么当表达到临界大小时，如果您碰巧添加和删除表，则可能会遇到"散列的抖动"。我喜欢把我的生长阈值设定在3、11、61、251……(质数小于4**N)和我的收缩阈值为1,7,31,119，…(2*4**N下的素数)，因此随着表的增长和缩小，将重新哈希保持到最小。