Анализ структур данных. Часть 2: Очередь, стек и хеш-таблица

ОГЛАВЛЕНИЕ

Эта статья - вторая часть серии из 6 статей о структурах данных в .NET Framework - посвящена трем наиболее часто рассматриваемым структурам данных: очереди, стеку и хеш-таблице. Как мы увидим, очередь и стек делаются с помощью ArrayList-а, обеспечивая место для хранения переменного числа объектов, накладывая, однако, при этом ограничения на порядок доступа к элементам. Хеш-таблица - это структура данных, похожая на массив, но с большей гибкостью индексирования элементов.

Часть 2: Очередь, стек и хеш-таблица

Обзор: Эта статья - вторая часть серии из 6 статей о структурах данных в .NET Framework - посвящена трем наиболее часто рассматриваемым структурам данных: очереди, стеку и хеш-таблице. Как мы увидим, очередь и стек делаются с помощью ArrayList-а, обеспечивая место для хранения переменного числа объектов, накладывая, однако, при этом ограничения на порядок доступа к элементам. Хеш-таблица - это структура данных, похожая на массив, но с большей гибкостью индексирования элементов. В то время как в массиве элементы индексируются с помощью порядковой величины, элементы хеш-таблицы могут быть индексированы посредством любого объекта.

Введение

В Части 1: Подробный анализ структур данных, мы остановились на определении понятия структур данных, методах оценки их эффективности, а также на том, как эти соображения влияют на выбор той или иной структуры данных для конкретного алгоритма. Помимо изучения базовых вещей о структурах данных и анализе их эффективности, мы также рассмотрели наиболее часто используемую структуру данных - массив.

Массив содержит совокупность однородных элементов (элементов одного типа), каждому из которых соответствует порядковый индекс. Физически, содержимое массива располагается в памяти в виде непрерывной области. Благодаря этому чтение или запись элемента массива осуществляется очень быстро.

Два недостатка массивов - это их однородность и то, что размер массива должен быть явно задан. Для устранения этого недостатка библиотека классов .NET Framework содержит в себе такую структуру данных как ArrayList, которая представляет собой совокупность элементов разного типа. Причем его размер увеличивается автоматически при необходимости. Как мы уже обсудили в предыдущей статье, реализация ArrayList в .NET Framework использует массив типа object. Каждый вызов метода Add() ArrayList-а проверяет, достаточен ли размер внутреннего массива object-ов для хранения дополнительных элементов и если нет, то размер этого внутреннего массива автоматически удваивается.

Во второй части серии мы продолжим наше знакомство с массивоподобными структурами данных и, прежде всего, рассмотрим очередь (queue) и стек (stack). Подобно ArrayList-у, эти две структуры данных содержат совокупность элементов разного типа (heterogeneous data) в непрерывной области памяти (contiguous block). Однако, как очередь, так и стек, налагают ограничения на порядок доступа к данным.

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


 

Структура данных "Очередь": обработка по принципу "Первым пришел, первым обслужен"

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

  • Обработка по принципу "Первым пришел, первым обслужен" (First come, first served; FCFS)
  • Обработка, основанная на приоритетах

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

Представим, что нам требуется создать компьютерную службу, и что мы хотим обрабатывать запросы к ней в порядке их получения. Поскольку запросы могут появляться быстрее, чем мы будем способны их обработать, нам потребуется помещать запросы в некоторый буфер, который будет хранить эти запросы в порядке их прихода.

Возможное решение - использовать ArrayList и целочисленную переменную nextJobPos, в которой будет храниться индекс следующей задачи, которая должна быть отправлена на обработку. С приходом нового задания мы попросту будем использовать метод Add() для добавления задачи в конец ArrayList-а. Как только мы готовы обработать очередную задачу, находящуюся в буфере, мы берем это задание из nextJobPos-ого элемента ArrayList-а и увеличиваем nextJobPos на 1. Следующая программа описывает этот алгоритм:

using System;
using System.Collections;
public class JobProcessing
{
private static ArrayList jobs = new ArrayList();
private static int nextJobPos = 0;
public static void AddJob(string jobName)
{
jobs.Add(jobName);
}
public static string GetNextJob()
{
if (nextJobPos > jobs.Count - 1)
return "NO JOBS IN BUFFER";
else
{
string jobName = (string) jobs[nextJobPos];
nextJobPos++;
return jobName;
}
}
public static void Main()
{
AddJob("1");
AddJob("2");
Console.WriteLine(GetNextJob());
AddJob("3");
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
AddJob("4");
AddJob("5");
Console.WriteLine(GetNextJob());
}
}

Вывод программы таков:

1
2
3
NO JOBS IN BUFFER
NO JOBS IN BUFFER
4

