Создание хеш таблицы c
В хеш-таблице обработка новых индексов производится при помощи ключей. А элементы, связанные с этим ключом, сохраняются в индексе. Этот процесс называется хешированием.
Пусть k — ключ, а h(x) — хеш-функция.
Тогда h(k) в результате даст индекс, в котором мы будем хранить элемент, связанный с k .
Конструкторы
Инициализирует новый пустой экземпляр класса Hashtable с заданными по умолчанию начальной емкостью, показателем загрузки, поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает заданными по умолчанию показателем загрузки, поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает заданным по умолчанию показателем загрузки и указанным объектом сравнения IEqualityComparer.
Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает заданным по умолчанию показателем загрузки и указанными поставщиком хэш-кода и объектом сравнения. Этот API устарел. См. Hashtable(IDictionary, IEqualityComparer) для альтернативных шагов.
Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает указанным показателем загрузки и заданными по умолчанию поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает указанными показателем загрузки и объектом сравнения IEqualityComparer.
Инициализирует новый пустой экземпляр класса Hashtable посредством копирования элементов из указанного словаря в новый объект Hashtable. У нового объекта Hashtable исходная емкость равна числу копируемых элементов, и он обладает указанными показателем загрузки, поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable с заданными по умолчанию исходной емкостью и показателем загрузки и указанным объектом сравнения IEqualityComparer.
Инициализирует новый пустой экземпляр класса Hashtable с заданными по умолчанию исходной емкостью и показателем загрузки и указанными поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable с указанной исходной емкостью и заданными по умолчанию показателем загрузки, поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью и объектом сравнения IEqualityComparer и заданным по умолчанию показателем загрузки.
Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью, поставщиком хэш-кода и объектом сравнения и заданным по умолчанию показателем загрузки.
Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью и показателем загрузки и заданными по умолчанию поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable с указанными исходной емкостью, показателем загрузки и объектом сравнения IEqualityComparer.
Инициализирует новый пустой экземпляр класса Hashtable с указанными начальной емкостью, показателем загрузки, поставщиком хэш-кода и объектом сравнения.
Инициализирует новый пустой экземпляр класса Hashtable, который может быть сериализован с помощью объектов SerializationInfo и StreamingContext.
Решения проблемы коллизии методом двойного хеширования
Мы будем (как несложно догадаться из названия) использовать две хеш-функции, возвращающие взаимопростые натуральные числа.
Одна хеш-функция (при входе g) будет возвращать натуральное число s, которое будет для нас начальным. То есть первое, что мы сделаем, попробуем поставить элемент g на позицию s в нашем массиве. Но что, если это место уже занято? Именно здесь нам пригодится вторая хеш-функция, которая будет возвращать t — шаг, с которым мы будем в дальнейшем искать место, куда бы поставить элемент g.
Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).
Наконец мы объяснили все самые важные моменты, можно перейти к непосредственному написанию кода, где уже можно будет рассмотреть все оставшиеся нюансы. Ну а строгое математическое доказательство корректности использования двойного хеширования можно найти тут.
Для наглядности будем реализовывать хеш-таблицу, хранящую строки.
Начнем с определения самих хеш-функций, реализуем их методом Горнера. Важным параметром корректности хеш-функции является то, что возвращаемое значение должно быть взаимопросто с размером таблицы. Для уменьшения дублирования кода, будем использовать две структуры, ссылающиеся на реализацию самой хеш-функции.
Чтобы идти дальше, нам необходимо разобраться с проблемой: что же будет, если мы удалим элемент из таблицы? Так вот, его нужно пометить флагом deleted, но просто удалять его безвозвратно нельзя. Ведь если мы так сделаем, то при попытке найти элемент (значение хеш-функции которого совпадет с ее значением у нашего удаленного элемента) мы сразу наткнемся на пустую ячейку. А это значит, что такого элемента и не было никогда, хотя, он лежит, просто где-то дальше в массиве. Это основная сложность использования данного метода решения коллизий.
Помня о данной проблеме построим наш класс.
На данном этапе мы уже более-менее поняли, что у нас будет храниться в таблице. Переходим к реализации служебных методов.
Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.
Увеличиваем размер мы стандартно вдвое.
Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).
Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.
Но к чему слова, код все разъяснит:
Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.
Начнем с самого простого — метод Find элемент по значению.
Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.
Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.
Помимо этого в данном методе есть еще одна часть, поддерживающая правильную асимптотику. Это запоминание первого подходящего для вставки элемента (даже если он deleted). Именно туда мы вставим элемент, если в нашей хеш-таблицы нет такого же. Если ни одного deleted-элемента на нашем пути нет, мы создаем новый Node с нашим вставляемым значением.
Some information relates to prerelease product that may be substantially modified before it’s released. Microsoft makes no warranties, express or implied, with respect to the information provided here.
Represents a collection of key/value pairs that are organized based on the hash code of the key.
Заключение
Так как хэширование устраняет необходимость в дорогостоящих поиске данных для извлечения данных, для эффективного извлечения данных можно использовать хэширование. Хэширование использует значение самого ключа для поиска данных.
Библиотеки базовых классов HashTable System.Collections предлагают класс, определенный в пространстве имен, чтобы вам не нужно было создавать собственные хэш-таблицы.
Examples
The following example shows how to create, initialize and perform various functions to a Hashtable and how to print out its keys and values.
Methods
Adds an element with the specified key and value into the Hashtable.
Removes all elements from the Hashtable.
Creates a shallow copy of the Hashtable.
Determines whether the Hashtable contains a specific key.
Determines whether the Hashtable contains a specific key.
Determines whether the Hashtable contains a specific value.
Copies the Hashtable elements to a one-dimensional Array instance at the specified index.
Determines whether the specified object is equal to the current object.
Returns an IDictionaryEnumerator that iterates through the Hashtable.
Returns the hash code for the specified key.
Serves as the default hash function.
Implements the ISerializable interface and returns the data needed to serialize the Hashtable.
Gets the Type of the current instance.
Compares a specific Object with a specific key in the Hashtable.
Creates a shallow copy of the current Object.
Implements the ISerializable interface and raises the deserialization event when the deserialization is complete.
Removes the element with the specified key from the Hashtable.
Returns a synchronized (thread-safe) wrapper for the Hashtable.
Returns a string that represents the current object.
Применяется к
Коллизии
Когда хеш-функция генерирует один индекс для нескольких ключей, возникает конфликт: неизвестно, какое значение нужно сохранить в этом индексе. Это называется коллизией хеш-таблицы.
Есть несколько методов борьбы с коллизиями:
- метод цепочек;
- метод открытой адресации: линейное и квадратичное зондирование.
1. Метод цепочек
Суть этого метода проста: если хеш-функция выделяет один индекс сразу двум элементам, то храниться они будут в одном и том же индексе, но уже с помощью двусвязного списка.
Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .
Комментарии
Каждый элемент представляет собой пару "ключ-значение", хранящуюся в объекте DictionaryEntry . Ключ не может быть null , но значение может быть.
Мы не рекомендуем использовать Hashtable класс для новой разработки. Вместо этого рекомендуется использовать универсальный Dictionary класс. Дополнительные сведения см. в статье, не относящийся к универсальным коллекциям, не следует использовать в GitHub.
Объекты, используемые в качестве ключей, Hashtable необходимы для переопределения Object.GetHashCode метода (или IHashCodeProvider интерфейса) и Object.Equals метода (или IComparer интерфейса). Реализация обоих методов и интерфейсов должна обрабатывать чувствительность регистра одинаково; Hashtable в противном случае поведение может быть неправильно. Например, при создании Hashtableкласса необходимо использовать CaseInsensitiveHashCodeProvider класс (или любую реализацию без учета регистра IHashCodeProvider ) с классом CaseInsensitiveComparer (или любой реализацией без учета IComparer регистра).
Кроме того, эти методы должны получать те же результаты при вызове с теми же параметрами, когда ключ существует в Hashtable. Альтернативой является использование конструктора Hashtable с параметром IEqualityComparer . Если бы ключевое равенство было просто эталонным равенством, унаследованная реализация Object.GetHashCode и Object.Equals будет достаточной.
Ключевые объекты должны быть неизменяемыми, если они используются в качестве ключей в .Hashtable
Когда элемент добавляется в Hashtableконтейнер, он помещается в контейнер на основе хэш-кода ключа. Последующие поиски ключа используют хэш-код ключа для поиска только в одном конкретном контейнере, что значительно сокращает количество сравнений ключей, необходимых для поиска элемента.
Коэффициент нагрузки Hashtable определяет максимальное соотношение элементов к контейнерам. Меньшие факторы нагрузки приводят к ускорению среднего времени поиска за счет увеличения потребления памяти. Коэффициент нагрузки по умолчанию 1.0 обычно обеспечивает оптимальный баланс между скоростью и размером. При создании также можно указать другой коэффициент нагрузки Hashtable .
По мере добавления элементов в Hashtableобъект фактический коэффициент нагрузки Hashtable увеличивается. Когда фактический коэффициент нагрузки достигает указанного коэффициента нагрузки, число контейнеров автоматически Hashtable увеличивается до наименьшего простого числа, которое больше, чем в два раза больше текущего Hashtable числа контейнеров.
Каждый объект ключа в объекте Hashtable должен предоставлять собственную хэш-функцию, доступ к которой можно получить путем вызова GetHash. Однако любой объект, реализующий объект IHashCodeProvider , можно передать конструктору Hashtable , и эта хэш-функция используется для всех объектов в таблице.
Емкость объекта Hashtable — это количество элементов, которые могут содержаться Hashtable . По мере добавления элементов в Hashtableобъект емкость автоматически увеличивается при необходимости при перемещении.
Оператор foreach является оболочкой вокруг перечислителя, который позволяет только считывать из коллекции, а не записывать в нее.
Так как сериализация и десериализация перечислителя для элемента Hashtable может привести к переупорядочению элементов, невозможно продолжить перечисление без вызова Reset метода.
Поскольку ключи могут наследоваться и их поведение изменено, их абсолютная уникальность не может быть гарантирована сравнением с помощью Equals метода.
Методы
Добавляет элемент с указанными ключом и значением в словарь Hashtable.
Удаляет из коллекции Hashtable все элементы.
Создает неполную копию Hashtable.
Определяет, содержит ли объект Hashtable указанный ключ.
Определяет, содержит ли объект Hashtable указанный ключ.
Определяет, содержит ли коллекция Hashtable указанное значение.
Копирует элементы коллекции Hashtable в экземпляр класса одномерного массива Array по указанному индексу.
Определяет, равен ли указанный объект текущему объекту.
Возвращает объект IDictionaryEnumerator, осуществляющий перебор Hashtable.
Возвращает хэш-код указанного ключа.
Служит хэш-функцией по умолчанию.
Реализует интерфейс ISerializable и возвращает данные, необходимые для сериализации коллекции Hashtable.
Возвращает объект Type для текущего экземпляра.
Сравнивает указанный объект класса Object с указанным ключом, который содержится в коллекции Hashtable.
Создает неполную копию текущего объекта Object.
Реализует интерфейс ISerializable и вызывает событие десериализации при завершении десериализации.
Удаляет элемент с указанным ключом из Hashtable.
Возвращает синхронизированную (потокобезопасную) оболочку коллекции Hashtable.
Возвращает строку, представляющую текущий объект.
Псевдокод операций
2. Открытая адресация
В отличие от метода цепочек, в открытой адресации несколько элементов в одной ячейке храниться не могут. Суть этого метода заключается в том, что каждая ячейка либо содержит единственный ключ, либо NIL .
Существует несколько видов открытой адресации:
a) Линейное зондирование
Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки.
h(k, i) = (h′(k) + i) mod m ,
Если коллизия происходит в h(k, 0) , тогда проверяется h(k, 1) . То есть значение i увеличивается линейно.
Проблема линейного зондирования заключается в том, что заполняется кластер соседних ячеек. Это приводит к тому, что при вставке нового элемента в хеш-таблицу необходимо проводить полный обход кластера. В результате время выполнения операций с хеш-таблицами увеличивается.
b) Квадратичное зондирование
Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению:
- c1 и c2 — положительные вспомогательные константы,
- i =
c) Двойное хэширование
Если коллизия возникает после применения хеш-функции h(k) , то для поиска следующей ячейки вычисляется другая хеш-функция.
h(k, i) = (h1(k) + ih2(k)) mod m
Constructors
Initializes a new, empty instance of the Hashtable class using the default initial capacity, load factor, hash code provider, and comparer.
Initializes a new instance of the Hashtable class by copying the elements from the specified dictionary to the new Hashtable object. The new Hashtable object has an initial capacity equal to the number of elements copied, and uses the default load factor, hash code provider, and comparer.
Initializes a new instance of the Hashtable class by copying the elements from the specified dictionary to a new Hashtable object. The new Hashtable object has an initial capacity equal to the number of elements copied, and uses the default load factor and the specified IEqualityComparer object.
Initializes a new instance of the Hashtable class by copying the elements from the specified dictionary to the new Hashtable object. The new Hashtable object has an initial capacity equal to the number of elements copied, and uses the default load factor, and the specified hash code provider and comparer. This API is obsolete. For an alternative, see Hashtable(IDictionary, IEqualityComparer).
Initializes a new instance of the Hashtable class by copying the elements from the specified dictionary to the new Hashtable object. The new Hashtable object has an initial capacity equal to the number of elements copied, and uses the specified load factor, and the default hash code provider and comparer.
Initializes a new instance of the Hashtable class by copying the elements from the specified dictionary to the new Hashtable object. The new Hashtable object has an initial capacity equal to the number of elements copied, and uses the specified load factor and IEqualityComparer object.
Initializes a new instance of the Hashtable class by copying the elements from the specified dictionary to the new Hashtable object. The new Hashtable object has an initial capacity equal to the number of elements copied, and uses the specified load factor, hash code provider, and comparer.
Initializes a new, empty instance of the Hashtable class using the default initial capacity and load factor, and the specified IEqualityComparer object.
Initializes a new, empty instance of the Hashtable class using the default initial capacity and load factor, and the specified hash code provider and comparer.
Initializes a new, empty instance of the Hashtable class using the specified initial capacity, and the default load factor, hash code provider, and comparer.
Initializes a new, empty instance of the Hashtable class using the specified initial capacity and IEqualityComparer, and the default load factor.
Initializes a new, empty instance of the Hashtable class using the specified initial capacity, hash code provider, comparer, and the default load factor.
Initializes a new, empty instance of the Hashtable class using the specified initial capacity and load factor, and the default hash code provider and comparer.
Initializes a new, empty instance of the Hashtable class using the specified initial capacity, load factor, and IEqualityComparer object.
Initializes a new, empty instance of the Hashtable class using the specified initial capacity, load factor, hash code provider, and comparer.
Initializes a new, empty instance of the Hashtable class that is serializable using the specified SerializationInfo and StreamingContext objects.
«Хорошие» хеш-функции
«Хорошие» хеш-функции не уберегут вас от коллизий, но, по крайней мере, сократят их количество.
Ниже мы рассмотрим различные методы определения «качества» хэш-функций.
1. Метод деления
Если k — ключ, а m — размер хеш-таблицы, то хеш-функция h() вычисляется следующим образом:
Например, если m = 10 и k = 112 , то h(k) = 112 mod 10 = 2 . То есть значение m не должно быть степенью 2. Это связано с тем, что степени двойки в двоичном формате — 10, 100, 1000… При вычислении k mod m мы всегда будем получать p-биты низшего порядка.
2. Метод умножения
- kA mod 1 отделяет дробную часть kA;
- ⌊ ⌋ округляет значение;
- A — произвольная константа, значение которой должно находиться между 0 и 1. Оптимальный вариант ≈ (√5-1) / 2, его предложил Дональд Кнут.
3. Универсальное хеширование
В универсальном хешировании хеш-функция выбирается случайным образом и не зависит от ключей.
Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.
Представляет коллекцию пар «ключ-значение», которые упорядочены по хэш-коду ключа.
Проблема коллизии
Естественно, возникает вопрос, почему невозможно такое, что мы попадем дважды в одну ячейку массива, ведь представить функцию, которая ставит в сравнение каждому элементу совершенно различные натуральные числа просто невозможно. Именно так возникает проблема коллизии, или проблемы, когда хеш-функция выдает одинаковое натуральное число для разных элементов.
Существует несколько решений данной проблемы: метод цепочек и метод двойного хеширования. В данной статье я постараюсь рассказать о втором методе, как о более красивом и, возможно, более сложном.
Thread Safety
Hashtable is thread safe for use by multiple reader threads and a single writing thread. It is thread safe for multi-thread use when only one of the threads perform write (update) operations, which allows for lock-free reads provided that the writers are serialized to the Hashtable. To support multiple writers all operations on the Hashtable must be done through the wrapper returned by the Synchronized(Hashtable) method, provided that there are no threads reading the Hashtable object.
Enumerating through a collection is intrinsically not a thread safe procedure. Even when a collection is synchronized, other threads can still modify the collection, which causes the enumerator to throw an exception. To guarantee thread safety during enumeration, you can either lock the collection during the entire enumeration or catch the exceptions resulting from changes made by other threads.
Remarks
Each element is a key/value pair stored in a DictionaryEntry object. A key cannot be null , but a value can be.
We don't recommend that you use the Hashtable class for new development. Instead, we recommend that you use the generic Dictionary class. For more information, see Non-generic collections shouldn't be used on GitHub.
The objects used as keys by a Hashtable are required to override the Object.GetHashCode method (or the IHashCodeProvider interface) and the Object.Equals method (or the IComparer interface). The implementation of both methods and interfaces must handle case sensitivity the same way; otherwise, the Hashtable might behave incorrectly. For example, when creating a Hashtable, you must use the CaseInsensitiveHashCodeProvider class (or any case-insensitive IHashCodeProvider implementation) with the CaseInsensitiveComparer class (or any case-insensitive IComparer implementation).
Furthermore, these methods must produce the same results when called with the same parameters while the key exists in the Hashtable. An alternative is to use a Hashtable constructor with an IEqualityComparer parameter. If key equality were simply reference equality, the inherited implementation of Object.GetHashCode and Object.Equals would suffice.
Key objects must be immutable as long as they are used as keys in the Hashtable.
When an element is added to the Hashtable, the element is placed into a bucket based on the hash code of the key. Subsequent lookups of the key use the hash code of the key to search in only one particular bucket, thus substantially reducing the number of key comparisons required to find an element.
The load factor of a Hashtable determines the maximum ratio of elements to buckets. Smaller load factors cause faster average lookup times at the cost of increased memory consumption. The default load factor of 1.0 generally provides the best balance between speed and size. A different load factor can also be specified when the Hashtable is created.
As elements are added to a Hashtable, the actual load factor of the Hashtable increases. When the actual load factor reaches the specified load factor, the number of buckets in the Hashtable is automatically increased to the smallest prime number that is larger than twice the current number of Hashtable buckets.
Each key object in the Hashtable must provide its own hash function, which can be accessed by calling GetHash. However, any object implementing IHashCodeProvider can be passed to a Hashtable constructor, and that hash function is used for all objects in the table.
The capacity of a Hashtable is the number of elements the Hashtable can hold. As elements are added to a Hashtable, the capacity is automatically increased as required through reallocation.
The foreach statement is a wrapper around the enumerator, which only allows reading from, not writing to, the collection.
Because serializing and deserializing an enumerator for a Hashtable can cause the elements to become reordered, it is not possible to continue enumeration without calling the Reset method.
Because keys can be inherited and their behavior changed, their absolute uniqueness cannot be guaranteed by comparisons using the Equals method.
Методы расширения
Приводит элементы объекта IEnumerable к заданному типу.
Выполняет фильтрацию элементов объекта IEnumerable по заданному типу.
Позволяет осуществлять параллельный запрос.
Преобразовывает коллекцию IEnumerable в объект IQueryable.
Properties
Gets or sets the IComparer to use for the Hashtable.
Gets the number of key/value pairs contained in the Hashtable.
Gets or sets the object that can dispense hash codes.
Gets a value indicating whether the Hashtable has a fixed size.
Gets a value indicating whether the Hashtable is read-only.
Gets a value indicating whether access to the Hashtable is synchronized (thread safe).
Gets or sets the value associated with the specified key.
Gets an ICollection containing the keys in the Hashtable.
Gets an object that can be used to synchronize access to the Hashtable.
Gets an ICollection containing the values in the Hashtable.
Понятие хеш-таблицы
Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.
Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.
Теперь стало понятно, почему же это именно хеш-таблица.
Потокобезопасность
Hashtable является потокобезопасной для использования несколькими потоками чтения и одним потоком записи. Потокобезопасно для использования нескольких потоков, если только один из потоков выполняет операции записи (обновления), что позволяет выполнять операции записи без блокировки при условии, что записи сериализуются в Hashtable. Чтобы обеспечить поддержку нескольких операций записи, Hashtable необходимо выполнить через оболочку, возвращаемую методом Synchronized(Hashtable) , при условии, что потоки не считывают Hashtable объект.
Перечисление через коллекцию по сути не является потокобезопасной процедурой. Даже если коллекция синхронизирована, другие потоки могут ее изменить, что приведет к тому, что перечислитель создаст исключение. Для обеспечения потокобезопасности при перечислении можно либо заблокировать коллекцию на все время перечисления, либо перехватывать исключения, возникающие в результате изменений, внесенных другими потоками.
Мотивация использовать хеш-таблицы
Для наглядности рассмотрим стандартные контейнеры и асимптотику их наиболее часто используемых методов.
Контейнер \ операция | 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) |
Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях
Из этой таблицы очень хорошо понятно, почему же стоит использовать хеш-таблицы. Но тогда возникает противоположный вопрос: почему же тогда ими не пользуются постоянно?
Ответ очень прост: как и всегда, невозможно получить все сразу, а именно: и скорость, и память. Хеш-таблицы тяжеловесные, и, хоть они и быстро отвечают на вопросы основных операций, пользоваться ими все время очень затратно.
Applies to
Примеры
В следующем примере показано, как создавать, инициализировать и выполнять различные функции в ключи Hashtable и значения.
Действия по сборке примера
Коллекция HashTable хранит пару ( Key , Value ) и использует ее Key для хэширования и получения расположения хранилища. Является Key неизменяемым и не может иметь повторяющиеся записи в HashTable . В этом примере используется несколько экземпляров простого Person класса для хранения в HashTable . Фамилия используется в качестве Key .
В Обозреватель решений щелкните правой кнопкой мыши имя проекта, наведите указатель на пункт "Добавить ", а затем выберите "Класс", чтобы добавить модуль класса. Class1 по умолчанию добавляется в проект.
Замените любой код в модуле Class1 следующим кодом:
Класс Person имеет один конструктор, который принимает параметры FirstName LastName и присваивает эти параметры локальным переменным. Функция ToString переопределяет ToString класс Object для возврата Fname Lname и объединения.
Создайте объект уровня формы Hashtable и объявите три переменные типа Person . Добавьте в класс Form1 следующий код.
Поместите элемент управления "Кнопка" в form1 и измените свойство Text на "Добавить элементы".
Дважды щелкните кнопку, чтобы открыть окно кода, и вставьте следующий код в событие Button1_Click :
Объект Hashtable предоставляет индексатор. На следующих шагах индексируйте, чтобы Key получить доступ к значению, которое хранится в хэшированном расположении:
Добавьте элемент управления Button в Form1 и измените свойство Name на "Получить элементы".
Дважды щелкните кнопку и вставьте следующий код Button2_Click в событие:
На следующих шагах используйте метод Remove для удаления одного элемента из HashTable коллекции:
Добавьте элемент управления Button в Form1 и измените свойство Text на "Удалить элемент".
Дважды щелкните кнопку и вставьте следующий код Button3_Click в событие:
На следующих шагах перечислите элементы, хранящиеся в коллекции HashTable :
Добавьте элемент управления Button в Form1 и измените свойство Text на "Перечисление".
Дважды щелкните кнопку и вставьте следующий код Button4_Click в событие:
Этот код объявляет переменную типа и IDictionaryEnumerator GetEnumerator вызывает метод коллекции HashTable . При возврате Enumerator код Keys HashTable перечисляет элементы в коллекции и использует метод перечисления ключей.
На следующих шагах используйте метод Clear для очистки: HashTable
Добавьте элемент управления "Кнопка" в Form1 и измените свойство Text на "Очистить".
Дважды щелкните кнопку и вставьте следующий код Button5_Click в событие:
Выполните следующие действия, чтобы создать и запустить приложение:
- Выберите "Добавить элементы". В Person коллекцию добавляются три HashTable объекта.
- Выберите "Получить элементы". Индексатор получает элементы в коллекции HashTable . Отображаются три добавленных элемента.
- Выберите "Удалить элемент". Элемент в расположении Burris ключа удаляется.
- Выберите "Перечисление". IDictionaryEnumerator перечисляет элементы в HashTable коллекции, Keys HashTable а свойство возвращает коллекцию ключей.
- Выберите "Очистить". Все элементы очищаются из HashTable коллекции.
Примеры компаний, организаций, продуктов, доменных имен, адресов электронной почты, логотипов, людей, мест и событий, описанных здесь, являются вымышленной. Никакие связи с реальной компанией, организацией, продуктом, доменным именем, адресом электронной почты, логотипом, человеком, местами или событиями не предназначены или должны быть выведены.
Я много раз заглядывал на просторы интернета, нашел много интересных статей о хеш-таблицах, но вразумительного и полного описания того, как они реализованы, так и не нашел. В связи с этим мне просто нетерпелось написать пост на данную, столь интересную, тему.
Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.
Explicit Interface Implementations
Returns an enumerator that iterates through a collection.
Свойства
Получает или задает интерфейс IComparer для использования применительно к коллекции Hashtable.
Возвращает число пар "ключ-значение", содержащихся в словаре Hashtable.
Получает объект IEqualityComparer, предназначенный для использования применительно к коллекции Hashtable.
Получает или задает объект, который может распределять хэш-коды.
Получает значение, указывающее, имеет ли список Hashtable фиксированный размер.
Получает значение, указывающее, является ли объект Hashtable доступным только для чтения.
Возвращает значение, показывающее, является ли доступ к коллекции Hashtable синхронизированным (потокобезопасным).
Возвращает или задает значение, связанное с указанным ключом.
Получает коллекцию ICollection, содержащую ключи из коллекции Hashtable.
Получает объект, с помощью которого можно синхронизировать доступ к коллекции Hashtable.
Возвращает интерфейс ICollection, содержащий значения из Hashtable.
Extension Methods
Casts the elements of an IEnumerable to the specified type.
Filters the elements of an IEnumerable based on a specified type.
Enables parallelization of a query.
Явные реализации интерфейса
Возвращает перечислитель, который осуществляет итерацию по коллекции.
Коллизии
Когда хеш-функция генерирует один индекс для нескольких ключей, возникает конфликт: неизвестно, какое значение нужно сохранить в этом индексе. Это называется коллизией хеш-таблицы.
Есть несколько методов борьбы с коллизиями:
- метод цепочек;
- метод открытой адресации: линейное и квадратичное зондирование.
1. Метод цепочек
Суть этого метода проста: если хеш-функция выделяет один индекс сразу двум элементам, то храниться они будут в одном и том же индексе, но уже с помощью двусвязного списка.
Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL .
Читайте также: