Когда использовать хеш-структуру данных?

У меня есть коллекция предметов (максимум 500).

Мои записи будут часто просматриваться на основе ключа типа MAC, диапазон которого неизвестен.

Теперь я не понимаю, какую структуру данных и алгоритм использовать для эффективного поиска значений.

Я не уверен, выбрать ли в этом случае сбалансированный BST (AVL) или хеш-таблицу.

Мало ли 500 ключей для построения хэш-таблиц?

Что было бы лучшим подходом в моем случае?

Я читал это computing hash might prove costly when the number of keys is less

Кстати, я также хотел бы знать, какое количество записей (мин) необходимо для рассмотрения хеш-таблицы?

Пожалуйста, добавьте комментарий, если требуются дополнительные сведения.

Заранее спасибо.


c performance algorithm hashtable avl-tree
person Nataraj    schedule 07.01.2015    source источник
comment
Если вы не будете строить свои структуры данных с нуля, чего я в любом случае не рекомендую, я предлагаю вам протестировать оба.   -  person Giulio Franco    schedule 07.01.2015
comment
Хеш-таблица дает вам время поиска O (1); BST дает вам время поиска O (log N). Вы должны взвесить стоимость вычисления хэша и стоимость множественных сравнений MAC. В целом, я подозреваю, что хеш-таблица будет работать хорошо.   -  person Jonathan Leffler    schedule 07.01.2015
comment
Как бы вы определили лучший? Хеш-таблицы обычно работают быстрее, но только если у вас есть хороший алгоритм для генерации хешей и подходящая обработка коллизий. Но тебе тоже нужно? Вы можете начать с _1 _ + _ 2_, и этого может быть достаточно.   -  person user694733    schedule 07.01.2015
comment
Обычный вопрос с множеством ответов по SO. Вот один.   -  person Andy Brown    schedule 07.01.2015
comment
Всем спасибо. @ user694733 Я думал пойти на qsort + bsearch, но в случае динамической вставки / удаления может потребоваться удар. нужно вставить и отсортировать. думал, что AVL дает больше преимуществ, поскольку вставка, удаление и поиск - это O (журнал N)   -  person Nataraj    schedule 07.01.2015
comment
@AndyBrown большое спасибо. Эта ссылка действительно помогла. Больше сравнений. :)   -  person Nataraj    schedule 07.01.2015

Ответы (1)


arrow_upward
2
arrow_downward

Ниже приведены некоторые из преимуществ хеш-структур.

  1. Быстрый поиск (теоретически O (1))
  2. Эффективное хранилище (помогает хранить ключ-значение)

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

  1. Если у вас есть большое количество объектов, потребуется больше места для хранения (памяти), что может привести к снижению производительности.
  2. Алгоритм хеширования / ключа не должен быть сложным. В противном случае на хеширование и поиск ключа уйдет больше времени.
  3. Конфликт ключей должен быть минимальным, чтобы избежать линейного поиска по всем значениям для одного ключа или дублирования ключа.

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

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

person Nachiket Kate    schedule 07.01.2015
comment
Большое спасибо. На данный момент мои данные статичны, но могут стать динамическими. Поэтому подумал, что было бы лучше рассмотреть этот случай, прежде чем придумывать DS / Algo. Судя по тому, что вы и другие предлагаете, похоже, что в моем случае подойдет Hash. - person Nataraj; 07.01.2015
comment
Количество вставок / удалений определенно будет <количество просмотров - person Nataraj; 07.01.2015