Притом, что такой подход исключительно прост и прямолинеен, он ужасно неэффективен. Для новичков поясняем: ArrayList будет неограниченно расти с каждым добавлением новой задачи в буфер. Это будет происходить даже в том случае, когда запросы обрабатываются немедленно после помещения их в буфер. Рассмотрим пример, когда каждую секунду в буфер добавляется задача и из буфера удаляется задача. Это означает, что раз в секунду вызывается метод AddJob(), который в свою очередь вызывает метод Add() ArrayList-а. При непрерывном вызове метода Add(), размер внутреннего массива ArrayList-а постоянно удваивается по мере необходимости. После 5 минут (300 секунд) размер внутреннего массива ArrayList-а достигнет 512 элементов, несмотря на то, что в буфере никогда не находилось более 1 задачи одновременно! Размер массива будет, конечно же, продолжать расти в процессе работы программы и с приходом новых задач.

Причина того, что ArrayList разрастается до таких невероятных размеров в том, что память буфера, использовавшаяся для старых запросов, не используется повторно. Ведь когда мы добавляем первое задание в буфер, а потом удаляем его из буфера после отправки на обработку, первая позиция ArrayList-а может быть использована повторно для размещения в ней нового запроса. Рассмотрим процесс диспетчеризации задач, представленный в программе, написанной выше. После исполнения первых двух строк -AddJob("1") и AddJob("2")-содержимое ArrayList-а будет выглядеть так (рис. 1):

Рисунок 1. ArrayList после исполнения первых двух строчек кода

Заметьте, что ArrayList на этот момент содержит 16 элементов потому, что при создании ArrayList-а по умолчанию создается внутренний массив из 16 элементов типа object. После этого вызывается метод GetNextJob(), который удаляет первую задачу из буфера. В результате мы получаем ситуацию, показанную на рис. 2.

Рисунок 2. Программа после вызова метода GetNextJob()

Когда выполняется AddJob("3"),нам нужно добавить очередную задачу в буфер. Очевидно, что первый элемент ArrayList-а (с индексом 0) можно использовать повторно. Изначально, возможно, и есть некий смысл поместить третью задачу в нулевой элемент. Однако, мы вынуждены отвергнуть такой подход, рассмотрев, что же получится если после выполнения AddJob("3") мы вызовем AddJob("4"), а затем два вызова метода GetNextJob(). Если бы мы поместили третью задачу по нулевому индексу, а четвертую - в элемент с индексом 2, мы бы получили следующую неприятную ситуацию, показанную на рисунке 3.

Рисунок 3. Что получится при помещении третьей задачи по нулевому индексу

Теперь если мы вызовем GetNextJob() из буфера будет удалена вторая задача, значение nextJobPos будет увеличено на 1 и станет равным 2. Таким образом, при повторном вызове GetNextJob(), из буфера будет удалена четвертая задача, которая в результате будет обработана раньше третьей. Мы получаем, что нарушается порядок "Первым пришел, первым обслужен", который мы договорились поддерживать.

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

Чтобы исправить это, нам придется сделать ArrayList циклическим (сircular). Циклический массив не имеет определенного начала или конца. Точнее, конец и начало массива хранятся в определенных переменных. Графическое представление циклического массива показано на Рисунке 4.

Рисунок 4. Пример циклического массива

При работе с циклическим массивом, метод AddJob() помещает новую задачу в элемент с индексом endPos, а затем "инкрементирует" endPos. Метод GetNextJob() забирает задачу из элемента с индексом startPos, присваивает элементу с индексом startPos значение null, а затем "инкрементирует" startPos. Слово "инкрементировать" (increment) значит увеличивать на единицу. Оно было помещено в кавычки, потому что в данном случае под "инкрементацией" подразумеваются чуть более сложные действия, нежели простое прибавление единицы к целочисленному значению переменной. Чтобы понять, почему мы не можем просто взять и прибавить 1, рассмотрим случай, когда endPos равняется 15. Если мы прибавим к endPos единицу, значение endPos станет равным 16. При следующем вызове AddJob() мы попытаемся получить доступ к элементу с номером 16, что приведет к исключению IndexOutOfRangeException.

Вместо этого, когда endPos равен 15, нам хотелось бы "инкрементировать" endPos так, чтобы его значение стало равным 0. Мы можем сделать это, написав функцию increment(variable), которая бы проверяла, что значение фактического входного параметра равно размеру массива, и в этом случае сбрасывала это значение в 0. Альтернативный вариант - это прибавлять единицу, однако сложение выполнять по модулю размера массива. В этом случае, код функции increment() будет таким:

int increment(int variable)
{
return (variable + 1) % theArray.Length;
}

Примечание Бинарный оператор % в выражении x % y вычисляет остаток от деления x на y. Остаток всегда будет в пределах между 0 и y - 1.

