Преимущества и недостатки связывания
Преимущества и недостатки связывания
Преимущества связывания достаточно очевидны. Во-первых, в таблице, использующей связывание, никогда не возникнет ситуация нехватки места. Мы сколько угодно можем продолжать добавлять элементы в хеш-таблицу, и при этом будет происходить только увеличение связных списков. Реализация вставки и удаления крайне проста - действительно, большая часть работы была проделана в главе 3.
Несмотря на простоту, связывание имеет один важный недостаток. Он заключается в том, что никогда не возникает ситуация нехватки места! Проблема в том, что длина связных списков все больше и больше увеличивается. При этом время поиска в связных списках также увеличивается, а поскольку любая имеющая смысл операция, которую можно выполнять с хеш-таблицами, предполагает поиск элемента (вспомните пресловутый метод htlIndexOf класса хеш-таблиц с линейным зондированием), большая часть рабочего времени будет тратиться на поиск в связных списках.
Стоит отметить еще ряд обстоятельств. При использовании алгоритма разрешения конфликтов линейного зондирования мы сознательно старались минимизировать количество выполняемых зондирований, расширяя хеш-таблицу, когда ее коэффициент загрузки начинал превышать две третьих. Как следует из результатов анализа, в этой ситуации для успешного поиска должно в среднем требоваться два зондирования, а для безрезультатного - пять. Подумайте, что означает зондирование. По существу, это сравнение ключей. Весь смысл применения хеш-таблицы заключался в уменьшении количества сравнений ключей до одного или двух. В противном случае вполне можно было бы выполнить бинарный поиск в отсортированном массиве строк. Что ж, при использовании связывания для разрешения конфликтов каждый раз, когда мы спускаемся по связному списку, пытаясь найти конкретный ключ, для этого мы используем сравнение. Если прибегнуть к терминологии метода с открытой адресацией, то каждое сравнение можно сравнить с "зондированием". Так сколько же зондирований в среднем требуется для успешного поиска при использовании связывания? Для алгоритма связывания коэффициент загрузки по-прежнему вычисляется как число элементов, деленное на число ячеек (хотя на этот раз оно может иметь значение больше 1.0), и его можно представить средней длиной связных списков, присоединенных к ячейкам хеш-таблицы. Если коэффициент загрузки равен F, то среднее число зондирований для успешного поиска составит F/2. Для безрезультатного поиска среднее число зондирований равно F. (Эти результаты справедливы для несортированных связных списков. Если бы связные списки были отсортированы, значения были бы меньше - исходя из теории, оба значения нужно разделить на log(_2_)(F))
- Как это ни удивительно, хотя на первый взгляд связывание кажется более удачным решением, нежели открытая адресация, при более внимательном рассмотрении этот метод оказывается не столь уж хорошим.
Суть всех выше приведенных рассуждений состоит в том, что в идеале необходимо увеличивать также хеш-таблицу, которая использует метод связывания для разрешения конфликтов. Использование методологии перемещения наиболее недавно использованных элементов в верхнюю часть соответствующих связных списков также обеспечивает существенный выигрыш в производительности.
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОКЧитайте также
Преимущества и недостатки data:URI
Преимущества и недостатки data:URI Вместе с техникой CSS Sprites (или как ее альтернатива) data:URI может существенно уменьшить число HTTP-запросов. Краткий список плюсов данного метода:Экономят HTTP-запросы, предотвращают издержки, связанные с большим числом объектов.Экономят число
Недостатки
А если по-другому? Ниже приведено сравнение других методов для снятия блокировки с загрузки скриптов, но все они также обладают своими недостатками. Метод Недостатки Используем атрибут defer тега scriptРаботает только в IEИспользуем document.write() для подключения тега
Преимущества и недостатки различных технологий удаленной регистрации
Преимущества и недостатки различных технологий удаленной регистрации В табл. 14.1 приведены наиболее важные характеристики различных технологий удаленной регистрации, рассмотренных в данной главе. Заметьте, что конкретные оценки могут различаться в зависимости от
Преимущества и недостатки проводной сети
Преимущества и недостатки проводной сети Рассмотрев достаточно много сетевых стандартов, которые находят применение в случае использования той или иной сетевой топологии, можно составить список основных преимуществ и недостатков проводной сети. Данная информация
Преимущества и недостатки беспроводной сети
Преимущества и недостатки беспроводной сети В любом деле есть свои преимущества и недостатки, однозначно определяющие выбор той или иной технологии в конкретных условиях. Это правило касается и беспроводных сетей.Рассмотрим основные преимущества беспроводной
12.20 Недостатки DNS
12.20 Недостатки DNS Domain Name System — очень важная система. Некорректные элементы базы данных могут сделать невозможным доступ к прикладным хостам. Поскольку многие администраторы используют распределенную базу данных с ручным вводом информации, весьма вероятно возникновение
3.1.2. Недостатки
3.1.2. Недостатки А теперь ложка дегтя – о недостатках I2P. Нет ничего идеального, и I2P – тоже не идеальна. Начнем с самой концепции I2P. Анонимизация и шифрование трафика происходит лишь внутри этой сети. Работая с I2P, вы можете обратиться только к I2P-ресурсам (к I2P-сайтам, почте,
Программный способ связывания данных
Программный способ связывания данных С помощью Windows Forms связывание данных можно организовать программно. Это позволяет добиться более высокой гибкости в ситуациях, когда расположение полей неизвестно во время создания приложения либо требуется явно выразить связь
Перспективы отображения, статического и динамического связывания и пользовательских атрибутов
Перспективы отображения, статического и динамического связывания и пользовательских атрибутов Даже после множества примеров применения соответствующих подходов вам может быть не ясно, когда же следует использовать отображение, динамическую загрузку, динамическое
2.3.5. Преимущества и недостатки библиотек
2.3.5. Преимущества и недостатки библиотек Познакомившись со статическими архивами и совместно используемыми библиотеками. читатели, очевидно, задумались: какие же из них лучше использовать? Есть несколько важных моментов, о которых следует помнить.Большим преимуществом
Преимущества и недостатки линейного зондирования
Преимущества и недостатки линейного зондирования В общем случае, если в хеш-таблице занято небольшое количество ячеек, можно надеяться, что для реализации большинства поисков, успешных или безрезультатных, придется выполнить всего одну-две операции зондирования.
Разрешение конфликтов посредством связывания
Разрешение конфликтов посредством связывания Если мы готовы использовать дополнительные ячейки, кроме тех, которые требуются самой хеш-таблице, можно воспользоваться другой эффективной схемой разрешения конфликтов - схемой с закрытой адресацией. Этот метод называется
7.7. Директива связывания extern "C" A
7.7. Директива связывания extern "C" A Если программист хочет использовать функцию, написанную на другом языке, в частности на С, то компилятору нужно указать, что при вызове требуются несколько иные условия. Скажем, имя функции или порядок передачи аргументов различаются в
2.1. Преимущества и недостатки стационарного ПК и ноутбука
2.1. Преимущества и недостатки стационарного ПК и ноутбука Преимущества стационарного компьютера следующие:Удобная клавиатура — что ни говори, а самая простенькая клавиатура стационарного компьютера удобнее клавиатуры любого ноутбука.Монитор с крупным экраном —
14.2.2. Преимущества и недостатки DVD
14.2.2. Преимущества и недостатки DVD У всего есть свои преимущества и недостатки. Есть они и у DVD. Начнем с преимуществ.? Большая емкость диска — лишнего места не бывает! Но, с другой стороны, 4,7 Гбайт хорошо для записи фильма в цифровом качестве (или коллекции фильмов в MPEG-4). Для
О реализации динамического связывания
О реализации динамического связывания Может возникнуть опасение, что динамическое связывание - это дорогой механизм, требующий во время выполнения поиска по графу наследования и поэтому накладных расходов, растущих с увеличением глубины этого графа.К счастью, это не