Ищете C ++ неизменяемый hashset / hashmap - PullRequest
Новая
       81

Ищете C ++ неизменяемый hashset / hashmap

0 голосов
/ 23 февраля 2020

Я работаю над кодом C ++ под GPL с интенсивной обработкой данных. Одна из частых схем, которую мы часто используем, - это собрать некоторое количество (от тысяч до миллионов) ключей или пар ключ / значение (обычно int32..int128), вставить их в hashset / hashmap и затем использовать его без дальнейших изменений.

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

Сегодня мы используем STL unordered_map / set, но мы ищем лучшая (особенно быстрая) библиотека. Можете ли вы порекомендовать что-нибудь подходящее для этой ситуации с лицензией, совместимой с GPL?

Я думаю, что наиболее эффективным подходом будет сортировка всех ключей по номеру корзины по номеру корзины и обеспечение соответствия диапазона корзины>, поэтому мы можно использовать следующий код для поиска ключа: 

bool contains (set,key) {
  h = hash(key);
  b = h % BUCKETS;
  for (i : range(set.bucket[b], set.bucket[b+1]-1)
    if (set.keys[i]==key)  return true;
  return false;
}

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

1 Ответ

0 голосов
/ 11 марта 2020

Я думаю, для вашего случая больше подойдет Двойное хеширование или Робин Гуд Хеширование . Среди множества возможных алгоритмов я предпочитаю использовать двойное хеширование с таблицей 2 ^ n и нечетным шагом. Этот алгоритм очень эффективен и легко кодируется. Ниже приведен пример такого контейнера для ключей uint32_t: 

class uint32_DH {
  static const int _TABSZ = 1 << 20; // 1M cells, 2^N size
  public:
  uint32_DH() { bzero(_data, sizeof(_data)); }
  bool search(uint32_t key) { return *lookup(key) == key; }
  void insert(uint32_t key) { *lookup(key) = key; }
  private:
  uint32_t* lookup(uint32_t key) {
    uint32_t pos  = key + (key >> 32) * 7919;
    uint32_t step = (key * 7717 ^ (pos >> 16)) | 1;
    uint32_t *rc;
    do {
      rc = _data + ((pos += step) & (_TABSZ - 1)); 
    } while(*rc != 0 && *rc != key);
    return rc;
  }
  uint32_t _data[_TABSZ]; 
}
...