Этот подход отлично работает, если наш буфер никогда не будет содержать более 16 элементов. А что будет, если мы захотим добавить новую задачу в буфер, в котором уже есть 16 задач? Like Подобно методу Add() ArrayList-a, нам придется соответствующим образом изменить размер циклического массива, например, удвоив размер массива.


Класс System.Collections.Queue

Функциональность, которую мы только что описали - добавление и удаление элементов из буфера в порядке FCFS при максимальной оптимизации используемого объема памяти - предоставляется стандартной структурой данных - Очередью. Библиотека классов .NET Framework Base содержит встроенный класс System.Collections.Queue. Аналогично тому, как мы использовали выше в написанном нами коде методы AddJob() и GetNextJob(), класс Queue cпредоставляет соответствующую функциональность в виде методов Enqueue() и Dequeue() соответственно.

За кулисами, класс Queue использует внутренний циклический массив элементов типа object и две переменные, служащих в качестве маркеров начала и конца циклического массива: head (голова) и tail (хвост). По умолчанию начальный размер очереди равен 32 элементам, хотя эту величину можно настроить при вызове конструктора очереди. Поскольку очередь для хранения данных использует массив object-ов, в ней можно хранить переменные любых типов.

Метод Enqueue() определяет, достаточно ли места для добавления нового элемента в очередь. Если да, то элемент просто записывается в ячейку массива с индексом tail, после чего значение tail "инкрементируется" (т.е. увеличивается на единицу и от результата берется остаток от деления его на длину массива). Елси места недостаточно, размер массива увеличивается в n раз. Число n называется growth factor - фактор роста. По умолчанию его значение равно 2.0, а значит, по умолчанию размер массива удваивается. Отметим, что фактор роста вы также можете задавать в конструкторе класса Queue.

Метод Dequeue() возвращает элемент, который находится в ячейке массива с индексом head. После этого он присваивает элементу head значение null и "инкрементирует" head. Для тех случаев, когда вы желаете лишь прочесть значение элемента из головы очереди, но приэтом не удалять его оттуда, класс Queue предлагает метод Peek().

Важно понимать то, что при работе с очередью, в отличие от ArrayList-а, вы не имеете доступа к ее произвольному элементу. Например, вы не можете посмотреть третий элемент очереди, не удалив из нее первые 2 элемента. (Отметим, однако, что класс Queue имеет метод Contains(), используя который вы можете определить, содержит ли очередь тот или иной конкретный элемент). Если вы точно уверены, что вам необходим произвольный доступ (random access), то структура данных "очередь" не для вас - используйте лучше ArrayList. Безусловно, очередь является идеальным выбором в ситуациях, когда вам необходимо выполнять обработку элементов данных точно в порядке их поступления.

Примечание Очереди также часто называют структурами данных типа FIFO - First In, First Out. Смысл этой аббревиатуры аналогичен FCFS и по-русски звучит примерно, как "первым вошел, первым вышел".


 

Структура данных "стек": Первым пришел, последним обслужен (First Come, Last Served)

Очередь дает нам доступ к элементам в порядке "первым пришел, первым ушел" и использует для этих целей внутренний циклический массив object-ов. Такая функциональность предоставляется посредством методов Enqueue() и Dequque(). Порядок обработки "первым пришел, первым ушел" имеет много применений в реальных приложениях, таких как веб-серверы, очереди печати и прочих программах, ориентированных на обработку множественных запросов.

Другой популярной схемой обработки в компьютерных программах является подход "первым пришел, последним ушел". Структура данных, предоставляющая такой доступ к своим элементам, называется стек (или магазин - по аналогии с магазином автоматического оружия). Библиотека классов .NET Framework содержит класс System.Collections.Stack, который, подобно классу Queue, хранит свои элементы в циклическом массиве типа object. Управление данными, содержащимися в стеке, происходит с помощью метода Push(item) ("втолкнуть"), который помещает объект, переданный в качестве параметра в стек, и метода Pop() ("извлечь"), который возвращает объект из вершины стека, удаляя его из стека.

Графически стек можно изобразить в виде вертикальной "пирамиды" элементов. При "заталкивании" элемента в стек он помещается сверху над всеми прочими элементами. Извлечение элемента из стека, удаляет его свершины стека. Следующие 2 рисунка показывают стек после "заталкивания" в него элементов 1, 2, and 3 и последующего их удаления из стека.

Рисунок 5. Графическое представление стека из трех элементов

Рисунок 6. Графическое представление стека после извлечения элементов

