Как я могу исправить эту функцию изменения размера?

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».

Во время изменения размера(), позаботьтесь о том, чтобы управлять распределениями списка ссылок старой таблицы. Они могут быть повторно использованы в вашей новой таблице, но правильное кодирование здесь может быть сложным.

Ниже приведены лишь некоторые идеи повышения ...

P. S. Также рекомендуем

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

вместо

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

P. S. Также рекомендуем не удвоить размер таблицы, но в четыре раза его. Кроме того, приятно иметь размер таблицы, который является простым. Выполнение «% ht-> tableSize» с простым числом помогает улучшить разброс слабых хеш-функций.

Четырёхкратный прикосновение при добавлении hashTableDelete(). С помощью функции удаления вы снова можете вызвать функцию изменения размера, но на этот раз таблица сокращается. Важно, чтобы ваш порог роста (например, tableize * 8) и ваш порог усадки были разными. Если примерно то же самое, вы можете получить «хэширование хэширования», если вам случится добавлять и удалять, когда таблица имеет этот критический размер. Мне нравится иметь свой порог роста на уровнях, таких как 3, 11, 61, 251, ... (пробег ниже 4 ** N) и мои пороги сокращения у 1, 7, 31, 119, ... (пробег ниже 2 * 4 ** N), таким образом, сохраняйте повторное хеширование до минимума, так как таблица растет и сжимается.