Линейная алгебра и мат. Статистика
жүктеу/скачать 294.26 Kb.
|
| Хеш-таблица — это СД, в которой хранятся значения и связанные с ними ключи. Представьте большую библиотеку. Обычно для поиска книги там нужен справочник. Но можно использовать алгоритм хеширования, тогда функция сразу выдаст номер шкафа и расположение книги в нем. Это происходит благодаря ключам. Они содержат информацию для доступа к файлу и о его расположении. Хеширование используют в криптографии для шифрования информации.
Хеш-функция сокращает длинную строку символов до короткого значения. Это и будет ключом или индексом элемента данных в хеш-таблице. Набор данных в ней называется словарем. Словарь (он же ассоциативный массив) — это тот же вектор, но с небольшими отличиями. В качестве индекса (который в словаре будет называться ключ) могут выступать не только числа, но и любые другие типы данных (даже другие коллекции!). Также допустимы пропуски, если мы все-таки будем использовать в качестве ключа целое число, например у нас может быть элемент связанный с ключом 5, но при этом отсутствовать элемент связанный с ключом 4. Основные операции (сложность ): Insert Remove Find Реализация: Можно просто завести массив (или список) пар (Ключ, Значение) и добавить специальную функцию, которая будет пробегать по этому списку и возвращать определенное значение по связанному с ним ключу. Производительность хеш-таблицы зависит от функции хеширования, размера таблицы и метода обработки коллизий. Область применения ассоциативных массивов весьма обширна. Например, с их помощью возможно реализовать разряженный вектор, который имеет достаточно большую длину, при этом заполнен в основном нулями. Таким образом, можно сэкономить значительный объем памяти. Другое весьма распространенное применение ассоциативных массивов связано с использованием строк в качестве ключей. В частности, вы можете организовать простой словарь в памяти, в котором каждому термину будет поставлен в соответствие его перевод на другом языке. Структура данных: куча (виды, построение, алгоритмы, применение). Куча — это полное двоичное дерево, удовлетворяющее свойству кучи: если узел A — это родитель узла B, то ключ узла A ≥ ключ узла B. Кучи — почти то же самое, что и деревья: у них также есть корневые и дочерние узлы. Отличается система иерархии: кучи бывают двух видов — те, где значения корневых узлов меньше и те, где значения больше, чем у дочерних. Эти СД можно хранить в простом или динамическом массиве, то есть они занимают гораздо меньше места, чем деревья. Чтобы добавить новый элемент в кучу, нужно пересмотреть все остальные. Элементы расположены по убыванию — от больших к маленьким. Виды СД куча: Если любой узел всегда больше дочернего узла (узлов), а ключ корневого узла является наибольшим среди всех остальных узлов, это max-куча. Если любой узел всегда меньше дочернего узла (узлов), а ключ корневого узла является наименьшим среди всех остальных узлов, это min-куча. жүктеу/скачать 294.26 Kb. Достарыңызбен бөлісу:
|