Отметим, что размер стека по умолчанию устанавливается равным 10 элементам, в отличие от 32 элементов очереди. Однако, как и раньше с классами Queue и ArrayList, вы легко можете изменить это количество, задав его в конструкторе класса. Как и в случае с ArrayList-ом, когда возникает необходимость увеличить стек, его размер автоматически удваивается. (Вспомним, что у очереди фактор роста может быть задан в конструкторе)

Примечание Стеки часто называют структурами данных типа LIFO = Last In, First Out ("Последним вошел, первым вышел").

Стеки - желанные гости в Computer Science

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

Например, рассмотрим любой императивный язык программирования вроде C# (императивный - значит, задающий жесткую последовательность действий, в противоположность функциональным и логическим языкам программирования - прим. перев.). Когда программа, написанная на C#, выполняется, CLR хранит стек вызовов, в котором записывается информация о вызове функций программы. При каждом вызове функции, ее информация добавляется на вершину стека. При завершении функции эта информация удаляется из стека. Информация в вершине стека вызовов представляет текущую функцию, выполняющуюся в данный момент. Чтобы самим взглянуть на стек вызовов, создайте проект в Visual Studio® .NET, установите точку останова (breakpoint), выберите пункт меню Debug/Start. Когда выполнение программы остановится на breakpoint-е, вызовите окно Call Stack с помощью пункта меню Debug/Windows/Call Stack.

Стеки также часто используются при разборе (parsing) грамматик (от простых алгебраических выражений до языков программирования), как средство моделирования рекурсии, и даже как модель исполнения инструкций.


 

Ограничения порядкового индексирования

Вспомним Часть 1 этой серии статей, где было дано следующее определение массива: "совокупность элементов одного типа, индексированных с помощью порядковой величины". То есть, iый элемент массива может быть прочитан или записан за постоянное время. (Вспомним также, что постоянное время доступа обозначается как O(1))

Однако лишь в немногих ситуациях нам известна позиция элемента, интересующего нас. Например, рассмотрим базу данных сотрудников предприятия. Каждый сотрудник может быть идентифицирован уникальным образом с помощью номера социального страхования (в США), который имеет вид DDD-DD-DDDD, где D - это цифра (0-9). Если бы у нас был неупорядоченный массив сотрудников, то, скажем, для поиска сотудника с номером 111-22-3333 нам бы потенциально потребовалось произвести поиск среди всех элементов массива сотрудников - операция, сложность которой равна O(n). Лучше было бы предварительно отсортировать сотрудников по их номеру социального страхования, уменьшив тем самым асимптотическое время поиска до O(log n).

В идеале, нам хотелось бы находить записи о каждом конкретном сотруднике за время O(1). Одним из способов реализовать это будет создать огромный массив, в котором номер каждого элемента был бы номером социального страхования. То есть, наш массив начинался бы с элемента номер 000-00-0000 и заканчивался бы элементом 999-99-9999, как показано на рисунке внизу:

Рисунок 7. Массив, содержащий все 9-значные числа

Как показано на рисунке, каждая запись о сотруднике содержит некоторую информацию: имя (Name), номер телефона (Phone), зарплату(Salary), и так далее. Каждая запись индексируется посредством номера социального страхования. По такой схеме информация о любом работнике может быть получена из массива за постоянное время - О(1). Недостаток этого подхода ужасающая растрата памяти - всего существует 109 (миллиард) различных номеров социального страхования. Для компании, в которой работает 1000 сотрудников, лишь 0,0001% массива будет фактически использовано. (На деле, чтобы почти полностью заполнить этот массив, вашей компании придется нанять ни много, ни мало - одну шестую часть населения Земли)


Сжатие порядкового индексирования с помощью хеш-функции

Ясно, что создание массива из миллиарда элементов для хранения информации о тысяче сотрудников неприемлемо. При этом нам очень хочется иметь высокую производительность и скорость доступа к информации о каждом конкретном сотруднике за постоянное время, не зависящее от числа элементов в структуре данных. Как вариант, можно использовать для номерации записей сотрудников не весь номер социального страхования целиком, а лишь его последние 4 цифры. Таким образом, вместо массива, простирающегося от элемента номер 000-00-0000 до 999-99-9999-го элемента, мы получим массив с диапазоном элементов от 0000 до 9999. На рисунке 8 показан такой "урезанный" массив.

Рисунок 8. Урезанный массив

При таком подходе мы имеем как постоянное время поиска (не зависящее от числа сотрудников), так и сравнительно экономный расход памяти. Выбор в пользу именно последних 4 цифр был сделан произвольно. С равным успехом мы могли использовать 4 средние цифры или, скажем, первую, третью, восьмую и девятую.

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

Хеш-функция - это функция, осуществляющая процесс хеширования. Для номера социального страхования наша хеш-функция, H, может быть описана следующим образом:

H(x) = последние 4 цифры числа x

