Хеш-таблицы - Java

Question

Я собираюсь сделать домашнее задание, и мне нужно хранить довольно много информации (словарь) в структуре данных на мой выбор. Я слышал, как люди в моем классе говорили, что хэш-таблицы - это путь. Как получилось?

Answer 1

Чтобы помочь вам решить, какой тип коллекции лучше для вас, взгляните на этот урок по Java Tutorials:

Урок: Введение в коллекции

Прочитав это, вы увидите, какая коллекция соответствует вашим потребностям.

Answer 2

Лучшей структурой для вашего словаря будет Дерево префиксов , в котором «ключ» каждого узла - это буква одного из ваших слов, а «значение» каждого узла - значение слова (перевод словаря) ). Поиск слова является линейным по длине слова (так же, как хеш-таблица, поскольку ваша хеш-функция в идеале должна быть линейной), или O (1), если мы рассматриваем слова как целое. Преимущество хеш-таблиц состоит в том, что хеш-таблица будет занимать много места для обеспечения доступа O (1) и, в зависимости от слов в словаре, может быть очень малонаселенной. С другой стороны, дерево префиксов фактически обеспечивает сжатие - само дерево будет содержать всю исходную информацию в меньшем пространстве, чем раньше, поскольку общие части слов совместно используются в древовидной структуре. Словари обычно содержат десятки тысяч слов, и единственное жизнеспособное решение - дерево префиксов.

P.S. Как упоминалось ранее, дерево имеет почти бесконечную масштабируемость, в отличие от хеш-таблицы.

Answer 3

Преимущества

Когда вы впервые слышите о хеш-таблицах, они звучат слишком хорошо, чтобы быть правдой. Причина заключается в том, что не имеет значения, сколько элементов выполняется поиск, вставка (иногда удаление) может занять приблизительно 0 (1), что в значительной степени происходит мгновенно из пользовательского POV. Учитывая его производительность с точки зрения скорости, хеш-таблицы используются в основном, но не ограничиваются программами, которые должны искать тысячи элементов менее чем за секунду (например, средства проверки орфографии / поисковые системы). С моей особой точки зрения, я считаю, что таблицы H гораздо проще программировать, чем любые виды двоичных деревьев, и я не эксперт, поэтому, если вы новичок, это может быть и преимуществом.

Недостатки

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

---

Дополнительная информация

Статьи из Википедии - Хеш-таблица - Big O Обозначения

Учебник по хеш-таблицам - Учебник

Все о хэш-таблицах - Java2S

---

Книжная консультация

Я советую вам купить книгу под названием «Структуры данных и алгоритмы в Java - второе издание - Роберт Лафоре», это большая книга, но в ней все объясняется очень тонко, для меня пока единственная книга по программированию я могу читать как роман.

---

Дополнительная информация относительно обозначения Big O - O (1)

O (1) не означает "почти мгновенный" (алгоритм O (1) может занять часы, недели или годы). Это означает (в данном случае) «не зависит от размера коллекции» (при условии, что хэш-код достаточно хорош). - Бен Лингс

Спасибо Бену за разъяснения.

---

P.S .: Вы можете захотеть быть более информативным в будущем, когда задаете вопрос таким образом, чтобы другие пользователи могли точно определить, что вы ищете.

Answer 4

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

Answer 5

Это зависит от того, что вы хотите сохранить и как вы хотите получить к нему доступ.Вы на самом деле не предоставляете достаточно информации.

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

Answer 6

Хеш-таблицы являются хорошим вариантом, но при их использовании вам, возможно, придется решить, что может быть хорошей хеш-функцией. Этот вопрос может иметь много ответов и зависит от программиста. Я лично чувствую, что вы можете проверить B + дерево или Trie. Одним из основных применений Trie является словарное представление. Trie в вики

Надеюсь, это поможет !!

Answer 7

Хеш-таблица позволяет вам сопоставлять ключи с объектами.

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