Хеш-таблица

Cтраница 1

Хеш-таблицы обычно содержат только одну запись с данным ключом. В этом случае процедуре Inse tltetfinepefl добавлением элемента необходимо проверить, нет ли такого элемента в таблице. [1]

Хеш-таблицы, содержащие большое количество элементов, наиболее интересны, поэтому программа Chain позволяет заполнять таблицу случайными элементами. [2]

Преимущества и недостатки различных методов хеширования. [3]

Хеш-таблицы на основе связывания или блоков легко увеличить или удалять из них элементы. Использование блоков также упрощает работу с таблицами, сохраненными на диске. За одно обращение к диску считывается сразу множество элементов данных. Однако оба этих метода выполняются медленнее, чем методы открытой адресации. [4]

Пока хеш-таблица не слишком полна ( скажем, заполнена на 50 % объема), коллизии появляются редко, и производительность схемы хеширования определяется прежде всего временем, требующимся для вычисления хеш-функции. Когда память становится более заполненной, доступ к именам требует все больше и больше времени из-за коллизий. Поэтому когда память используется в большой степени, схема разрешения коллизий определяет эффективность схемы хеширования. Отсюда выбор схемы разрешения коллизий обычно важнее выбора хеш-функции. [5]

Если хеш-таблица почти заполнена, производительность резко снижается. [6]

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

Для хеш-таблиц с внешними цепочками переполнения удаление является процедурой, обратной вставке, и выполняется аналогично операции удаления из обычного линейного списка. Для хеш-таблиц с линейным опробованием или с внутренними цепочками переполнения связь между занятыми позициями однозначна, поэтому возможны реальные удаления. Для этого достаточно переместить содержимое всех позиций, приндалежащих списку и следующих за удаленной. Для выявления синонимов может потребоваться повторно вычислить хеш-функцию ключей, принадлежащих списку. Если потребовать, чтобы каждый список синонимов обязательно начинался со своего хеш-адреса h0 ( k), то это позволит сократить затраты на удаление. Затраты на вставку в этом методе будут несколько выше, так как может потребоваться переместить ключ, занимавший чужую позицию. Этот метод можно рекомендовать и в том случае, когда вставки ключей в таблицу редки по сравнению с поиском. [8]

Построение таблицы с помощыо метода открытого хеширования. ( Для краткости опущена информация, связанная с ключами. Вновь вставляемые эле -. менты отмечены звездочкой. [9]

Поэтому строится хеш-таблица, имеющая 3 / 2x7 10 входов. Позицию ключа в таблице дает функция отображения kK & M ( K), где К. [10]

Принсднге содержимое хеш-таблицы, обр а за ванной к результате злсменток с ключами KASYQUTIONn указакном порядке п но пустую тэ ( 5лис1у размерим Л / - 16 при использовании линейного Используйте хеш-функцию Ilk ( Hod M JJSM иреобразованыл А-ой. [11]

Приведите содержимое хеш-таблицы, образованной в результате вставки элементов с ключами EASYQUTIONs указанном порядке в первоначально пустую таблицу, имевшую начальный размер М 4, которая увеличивается вдвое при ее заполнении наполовину, при разрешении конфликтов методом линейного зондирования. Воспользуйтесь хеш-функцией НА; mod M для преобразования А: - той буквы алфавита в индекс таблицы. [12]

Различные типы хеш-таблиц, описанные в этой главе, имеют свои преимуществен недостатки. [13]

Чтобы создать хеш-таблицу в Delphi, нужно объявить массив ячеек, начинающийся с нуля. [14]

Поиск в хеш-таблице с внешними цепочками переполнения выполняется очень просто. [15]

Страницы: 1 2 3 4