На вход H подается любой 9-значный номер социального страхования. На выходе мы имеем четырехзначное число, которое состоит из последних 4 цифр входного числа. В математических терминах, H осуществляет отображение (maps) множества 9-значных номеров социального страхования на множество 4-значных чисел, как показано на рис. 9.

Рисунок 9. Иллюстрация действия хеш-функции

Рисунок 9 демонстрирует, помимо прочего, явления, присущие всем хеш-функциям, называемые коллизиями (collisions). Коллизия - это явление, когда хеш-функция отображает 2 разных элемента из более широкого множества в один и тот же элемент более узкого множества. В нашем случае все номера социального страхования, оканчивающиеся на 0000, отобразятся хеш-функцией в 0000. Т.е. значением хеш-функции для 000-00-0000, 113-14-0000, 933-66-0000 и многих других номеров будет одно и то же число - 0000.

Возвращаясь назад к содержанию нашего примера, рассмотрим, что случится, если мы попытаемся добавить запись о новом сотруднике, номер которого 123-00-0191. Очевидно, что при этом у нас возникнут проблемы, поскольку в массиве уже существует сотрудник в ячейке с номером 0191 (Jisun Lee).

Математическое примечание Хеш-функция в более строгих математических терминах может быть определена как функция f : A -> B (А и B - конечные множества). Поскольку мы имеем, что |A| > |B|, то очевидно, что f не является взаимно-однозначной функцией. Следовательно, будут иметь место коллизии.

Ясно, что возможность возникновения коллизий вызовет некоторые проблемы. В следующем разделе мы рассмотрим взаимосвязь между выбором хеш-функции и вероятностью возникновения коллизий, а также обсудим некоторые стратегии борьбы с коллизиями. После этого мы изучим класс System.Collections.Hashtable, который представляет собой реализацию хеш-таблицы. Особое внимание мы обратим на хеш-функцию класса Hashtable, методы разрешения коллизий, а также некоторые примеры использования класса Hashtable на практике.

Избегание и разрешение коллизий

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

Частота коллизий напрямую связана с используемой хеш-функцией и распределением данных, подаваемых на вход хеш-функции. В нашем примере использование последних 4 цифр номера социального страхования сотрудника в качестве хеш-функции было бы практически идеальным вариантом, если предположить, что номера социального страхования присваиваются людям абсолютно случайным образом. Однако, если эти номера назначаются таким образом, что те, кто родились в один и тот же год или в одной и той же местности, получают номера, последние цифры которых одинаковые, то использование последних 4 цифр может вызвать большое число коллизий в случае если даты или места рождения ваших сотрудников распределены не равномерно.

Примечание Тщательный анализ хеш-функции требует некоторых знаний из области математической статистики, что выходит за рамки этой статьи. Главным образом требуется, чтобы вероятность выбора каждого конкретного значения из области значений хеш-функции для хеш-таблицы с k ячейками равнялась 1/k. (Если вы почти ничего не поняли - не очень смущайтесь!)

Выбор соответствующей хеш-функции называют избеганием коллизий. Этому посвящено большое количество исследований, поскольку хеш-функция оказывает решающее влияние на производительность хеш-таблицы. В следующем разделе мы рассмотрим хеш-функцию, используемую классом Hashtable из .NET Framework.

При возникновении коллизии существуют различные подходы к ее разрешению. Задача разрешения коллизии, собственно, состоит в том, чтобы найти некоторое другое место для объекта, добавляемого в хеш-таблицу (поскольку при коллизии обычное место, вычисленное с помощью хеш-функции, занято). Один из простейших методов называется линейная последовательность проб (linear probing) и работает так:

  1. Когда новый элемент добавляется в хеш-таблицу, используем хеш-функцию, чтобы определить, в какое место таблицы следует записать этот элемент.
  2. Проверяем, существует ли элемент в позиции, найденной на шаге 1 с помощью хеш-функции. Если позиция свободна, помещаем туда элемент, в противном случае идем на шаг 3.
  3. Пусть номер позиции, выданный хеш-функцией - i. Тогда мы проверяем, занята ли позиция с номером i + 1. Если и она занята, то проверяем позицию i + 2 и так далее до тех пор, пока не найдем свободную ячейку.

Рассмотрим пример, когда мы поместили в таблицу записи о следующих 4 сотрудниках: Alice (333-33-1234), Bob (444-44-1234), Cal (555-55-1237), Danny (000-00-1235) и Edward (111-00-1235). После занесения этих данных в хеш-таблицу последняя будет выглядеть, как показано на рис. 10.

Рисунок 10. Хеш-таблица с 4 сотрудниками с похожими номерами

