На какие аспекты следует обращать внимание при разработке hash_table? - PullRequest
Новая
       2

На какие аспекты следует обращать внимание при разработке hash_table?

4 голосов
/ 09 мая 2011

У меня есть несколько возможных аспектов:

  1. Хеш-функция важна, хэш-код должен быть насколько возможно уникальным.
  2. Важна структура внутренних данных, все операции поиска, вставки и удаления должны иметь временную сложность O (1).
  3. Важное значение имеет управление памятью, поэтому использование каждой записи в хэш-таблице должно быть как можно меньше.Когда hash_table расширяется, память должна эффективно увеличиваться, а когда hash_table сокращается, память должна эффективно выполнять сборку мусора.И с этими операциями с памятью аспект 2 также должен быть полностью заполнен.
  4. Если hash_table будет использоваться в multi_threads, он должен быть потокобезопасным, а также эффективным.

Мои вопросы:

  1. Есть ли еще какие-либо аспекты, заслуживающие внимания?
  2. Как спроектировать hash_table для полного заполнения этих аспектов?
  3. Есть ли какие-либо ресурсы, на которые я могу сослаться?

Большое спасибо!

Прочитав некоторые материалы, обновите мои вопросы.:)

В книге, объясняющей исходный код SGI STL, я нашел несколько полезных сведений:
  1. Структура внутренних данных - корзина из связанный список .При поиске вставьте или удалите элемент в hash_table:
    1. Используйте хеш-функцию для вычисления соответствующей позиции в bucket и элементы сохраняются в связанном списке после этой позиции .
    2. Когда размер элементов больше, чем размер ведер , ведер необходимо изменить размер : увеличить размер доВ 2 раза больше старого размера.Размер ведер должен быть простых .Затем скопируйте старые корзины и элементы в новое.
    3. Я не нашел логики сборки мусора , когда количество элементов намного меньше, чем сегментов .Но я думаю, что эта логика должна учитываться, когда многие вставляют сначала, а затем многие удаляют позже.
  2. Другие структуры данных, такие как массивы с линейным обнаружением или квадратным обнаружением не так хороши, как связанный список .
  3. Хорошая хеш-функция позволяет избежать кластеров , а двойной хэш может помочь разрешить кластеров .

Вопрос о multi_threads все еще открыт.: D

Ответы [ 2 ]

3 голосов
/ 09 мая 2011

Есть две (слегка) ортогональные проблемы.

Хотя хэш-функция, очевидно, важна, в целом вы отделяете дизайн бэкенда от дизайна хеш-функции:

  • хеш-функция зависит от данных, которые должны быть сохранены
  • бэкэнд зависит от требований к хранилищу

Для хеш-функций я бы посоветовал прочитать о CityHash или MurmurHash (с объяснением для SO ).

Для серверной части, как вы заметили, существуют различные проблемы.Несколько замечаний:

  • Мы говорим о средней или наихудшей сложности?Насколько мне известно, без идеального хеширования достижение O (1) практически невозможно, хотя частоту и сложность наихудшего случая можно значительно снизить.
  • Мы говорим об амортизированной сложности?Амортизируемая сложность в целом обеспечивает лучшую пропускную способность за счет «шипов».Линейное перефразирование, за счет немного меньшей пропускной способности, даст вам более плавную кривую.
  • Что касается многопоточности, обратите внимание, что шаблон чтения / записи может повлиять на решение, учитывая крайние случаи, 1 производительи 99 читателей сильно отличаются от 99 производителей и 1 читателя.В целом записи труднее распараллелить, потому что они могут потребовать изменения структуры.В худшем случае они могут потребовать сериализации.
  • Сборка мусора довольно тривиальна в амортизированном случае, с линейной перефразировкой это немного сложнее, но, вероятно, наименее сложная часть.

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

Ссылки:

  • The *В статье 1036 * в Википедии представлено множество различных реализаций, всегда приятно взглянуть на разнообразие
  • В этом GoogleTalk от доктора Клиффа (Azul Systems) показана хеш-таблица, предназначенная для сильномногопоточные системы на Java.
3 голосов
/ 09 мая 2011

Я предлагаю вам прочитать http://www.azulsystems.com/blog/cliff/2007-03-26-non-blocking-hashtable

Ссылка указывает на блог от Cliff Click, в котором есть запись о хэш-функциях.Вот некоторые из его выводов:

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