Хеш-таблица

Cтраница 3

С другой стороны, если хеш-таблица не сильно переполнена, многие блоки будут иметь блоки переполнения, содержащие всего один или два элемента. Предположим, что в каждом блоке находится по 11 элементов. [31]

Способ организации структур данных ( хеш-таблиц), обеспечивающий эффективный поиск и пополнение; положение элемента данных в хеш-таблице определяется значением функции расстановки, отображающей множество возможных ключей элементов данных в множество индексов таблицы и обеспечивающей равномерное заполнение. [32]

Найдем среднее число проб в хеш-таблице с внешними цепочками переполнения, предполагая, что все М хеш-последовательностей равновероятны. [33]

С увеличением количества ключей в хеш-таблице производительность поиска уменьшается. При использовании раздельного связывания время поиска увеличивается постепенно - когда количество ключей в таблице удваивается, время поиска удваивается. Это же справедливо по отношению к таким методам с открытой адресацией, как линейное зондирование и двойное хеширование для разреженных таблиц, но по мере заполнения таблицы затраты возрастают коренным образом и, что гораздо хуже, наступает момент, когда никакие дополнительные ключи вообще не могут быть вставлены. Эта ситуация отличается от деревьев поиска, в которых рост происходит естественным образом. Например, в RB-дереве затраты на поиск возрастают лишь несущественно ( на одно сравнение) при каждом удвоении количества узлов в дереве. [34]

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

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

Часто довольно трудно распределить память под хеш-таблицу. [37]

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

Вторичная кластеризация. [39]

Когда позднее потребуется найти элемент в хеш-таблице, еще раз установите генератор случайных чисел, используя значение элемента. [40]

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

Основная причина выбора в качестве размера М хеш-таблицы простого числа для модульного хеширования иллюстрируется на рис. 14.3. В этом примере символьных данных с 7-разрядным кодированием ключ трактуется как число с основанием 128 - по одной цифре для каждого символа в ключе. [42]

Для 1 миллиона целочисленных ключей вычислите размер хеш-таблицы, при которой каждый из трех методов хеширования ( раздельное связывание, линейное зондирование и двойное хеширование) использует для обнаружения промаха при вставке в среднем столько же сравнений с ключами, как и BST-деревья, подсчитывая вычисление хеш-функции как сравнение. [43]

Объясните, чем упорядоченная хеш-таблица отличается от обычной хеш-таблицы. [44]

Сами списки могут размещаться как в памяти, принадлежащей хеш-таблице, так и в отдельной памяти. В первом случае цепочки называются внутренними, а во втором - внешними. [45]

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