Номер социального страхования Алисы хешируется в значение 1234 и ее запись помещается в 1234-й элемент массива. Далее, номер Боба тоже хешируется в 1234, однако ячейка 1234 уже занята записью Алисы, таким образом Боб занимает следующую свободную ячейку - 1235. После Боба мы добавляем запись Кэла, хеш-функция выдает для его номера социального страхования значение 1237. Поскольку в ячейке 1237 никого нет, запись Кэла помещается в нее. Следующий - Дэнни. Его номер отображается хеш-функцией в 1235. Поскольку позиция 1235 занята, проверяется ячейка с номером 1236. Т.к. ячейка 1236 вакантна, Дэнни записывается в нее. В конце добавляется запись Эдварда, его номер социального страхования также хешируется в 1235. Поскольку 1235 занята, проверяется 1236. Она также занята, проверяем 1237. Эта ячейка занята Кэлом, и мы проверяем 1238, которая оказывается свободной. Итак, запись Эдварда добавляется в ячейку 1238.

Из-за коллизий возникают проблемы и при поиске в хеш-таблице. Например, представим, что нам нужно найти в хеш-таблице из предыдущего примера информацию об Эдварде. Мы берем номер социального страхования Эдварда 111-00-1235, хешируем его, получаем 1235 и начинаем поиск. В ячейке 1235 мы находим Боба, а не Эдварда. Таким образом, нам нужно теперь проверить ячейку 1236, но там Дэнни. Наш линейный поиск будет продолжаться либо до тех пор, пока мы не найдем Эдварда, либо когда мы дойдем до пустой ячейки. Последнее будет означать, что в хеш-таблице не существует сотрудника с номером социального страхования 111-00-1235.

Несмотря на то, что линейная последовательность проб - простая процедура, она является не лучшим способом разрешения коллизий, поскольку ведет к образованию кластеров (clustering). Поясним это понятие. Представим, что первые 10 сотрудников, которых мы добавили в хеш-таблицу, все имеют номер социального страхования, заканчивающийся на одни и те же 4 цифры, скажем, 3344. Тогда будут заняты 10 последовательных ячеек массива от 3344 до 3353. При попытке поиска данных любого из этих 10 сотрудников будет происходить процесс линейной последовательности проб. Более того, добавление сотрудников, для которых значение хеш-функции лежит в интервале от 3345 до 3353 приведет к дальнейшему разрастанию кластера. Для быстрого поиска, конечно же, лучше иметь равномерное распределение данных в хэш-таблице, а не кластеризованное в окрестности некоторых точек.

Более сложной является квадратичная последовательность проб (quadratic probing), которая начинает проверять ячейки на квадратичном расстоянии друг от друга. То есть в случае, если ячейка s занята, то вместо проверки ячейки s + 1, а за ней s + 2 и т.д., как в линейной последовательности проб, сначала проверяется ячейка (s + 1)2, затем (s - 1)2, потом (s + 2)2, затем (s - 2)2, после этого (s + 3)2 и так далее. Однако даже квадратичный вариант может привести к образованию кластеров.

В следующем разделе мы рассмотрим третий метод разрешения коллизий, называемый повторным хешированием (rehasing). Этот метод используется классом Hashtable из .NET Framework.


 

Класс System.Collections.Hashtable

Базовая библиотека классов .NET Framework iсодержит реализацию хеш-таблицы в классе Hashtable. При добавлении элемента в Hashtable вы должны передать не только данные, но и уникальный ключ, по которому этот элемент может быть найден. Как ключ так и данные могут быть любого типа. В нашем примере с сотрудникамиключом был номер социального страхования. Элементы добавляются в Hashtable с помощью метода Add().

Чтобы извлечь элемент из Hashtable вы можете индексировать хеш-таблицу по ключу, точно так же, как вы бы индексировали элемент массива с помощью порядкового индекса. Следующая небольшая программа на C# демонстрирует как это делается. Программа добавляет в Hashtable несколько элементов, ассоциируя с каждым элементом строковый ключ. После этого доступ к конкретному элементу можно получить по его строковому ключу.

using System;
using System.Collections;
public class HashtableDemo
{
private static Hashtable ages = new Hashtable();
public static void Main()
{
// Добавим несколько значений, проиндексированных строковым ключом в хеш-таблицу
ages.Add("Scott", 25);
ages.Add("Sam", 6);
ages.Add("Jisun", 25);
// Найдем элемент по его ключу
if (ages.ContainsKey("Scott"))
{
int scottsAge = (int) ages["Scott"];
Console.WriteLine("Scott is " + scottsAge.ToString());
}
else
Console.WriteLine("Scott is not in the hash table...");
}
}

В коде также демонстрируется метод ContainsKey(), возвращающий булевское значение, говорящее нам был ли найден в хеш-таблице указанный ключ. Класс Hashtable имеет свойство Keys, возвращающее все ключи, используемые в хеш-таблице. Это свойство может быть использовано для перечисления элементов хеш-таблицы, как показано внизу:

