Каков самый быстрый способ перефразировать?

из структур данных Марка Вайса и анализа алгоритма в C++:Каков самый быстрый способ перефразировать?

/** 
* Rehashing for quadratic probing hash table. 
*/ 
void rehash() 
{ 
    vector<HashEntry> oldArray = array; 

    // Create new double-sized, empty table 
    array.resize(nextPrime(2 * oldArray.size())); 
    for(auto & entry : array) 
     entry.info = EMPTY; 

    // Copy table over 
    currentSize = 0; 
    for(auto & entry : oldArray) 
     if(entry.info == ACTIVE) 
      insert(std::move(entry.element)); 
}

Похоже, действительно болезненная операция, чтобы пройти через каждый элемент в таблице, и проверять, если элемент активен или не. В частности, существует ли реализация, которая подразумевает только количество вставленных элементов (в отличие от всей таблицы)?

источник

2016-04-08 blueman

Связанная структура хэша (где записи также связаны как дважды связанный список) позволит вам непосредственно перемещаться по элементам, а не всей таблице (и позволяет вам итерировать таблицу в порядке вставки вместо произвольного порядка). Будет ли это работать? – ShadowRanger

Будет ли это работать в закрытом хэшировании (моя цель)? Для справки: Open Hashing (отдельное цепочка): при открытом хэшировании ключи хранятся в связанных списках, прикрепленных к ячейкам хеш-таблицы. Закрытое Хеширование (Открытое Адресация): при закрытом хэшировании все ключи хранятся в самой хэш-таблице без использования связанных списков. – blueman

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

См. Per-Ake Larson, Dynamic Hashing, CACM April 1988, pp. 446-457. Он описывает систему хэширования, в которой ведра могут быть разделены, и только хэш-коды для ведра splt нуждаются в пересчете.

Вы найдете 'C' version of it coded as an hsearch(3) replacement, в архивах Usenet comp.sources.misc за июль 1998 года, внесенный [email protected] (me). Этот код впоследствии нашел свой путь в DB Berkeley и в других местах, включая OpenLDAP. Извините, у меня нет исходного исходного кода, но у меня есть реализация Java.

источник

2016-04-08 02:34:03 EJP

Разве вы не используете открытое хеширование (например, 'p = & q-> Next;')? Вопрос о закрытом хешировании (* «Повторная обработка для квадратичной таблицы хеширования зондирования» *), поэтому методы совершенно разные. –

Каков самый быстрый способ перефразировать?

ответ

Смежные вопросы