Скученность

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

Из-за скученности нелегко определить среднюю длину поиска для открытой хешированной таблицы. Кривая А на рис. 5.11 показывает зависимость средней длины поиска от заполненности таблицы, определяемой выражением
фактическое число элементов М
максимально возможнее число элементов N 9 в предположении, что используется стандартная функция отображения для случайно распределенных ключей.

Однако имена идентификаторов, размещаемые в таблицах символов, распределены, вообще говоря, не случайно. Кривая В показывает среднюю длину поиска, получающуюся на практике при использовании идентификаторов из реальных программ, опубликованных в журналу Communications of ACM [8].

Из рис. 5.11 ясно, что эффективность хеширования быстро ухудшается, если таблица близка к заполнению. Когда возникает подобная ситуация, целесообразно завести большую таблицу, заново проведя хеширование всех элементов и разместив их в новой таблице. Момент, в который такое преобразование становится необходимым, зависит от частоты, с которой проверяются записи, и от соотношения времени вычисления хеш-значения от некоторого ключа с числом шагов, необходимых при появлении скученности. Необходимо сбалансировать затраты времени на вычисление новых хеш-значений с выигрышем за счет короткого среднего времени поиска для большей и более разреженной таблицы. Существует эмпирическое правило, согласно которому обычно нецелесообразно расширять таблицу до того момента, когда она заполнится на 80%, если каждый элемент должен выбираться только один раз; в то же время имеет смысл удвоить размер таблицы, заполненной на 40%,4если каждый элемент будет выбираться в среднем шесть раз.

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

Как уже упоминалось ранее в этой главе, таблицы символов строятся на первом проходе процесса трансляции обычно с использованием некоторой разновидности метода хеширования. На втором проходе всякий раз, когда в поле метки или адреса команды появляется некоторый символ, производится поиск в таблице, при котором данный символ используется в качестве ключа. Связанный с этим ключом адрес подставляется в машинный код. Если некоторый элемент не представлен в таблице, он помечается и передается ассемблером редактору связей или загрузчику. Такие символы должны обрабатываться на более поздней стадии преобразования машинного представления программы.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Скученность Этот небольшой пример иллюстрирует тот факт, что по мере роста числа элементов в таблице возрастает и вероятность того, что элемента не удается достичь за один шаг. Чем полнее таблица, тем больше средняя длина поиска. То же самое хеш-значение, т. е. та же самая позиция таблицы, будет с возрастающей частотой назначаться на первом шаге для различных ключей, поскольку число пустых позиций в таблице уменьшается. Это явление называется скученностью. Если оно встречается часто, эффективность механизма доступа к таблице снижается. Минимизация скученности зависит от распределения ключей, от алгоритма хеширования и от того, как обрабатываются элементы-синонимы, для которых получаются одни и те же исходные хеш-значения. Детальное исследование этих процедур можно найти в работах [8—11], ссылки на которые приведены в конце главы. Из-за скученности нелегко определить среднюю длину поиска для открытой хешированной таблицы. Кривая А на рис. 5.11 показывает зависимость средней длины поиска от заполненности таблицы, определяемой выражением фактическое число элементов М максимально возможнее число элементов N 9 в предположении, что используется стандартная функция отображения для случайно распределенных ключей. Однако имена идентификаторов, размещаемые в таблицах символов, распределены, вообще говоря, не случайно. Кривая В показывает среднюю длину поиска, получающуюся на практике при использовании идентификаторов из реальных программ, опубликованных в журналу Communications of ACM [8]. Из рис. 5.11 ясно, что эффективность хеширования быстро ухудшается, если таблица близка к заполнению. Когда возникает подобная ситуация, целесообразно завести большую таблицу, заново проведя хеширование всех элементов и разместив их в новой таблице. Момент, в который такое преобразование становится необходимым, зависит от частоты, с которой проверяются записи, и от соотношения времени вычисления хеш-значения от некоторого ключа с числом шагов, необходимых при появлении скученности. Необходимо сбалансировать затраты времени на вычисление новых хеш-значений с выигрышем за счет короткого среднего времени поиска для большей и более разреженной таблицы. Существует эмпирическое правило, согласно которому обычно нецелесообразно расширять таблицу до того момента, когда она заполнится на 80%, если каждый элемент должен выбираться только один раз; в то же время имеет смысл удвоить размер таблицы, заполненной на 40%,4если каждый элемент будет выбираться в среднем шесть раз. Один из серьезных недостатков хеш-таблиц (который, к счастью, не имеет отношения к таблицам символов) заключается в трудности исключения из них произвольного элемента. Исключенная позиция не может быть освобождена, так как это, возможно, нарушит цепочку ссылок для скученных элементов. На практике каждый элемент снабжается дополнительным признаком, указывающим, существует ли еще данный элемент, или же он был исключен. Как уже упоминалось ранее в этой главе, таблицы символов строятся на первом проходе процесса трансляции обычно с использованием некоторой разновидности метода хеширования. На втором проходе всякий раз, когда в поле метки или адреса команды появляется некоторый символ, производится поиск в таблице, при котором данный символ используется в качестве ключа. Связанный с этим ключом адрес подставляется в машинный код. Если некоторый элемент не представлен в таблице, он помечается и передается ассемблером редактору связей или загрузчику. Такие символы должны обрабатываться на более поздней стадии преобразования машинного представления программы.