В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 12
Текст из файла (страница 12)
Естественно, оценка производительности удаления ключа останется логарифмической: (log ).Однако, что происходит с местом на диске при удалении страницы? Ведь удаляем мы еёиз середины файла! Здесь нас выручит то, что все страницы одного размера – мы будемпросто в отдельном контейнере в оперативной памяти поддерживать список таких опустевших внутренних страниц – и, если возникнет нужда через какое-то время создать новуюстраницу – сначала проверим, есть ли незанятые страницы в этом списке? Если есть –займём такую ранее выделенную страницу под новые данные, если нет – создадим новуюстраницу в конце файла, как раньше. То есть, при удалении страницы никакие смещения,записанные в рабочих страницах – не меняются и с этими страницами возможна нормальная работа. -дерево порядка 1 (его ещё называют 2−3-деревом, т.к.
внутренние узлы содержат либо две,либо три дочерние связи) довольно успешно используется для балансировки дерева поиска воперативной памяти компьютера.Ещё один популярный вариант этой структуры данных называется + -деревом. Он экономитиспользуемую оперативную память в том случае, когда хранятся пары «ключ-значение, связанное с этим ключом», причём размер данных «значения» достаточно велик. От -дереваона отличается тем, что абсолютно все ключи (или пары ключ-значение) представлены в листьях, которые, к тому же, ещё провязаны в линейный одно- или даже двухсвязный список,образуя упорядоченное по возрастанию ключей множество пар ключ-значение – для удобстваих упорядоченного перебора.
Внутренние, не-листовые страницы используются только дляпоиска и в них хранятся только ключи, некоторые из которых дублируются на каждом извышележащих уровней:931295345678Рис. 25: + -дерево56911101112Битовые вектора, хэш-таблицыРассмотрим такой интересный вопрос: а можно ли построить ассоциативный контейнер,в котором можно будет искать значения за константное, а не за логарифмическое время?Т.е., можно ли сделать так, чтобы время поиска вообще не зависело от того, сколько вконтейнере хранится элементов?Если бы нам надо было бы найти по целочисленному ключу некоторое связанное с нимзначение (контейнер типа map), то можно было бы просто использовать массив, длинакоторого равна максимально возможному ключу плюс один и сохранять значения простов элементах этого массива.
То есть, роль ключа будет играть просто индекс в этом массиве.Очевидно, что операция взятия элемента по его индексу не зависит от размера массива,нам ведь достаточно просто прибавить смещение, равное индексу массива к указателю наначало массива – это ровно одна операция!Если нам нужно решать задачи для ассоциативного контейнера типа set (множество), тоесть просто быстро давать ответ на вопрос «есть такое-то целое число во множестве илинет?», то можно существенно сэкономить занимаемую память, если просто хранить битовый вектор.
Если -тый бит вектора установлен в единицу – то мы считаем, что число входит в множество, если в ноль – то число отсутствует в нём. Такой вектор будет компактнее в восемь раз по сравнению с вектором значений байтов «истина» и «ложь» и в 32раза компактнее массива целых чисел.Однако даже с целыми числами возникает вопрос: если мы априори не знаем, какое можетбыть максимальное значение ключа во множестве, или это максимальное значение слишком велико (миллиард) – то вектора понадобятся слишком длинные, что потребует многихгигабайт памяти. Что уж говорить о ключах произвольной природы типа вещественныхчисел, строк или даже произвольных структур данных! А ведь понятно, что с данными такой природы тоже могут возникнуть задачи поиска, мы же их успешно решали с помощьюдеревьев поиска.Решением будет вычисление специально подобранной функции с ключом в качестве аргумента.
Пусть пока для простоты ключи у нас будут целочисленными, но произвольными,любой величины. Мы бы хотели подобрать такую функцию, которая бы отобразила любойключ на целое число, которое можно было бы использовать в качестве индекса в массивенекоторого заранее зафиксированного размера, превышающего общее количество ключей,которые мы бы хотели сохранить в контейнере.Неплохим вариантом такой функции, которая отображает произвольное целое число в диапазон от нуля до некоторого наперёд заданного будет операция нахождения остатка отделения ключа на число :() = %.Действительно, ведь все возможные значения остатка как раз и будут занимать диапазон отнуля до − 1, то есть пробегать все возможные значения индекса массива размерности .Такую функцию называют хэш-функцией (от английского слова hash – мелко рубленное,перемешанное блюдо, литературный перевод на русский язык – винегрет), а массив, кудабудут сохраняться значения – хэш-таблицей.Теперь возникает следующий вопрос: если у нас значения ключей не ограничены, а значения хэш-функции – ограничены, то, весьма вероятно, что функция не будет взаимнооднозначной, то есть разным ключам с некоторой ненулевой вероятностью может сопоставиться один и тот же индекс хэш-таблицы.
В таком случае, говорят, что в хэш-таблицевозникает коллизия:57T[0]H(K1)I1T[I1]:K1H(K2)I1H(K3)I1K2K3T[N]Рис. 26: Коллизии в хэш-таблице и их разрешение методом цепочекПростейший метод их разрешения – просто стартовать в каждой ячейке хэш-таблицы односвязный список, в котором надо будет искать значения исходного ключа простым перебором. Такой метод разрешения называется методом цепочек. Если мы не найдём ключ вэтой «цепочке», то можно быть уверенным, что ключ отсутствует в контейнере.
Если мыего захотим добавить – достаточно будет его вписать в конец цепочки.Очевидно, что хэш-функция тем лучше, чем более короткие цепочки она порождает дляданного размера хэш-таблицы. В идеале она должна была бы просто равномерно «размазать» все возможные значения ключей по всей таблице, то есть, оптимальной с точкизрения минимизации числа коллизий будет просто генератор псевдослучайных чисел с равномерной плотностью распределения вероятностей. Псевдо – потому, что такой генератордолжен давать однозначные результаты, то есть, независимо от порядка, в котором подаются ключи на хэширование – он каждому ключу должен сопоставить одну и ту же ячейкухэш-таблицы.Известно, что наиболее часто используемый генератор псевдослучайных чисел как раз иоснован на функции взятия остатка от деления – и именно поэтому функция взятия остаткапоказывает неплохие результаты в качестве функции хэширования.С другой стороны, в отличие от деревьев поиска хэш-таблицы никак не упорядочиваютсохраняемые в них ключи, этот порядок вообще-то будет зависеть от порядка, в которыхмы подаем ключи на хэширование, то есть, может быть разным для одного и того женабора ключей.Очевидное соображение: если мы ожидаем, что цепочки будут длинными, то в качестве«хранилища коллизий» лучше использовать не связный список, а дерево поиска или дажехэш-таблицу второго уровня.Еще одно очевидное соображение: чем меньше заполнена таблица – тем меньше вероятность коллизии, то есть, количество коллизий будет зависеть от соотношения планируемого количества хэшируемых ключей и размера хэш-таблицы.
Это говорит в пользу того,что размер хэш-таблицы, – который выбирается заранее, – следует выбирать как можнобольше.Но вот нетривиальный факт: в типовых случаях среднее количество коллизий оказываетсянебольшим даже при 75% заполнении хэш-таблицы. В теории вероятностей это можнодоказать строго, мы же здесь ограничимся только результатами этого доказательства (см.табл.1).58Дробные числа тут можно понимать в смысле: «105 коллизий на 100 операций вставки всреднем при коэффициенте заполнения таблицы 10%». Мы видим, что среднее число коллизий растет не очень быстро, поэтому рекомендация по выбору размера хэш-таблицы отсюдаследует довольно простая: если вы планируетедобавить в таблицу известное количество ключей – увеличьте её размер на четверть относительно этого количества и при этом среднее количество коллизий на одну операцию будет всёещё меньше двух, то есть, в среднем операциявставки будет занимать константное время.коэффициентзаполнениятаблицы10%25%50%75%90%95%99%среднее числоколлизий наодну операцию1.051.151.391.852.563.154.66Таблица 1: Количество коллизий приразной заполненности хэш-таблицыУвы, эти соображения не страхуют от возможных неприятностей – случайно можно получить такое соотношение размера таблицы, хэш-функции и ключей, что какая-то однацепочка окажется очень длинной.
Но можно надеяться, что это будет весьма редкой ситуацией. Для того, чтобы немного застраховаться от подобных неприятностей рекомендуютразмер таблицы (и модуль в хэш-функции) выбирать простым числом. То есть, полнаярекомендация по выбору размера хэш-таблицы звучит так: увеличьте размер на 25% относительно планируемого количества ключей, после чего найдите ближайшее сверху отэтого числа простое число – и используйте его в качестве модуля хэш-функции и размерахэш-таблицы.Другая прагматическая рекомендация – в ходе добавления ключей можно каждый раз подсчитывать максимальное или среднее количество коллизий и сохранять его где-то рядомс хэш-таблицей. Если это число покажется вам чрезмерным, можно устроить рехэширование : увеличить размер таблицы в два раза (опять найти ближайшее сверху простое число)и переместить все ключи из старой таблицы в новую, вычисляя для каждого ключа хэшфункцию с новым модулем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
