Борьба с коллизиями (они же столкновения)

Борьба с коллизиями (они же столкновения)

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

Но в большинстве случаев приходится бороться с коллизиями. Обычно применяются методы цепочек и открытой индексации.

Метод цепочек

Этот метод часто называют открытым хешированием. Его суть проста — элементы с одинаковым хешем попадают в одну ячейку в виде свя́зного спи́ска если ячейка с хешем уже занята, но новый ключ отличается от уже имеющегося, то новый элемент вставляется в список в виде пары ключ-значение. (Связный список - базовая динамическая структура данных в программировании, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка; принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями).

Сравним ранее рассмотренные нами динамические структуры по организации трех операций: добавлению элемента в структуру, удалению и поиску.

Контейнер \ операция	insert	remove	find
Array	O(N)	O(N)	O(N)
List	O(1)	O(1)	O(N)
Sorted array	O(N)	O(N)	O(logN)
Бинарное дерево поиска	O(logN)	O(logN)	O(logN)
Хеш-таблица	O(1)	O(1)	O(1)

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

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

В классе Hashtable реализуются интерфейсы IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback и ICloneable. В классе Hashtable определено немало конструкторов. Ниже приведены наиболее часто используемые конструкторы этого класса:

public Hashtable()

public Hashtable(IDictionary d)

public Hashtable(int capacity)

public Hashtable(int capacity, float loadFactor)

В первой форме создается создаваемый по умолчанию объект класса Hashtable. Во второй форме создаваемый объект типа Hashtable инициализируется элементами из коллекции d. В третьей форме создаваемый объект типа Hashtable инициализируется, учитывая емкость коллекции, задаваемую параметром capacity. И в четвертой форме создаваемый объект типа Hashtable инициализируется, учитывая заданную емкость capacity и коэффициент заполнения loadFactor. Коэффициент заполнения, иногда еще называемый коэффициентом загрузки, должен находиться в пределах от 0.1 до 1.0. Он определяет степень заполнения хеш-таблицы до увеличения ее размера. В частности, таблица расширяется, если количество элементов оказывается больше емкости таблицы, умноженной на коэффициент заполнения. В тех конструкторах, которые не принимают коэффициент заполнения в качестве параметра, этот коэффициент по умолчанию выбирается равным 1.0.

В классе Hashtable определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто используемых методов этого класса приведены ниже. В частности, для того чтобы определить, содержится ли ключ в коллекции типа Hashtable, вызывается метод ContainsKey(). А для того чтобы выяснить, хранится ли в такой коллекции конкретное значение, вызывается метод ContainsValue(). Для перечисления содержимого коллекции типа Hashtable служит метод GetEnumerator(), возвращающий объект типа IDictionaryEnumerator. Напомним, что IDictionaryEnumerator — это перечислитель, используемый для перечисления содержимого коллекции, в которой хранятся пары "ключ-значение".

ContainsKey()

Возвращает логическое значение true, если в вызывающей коллекции типа Hashtable содержится ключ, а иначе — логическое значение false

ContainsValue()

Возвращает логическое значение true, если в вызывающей коллекции типа Hashtable содержится значение, а иначе — логическое значение false

GetEnumerator()

Возвращает для вызывающей коллекции типа Hashtable перечислитель типа IDictionaryEnumerator

Synchronized()

Возвращает синхронизированный вариант коллекции типа Hashtable, передаваемой в качестве параметра

В классе Hashtable доступны также открытые свойства, определенные в тех интерфейсах, которые в нем реализуются. Особая роль принадлежит двум свойствам, Keys и Values, поскольку с их помощью можно получить ключи или значения из коллекции типа Hashtable. Эти свойства определяются в интерфейсе IDictionary следующим образом:

public virtual ICollection Keys { get; }

public virtual ICollection Values { get; }

В классе Hashtable не поддерживаются упорядоченные коллекции, и поэтому ключи или значения получаются из коллекции в произвольном порядке. Кроме того, в классе Hashtable имеется защищенное свойство EqualityComparer. А два других свойства, hep и comparer, считаются устаревшими.

Давайте расмотрим пример:

using System;

using System.Collections;

namespace ConsoleApplication1

{ class Program

{ static void Main()

{ // Создаем хеш-таблицу

Hashtable ht = new Hashtable();

// Добавим несколько записей

ht.Add("domainname1", "mail");

ht.Add("domainname2", "gmail");

ht.Add("domainname3", "hotmail");

// Считаем коллекцию ключей

ICollection keys = ht.Keys;

foreach (string s in keys)

Console.WriteLine(s + ": " + ht[s]);

Console.ReadLine();

} } }

⇐ Предыдущая 123 4 Следующая ⇒