// проход по всем элементам хеш-таблицы
foreach(string key in ages.Keys)
Console.WriteLine("Value at ages[\"" + key + "\"] = " + ages[key].ToString());

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

Value at ages["Jisun"] = 25
Value at ages["Scott"] = 25
Value at ages["Sam"] = 6

Несмотря на то, что порядок добавления элементов был "Scott," "Sam," "Jisun." Хеш-функция класса Hashtable

Хеш-функция класса Hashtable немного сложнее функции для номера социального страхования, рассмотренной выше. Во-первых, помните, что хеш-функция должна возвращать порядковое значение. Этому требованию было легко удовлетворить в примере с номером социального страхования, потому что это номер уже сам по себе является числом. Для получения хеша мы просто выбросили все цифры, кроме последних четырех. Однако, класс Hashtable позволяет ключу иметь произвольный тип. Например, ключ может быть строкой вроде "Скотт" или "Сэм", как в предыдущем примере. Возникает естественный вопрос, как хеш-функция переводит строку в число.

Это магическое преобразование осуществляется методом GetHashCode(), определенным в классе System.Object. Реализация метода GetHashCode() класса Object по умолчанию возвращает уникальное целое число, которое гарантированно не изменится за время жизни объекта. Поскольку все типы прямо наследуются от класса Object, всем объектам доступен этот метод. Поэтому строка или любой другой тип может быть представлен уникальным числом.

Определение хеш-функции класса Hashtable таково:

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1))] % hashsize

Эдесь GetHash(key) - это по умолчанию значение, возвращаемое при вызове метода GetHashCode() объекта key ( вы можете определить собственную функцию GetHash()). GetHash(key) >> 5 вычисляет хэш для key после чего выполняет побитовый сдвиг вправо на 5 бит, что равносильно делению результата хеширования на 32. Как уже обсуждалось ранее в этой статье, оператор % служит для нахождения остатка от деления одного числа на другое. hashsize - это общее число всех ячеек в хеш-таблице. (Вспомним, что x % y возвращает остаток от деления x на y и что этот остаток лежит в диапазоне от 0 до y - 1.) Благодаря операциям взятия модуля конечный результат функции H(key) всегда будет от 0 до hashsize - 1. А поскольку hashsize - это число всех ячеек в хеш-таблице, то результат, выданный хеш-функцией, будет всегда лежать в допустимых пределах.

Разрешение коллизий в классе Hashtable

Вспомним, что при вставке или удалении элемента из хеш-таблицы может возникнуть коллизия. При вставке элемента необходимо найти пустую ячейку; а при выборке элемента, его фактическое местоположение должно быть найдено, если его нет в ожидаемой позиции. Ранее мы кратко рассмотрели дваметода разрешения коллизий - линейную и квадратичную последовательность проб. Класс Hashtable использует другой метод, называемый повторным хешированием (rehasing). В некоторых источниках этот метод называют двойным хешированием (double hashing).

Повторное хеширование работает следующим образом. Пусть имеется набор хеш-функций, H1 H2 …. Hn . При вставке или извлечении элемента из хеш-таблицы изначально используется хеш-функция H1. Если в результате мы получаем коллизию, то далее пробуется функция H2 и т.д. до Hn . В предыдущем разделе я продемонстрировал лишь одну хеш-функцию-пусть она будет начальной хеш-функцией (H1). Остальный хеш-функции будут похожи на H1, отличаясь от нее лишь множителем k. Т.е. k-я хеш-функция Hk определена так:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1)))] % hashsize

Математическое примечание В случае повторного хеширования важно, чтобы каждая ячейка хеш-таблица была посещена ровно 1 раз после hashsize проб. То есть, для каждого ключа мы не хотим, чтобы функции Hi и Hj выдавали одно и то же значение хеша. В случае хеш-функций класса Hashtable это свойство выполняется, если результат вычисления (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1)) и hashsize взаимно просты. (Два числа называются взаимно простыми, если они не имеют общих делителей кроме единицы). Эти двачисла будут гарантированно взаимно просты, если hashsize - простое число.

Повторное хеширование обеспечивает лучшее избегание коллизий, чем линейная и квадратичная последовательности проб.


Уровень заполнения и расширение хеш-таблицы

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

В одной из перегруженных форм конструктора хеш-таблицы вы можете задавать значение loadFactor от 0.1 до 1.0. При этом, однако, независимо от того, какое значение этой переменной вы зададите, оно будет автоматически уменьшено до 72 процентов, так что даже если вы зададите это значение равным 1,0, то на самом деле уровень заполнения хеш-таблицы все равно будет равен 0,72. В Microsoft опытным путем установили, что 0,72 является оптимальным уровнем заполнения хеш-таблицы, так что рекомендуется использовать значение уровня заполнения по умолчанию, равное 1.0 (которое при этом автоматически устанавливается в 0,72 - да, это звучит запутанно, но что поделать).

