Развернуть хеш-таблицу без перефразирования?

Question

Я ищу для структуры данных hash table, которая не требует rehash для расширения и усадки? Rehash - это процессорное усилие. Мне было интересно, можно ли создать структуру данных хеш-таблицы таким образом, чтобы не требовать перефразирования? Вы слышали о такой структуре данных раньше?

Answer 1

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

Answer 2

Предполагая, что вам действительно нужно это .. Это возможно. Здесь я приведу тривиальный пример, на котором вы можете построить.

// Basic types we deal with 
typedef uint32_t key_t; 
typedef void * value_t; 
typedef struct 
{ 
    key_t key; 
    value_t value; 
} hash_table_entry_t; 

typedef struct 
{ 
    uint32_t initialSize; 
    uint32_t size; // current max entries 
    uint32_t count; // current filled entries 
    hash_table_entry_t *entries; 
} hash_table_t; 

// Hash function depends on the size of the table 
key_t hash(value_t value, uint32_t size) 
{ 
    // Simple hash function that just does modulo hash table size; 
    return *(key_t*)&value % size; 
} 

void init(hash_table_t *pTable, uint32_t initialSize) 
{ 
    pTable->initialSize = initialSize; 
    pTable->size = initialSize; 
    pTable->count = 0; 
    pTable->entries = malloc(pTable->size * sizeof(*pTable->entries)); 
    /// @todo handle null return; 
    // Set to ~0 to signal invalid keys. 
    memset(pTable->entries, ~0, pTable->size * sizeof(*pTable->entries)); 
} 

void insert(hash_table_t *pTable, value_t val) 
{ 
    key_t key = hash(val, pTable->size); 
    for (key_t i = key; i != (key-1); i=(i+1)%pTable->size) 
    { 
     if (pTable->entries[i].key == ~0) 
     { 
      pTable->entries[i].key = key; 
      pTable->entries[i].value = val; 
      pTable->count++; 
      break; 
     } 
    } 

    // Expand when 50% full 
    if (pTable->count > pTable->size/2) 
    { 
     pTable->size *= 2; 
     pTable->entries = realloc(pTable->entries, pTable->size * sizeof(*pTable->entries)); 
     /// @todo handle null return; 
     memset(pTable->entries + pTable->size/2, ~0, pTable->size * sizeof(*pTable->entries)); 
    } 
} 

_Bool contains(hash_table_t *pTable, value_t val) 
{ 
    // Try current size first 
    uint32_t sizeToTry = pTable->size; 
    do 
    { 
     key_t key = hash(val, sizeToTry); 
     for (key_t i = key; i != (key-1); i=(i+1)%pTable->size) 
     { 
      if (pTable->entries[i].key == ~0) 
       break; 
      if (pTable->entries[i].key == key && pTable->entries[i].value == val) 
       return true; 
     } 

     // Try all previous sizes we had. Only report failure if found for none. 
     sizeToTry /= 2; 
    } while (sizeToTry != pTable->initialSize); 
    return false; 
} 

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

Таким образом, get()/ и подобные операции занимают больше времени, чем больше раз, чем вы расширили свой стол, но у вас нет огромного всплеска перефразирования. Я могу представить некоторые системы, где это было бы требованием.

Answer 3

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

Это зависит от того, что вы называете «перепев»:

• Если вы просто означает, что перепев на уровне таблицы не должны повторно использовать хэш-функции для каждого ключа при изменении размера, то это легко с большинство библиотек: например оберните ключ и его исходное значение хэш-значения (pre-modulo-table-size) вместе a la struct X { size_t hash_; Key key_ };, поставьте библиотеку хэш-таблицы с хеш-функцией, которая возвращает hash_, но сравнивает функцию, которая сравнивает key_ s (в зависимости от сложности key_ сравните, вы можете использовать hash_ для оптимизации, например lhs.hash_ == rhs.hash_ && lhs.key_ == rhs.key_).

  • Это поможет большинству, если хэширование ключей было особенно трудоемким (например, криптографическая сила на длинных клавишах). Для очень простого хэширования (например, пересылка int с) это замедлит вас и потеряет память.

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

Как только один пример, вы могли бы использовать более типичный хеш реализации (назовем его Н), имея свой собственный хэш-таблицу (C) имеют H** p, что - до начального предела размера - будет иметь p[0] быть единственный экземпляр H, а также просто паромные операции/результаты.Если таблица выходит за рамки этого, вы сохраняете p[0], ссылаясь на существующий H, создавая вторую хэш-таблицу H, которая будет отслеживаться p[1]. Тогда вещи начинают получать ненадежные:

• для поиска или удалений в C, ваша реализации должна искать p[1] затем p[0] и сообщать о любой спичке либо из

• вставить новое значение в C, ваша реализация должна подтвердить, что это не в p[0], а затем вставить в p[1]

  • с каждым insert (и, возможно, даже для других операций), он может при необходимости перенести любые м atching - или произвольная запись p[0] - до p[1] так постепенно p[0] пустые; вы можете легко гарантировать, что p[0] будет пуст до того, как p[1] будет таким полным (и, следовательно, потребуется большая таблица). Когда p[0] пуст, вы можете захотеть p[0] = p[1]; p[1] = NULL;, чтобы сохранить простую ментальную модель того, что есть, - множество опций.

Некоторых существующих реализации хэш-таблиц является очень эффективным при переборе над элементами (например, GNU C++ std::unordered_set), поскольку есть односвязный список всех значений, и хэш-таблица действительно только коллекция указателей (на языке C++, итераторах) в связанном списке. Это может означать, что если ваше использование падает ниже некоторого порогового значения (например, коэффициент загрузки 10%) для вашей единственной/большой хеш-таблицы, вы знаете, что можете очень эффективно перенести оставшиеся элементы на меньшую таблицу.

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

Некоторые из вариантов реализации имеют смысл только для открытой или закрывающей хеширующей реализации или полезны только тогда, когда ключи и/или значения малы или большие, и в зависимости от того, вставляет ли таблица их или указывает на их. Лучший способ узнать об этом - это код ....