Реализация хеш-таблицы

@constantin01 · Регистрация: 20.09.2019

Author24 — интернет-сервис помощи студентам

Здравствуйте!

В некоторых реализациях хеш-таблицы функция удаления значения выглядит так, что на место значения, которое необходимо удалить вставляют фиктивный узел dummy со значением ключа -1.

Например

C++

//if node found 
            if(arr[hashIndex]->key == key) 
            { 
                HashNode<K,V> *temp = arr[hashIndex]; 
                  
                //Insert dummy node here for further use 
                arr[hashIndex] = dummy; 
                  
                // Reduce size 
                size--; 
                return temp->value; 
            }

В чем польза такого подхода? Почему нельзя просто удалять элемент и освобождать память?

@oleg-m1973 · 18.10.2019, 20:22

Сообщение от constantin01

В чем польза такого подхода? Почему нельзя просто удалять элемент и освобождать память?

Чтобы не перестраивать хэш-таблицу, не пересчитывать хэши. Просто помечаем ячейку, как пустую.

@oleg-m1973 6579 / 4564 / 1843 Регистрация: 07.05.2019 Сообщений: 13,726
	18.10.2019, 20:22	2
	Сообщение от constantin01 В чем польза такого подхода? Почему нельзя просто удалять элемент и освобождать память? Чтобы не перестраивать хэш-таблицу, не пересчитывать хэши. Просто помечаем ячейку, как пустую. 1