Примечание Я потратил несколько дней, задавая вопросы в различных форумах и ребятам из Microsoft почему применяется такое автоматическое преобразование уровня заполнения. Мне было интересно, почему они решили не делать диапазон допустимых значений уровня заполнения от 0.072 до 0.72. В конце концов я добрался до той команды в Microsoft, которая работала над реализацией класса Hashtable и они поделились со мной причинами такого решения. А именно, в процессе тестирования они обнаружили, что при уровне заполнения больше 0.72 производительность резко падала. Они решили, что разработчику, который будет использовать класс Hashtable лучше не забивать себе голову таким странным числом как 0.72, вместо этого ему достаточно помнить, что уровень заполнения 1.0 дает наилучший результат. Таким образом, такое решение, немного жертвует функциональностью, зато делает структуру данных более простой в использовании и принесет меньше головных болей сообществу разработчиков.

Каждый раз при добавлении элемента в хеш-таблицу происходит проверка, не превосходит ли уровень заполнения заданного значения. Если данный факт имеет место, то хеш-таблица расширяется (is expanded). Расширение происходит в два этапа:


  1. Число ячеек хеш-таблицы приблизительно удваивается. Более точно, число ячеек увеличивается с текущего простого числа до следующего простого числа, хранящегося во внутренней таблице is (вспомним, что для надлежащей работы процесса повторного хеширования необходимо, чтобы размер хеш-таблицыбыл простым числом)
  2. Поскольку в случае повторного хеширования значение хеш-функций зависит от размера хеш-таблицы, все значения хеш-функций для элементов данных хеш-таблицы вычисляются заново (поскольку размер хеш-таблицы был изменен на первом этапе).

К счастью, класс Hashtable скрывает от разработчика всю сложность метода Add(), так что в реальности вам не придется беспокоиться обо всех этих деталях.

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

Как уже говорилось, в Microsoft настроили хеш-таблицу на использование по умолчанию уровня заполнения 0,72. Следовательно, в среднем при возникновении коллизии будет осуществляться 3.5 пробы. Поскольку эта оценка не зависит от числа ячеек хеш-таблицы, то асимптотическое время доступа хеш-таблицы равно O(1), что конечно же лучше, чем O(n) - время поиска в неотсортированном массиве.

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


 

Заключение

В этой статье мы рассмотрели три структуры данных, поддерживаемых библиотекой классов .NET Framework:


  • Очередь
  • Стек
  • Хеш-таблица

Очередь и стек по своим возможностям подобны ArrayList-у, поскольку они могут хранить произольное число объектов любого типа. Отличие очереди и стека от ArrayList-а состоит в том, что ArrayList позволяет доступаться к его элементам в произвольном порядке, в то время как и очередь, и стек накладывают ограничения на порядок доступа к своим элементам.

Очередь - это структура данных типа FIFO=First In, First Out . Т.е. порядок извлечения элементов из очереди будет таким же как и порядок их добавления в очередь. To Для этих целей очередь предоставляет два метода: Enqueue() и Dequeue(). Очереди полезны для обработки заданий или других ситуаций, когда элементы должны обрабатываться в порядке их прихода.

Модель доступа к данным стека называется LIFO=Last In, First Out. Такая схема доступа реализована в стеке с помощью методов Push() и Pop(). Стеки часто используются в различных областях computer scienceот исполнения кода до синтаксического разбора.

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

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

До следующего раза, Счастливого Программирования!

Литература

  • Кормен, Лейзерсон, Ривест. "Алгоритмы. Построение и анализ", М.: МЦНМО, 2002.
  • Headington, Mark R. and David D. Riley. "Data Abstraction and Structures Using C++." D.C. Heath and Company. 1994.
  • Дж. Рихтер Программирование на платформе Microsoft .NET Framework
  • Shared Source Common Language Infrastructure 1.0 Release (Сделана доступной в ноябре 2002 года)

Скотт Митчелл, автор пяти книг и основатель 4GuysFromRolla.com, на протяжении последних пяти лет работал с веб-технологиями Microsoft. Скотт работает независимым консультантом, преподавателем и писателем. Недавно он получил степень магистра Computer Science в Калифорнийском университете (University of California), Сан-Диего. Связаться с ним можно по адресу Адрес электронной почты защищен от спам-ботов. Для просмотра адреса в вашем браузере должен быть включен Javascript..

Перевод - Станислав Воног, Московский физико-технический институт