Double Hashing — функция удаления и перефразирования
Я работаю над хэш-картой и испытываю проблемы с функцией удаления открытой карты стиля адреса с двойным хешированием. Допустим, я вставляю в таблицу размером 10, и мои 2 хэш-функции следующие:
int hash( int key, std::size_t M ) { return key % M; }
int hash2( int key, std::size_t M ) { return key % (M-1) + 1; }
Если я вставлю элементы с ключами 0, 10 и 20, они перейдут в позиции 0, 2 и 3.
<[ 0:A, - , 10:B, 20:C, - , - , - , - , - , - ]>
Однако при удалении элемента я хочу удалить элемент И перефразировать следующие элементы в том же кластере. Когда я удаляю, скажем, элемент с ключом 0, он находит элемент для удаления без проблем. Но теперь нужно перейти к индексу 2 — НО ЭТО НЕ МОЖЕТ, ПОТОМУ ЧТО ЕГО ИСПОЛЬЗУЕТ КЛЮЧ 0 КАК ЕГО УВЕЛИЧЕНИЕ, поэтому вместо этого он переходит к индексу 1. Таким образом, он никогда не найдет последующие элементы в кластере. Как мне это сделать???
Решение
Как правило, вы удаляете элемент, помещая удаленный маркер в эту позицию. Для целей поиска он занят, поэтому предметы, которые столкнулись и которые необходимо найти, не являются осиротевшими. Но при вставке вы можете использовать это место повторно. Если количество удаленных маркеров в вашей таблице становится большим, вы можете перефразировать таблицу, чтобы очистить ее.
Эта лекция объясняет более подробно: Открытая адресация
Другие решения