Что такое hash таблица java
Перейти к содержимому

Что такое hash таблица java

  • автор:

Хэш-таблицы. Что это такое и как работают

Мы продолжаем курс по структурам данных, и на этом занятии речь пойдет о новой структуре под названием хэш-таблица. Она обладает поистине впечатляющими характеристиками. Для стандартных операций вставки, чтения и удаления данных она, в среднем, выполняется за константное время O(1), то есть, быстро и не зависимо от размера таблицы (объема данных):

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

Предположим, в продуктовом магазине необходимо хранить товары и выдавать цену по их названиям.

Как это сделать? Из того, что мы знаем на данный момент, вполне подошел бы связный список, т.к. в него достаточно быстро можно добавлять новые товары и удалять ненужные. Правда, поиск будет выполняться линейное время O(n). И это нас не очень устраивает, т.к. товаров в магазине может быть очень много и нам бы хотелось иметь более быстрый доступ к цене товара по его названию. Поэтому сделаем несколько иначе. Единственная из всех рассмотренных структур, которая предоставляет быстрый доступ к элементу за время O(1) – это массивы (и динамические массивы).

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

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

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

Добавление элементов в хэш-таблицу

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

Ключ Значение
a а
b б
c с
d д
f ф

Причем нам наперед неизвестно, сколько именно букв будет храниться в хэш-таблице. Поэтому, чтобы зря не расходовать память, начальный размер таблицы будет иметь m=5 элементов. Сами ячейки таблицы будут хранить адреса на объекты с данными. Если данных нет, то указатели принимают значение NULL. Далее, у нас имеется хэш-функция, которая для каждой буквы латинского алфавита вычисляет индекс в массиве T. Предположим, мы хотим по ключу b записать значение б. На вход хэш-функции подается символ b. На выходе получаем индекс массива, по которому этот ключ должен располагаться в таблице. Пусть это будет индекс 1: Затем, в памяти создается новый объект с ключом b и значенем б, и адрес этого объекта сохраняется во втором элементе таблицы. То есть, массив хранит не сами данные, а ссылки на объекты с данными. Это наиболее частая реализация хэш-таблиц. В результате мы добавили новый ключ b и его значение б в хэш-таблицу. На уровне языков программирования эта операция часто записывается в виде:

T["b"] = "б"

Разумеется, если T – это хэш-таблица. По аналогии можно добавить еще несколько ключей и значений. Например, ключи f, d, u: И наш массив почти заполнен! В теории хэш-таблиц степень их заполненности определяется коэффициентом: α = n / m где n – количество хранимых ключей (в нашем примере 4); m – размер массива (в нашем примере 5). Получаем, значение степени заполнения таблицы: α = 4 / 5 = 0,8 То есть, пока этот коэффициент меньше единицы, в массиве есть свободные элементы, куда теоретически еще можно добавить новые ключи. Если α = 1, то массив заполнен полностью. Если же α > 1, то число ключей превышает размер хэш-таблицы. (Как такое может быть, мы еще будем говорить.) Итак, на данный момент коэффициент α = 0,8, значит, массив почти заполнен. Что делать дальше? Выход только один: увеличить размер таблицы, то есть, рассматривать массив как динамический и, например, при α близкой к 1 увеличивать его размер в 2 раза. Давайте так и сделаем. Сначала мы должны в памяти создать новый массив длиной в 2 раза больше предыдущего. После этого хэш-функция будет уже выдавать новый диапазон индексов [0; 9]. Поэтому элементы должны не просто копироваться в новый массив, а заново прогоняться через новую хэш-функцию. Получим (как пример): Только после этого мы сюда можем добавлять новые ключи. Вот общий принцип работы алгоритма добавления ключей и значений в хэш-таблицы. В среднем, эта операция выполняется за фиксированное время O(1).

Разрешение коллизий в хэш-таблицах

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

  • метод цепочек;
  • метод открытой адресации.

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

T["b"] = б T["ba"] = ба T["d"] = д T["f"] = ф T["bb"] = бб T["fa"] = фа

И хэш-функция для ключей с одинаковыми первыми буквами выдает одни и те же индексы таблицы. Тогда, чтобы сохранить несколько разных ключей по одному и тому же индексу, формируется двусвязный список, на начало которого ведет указатель ptr. В элементах этого двусвязного списка сохраняются пары ключ-значение. Это и есть принцип разрешения коллизий по методу цепочек. У такого решения есть положительные и отрицательные стороны. К положительным можно отнести простоту реализации. Сформировать двусвязные списки там, где необходимо хранить несколько ключей, не составляет особого труда. Также относительно быстро происходит вставка новых ключей и удаление существующих в таких списках (цепочках). А основным недостатком является возможность появления длинных цепочек в хэш-таблицах. Тогда поиск нужного ключа может занять продолжительное время и преимущества хэш-таблиц будут сведены к нулю. Очевидно, чтобы избежать такого неблагоприятного случая (образования длинных цепочек), нужно правильно выбирать хэш-функцию, которая бы равномерно распределяла возможные ключи по индексам таблицы. Благо, существуют подходы, позволяющие создавать такие функции, но об этом мы еще будем говорить. А сейчас посмотрим, как в хэш-таблицах со списками выполняется поиск и удаление ключей.

Алгоритм поиска ключей

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

val = T["ba"]

Для этого мы подаем ключ «ba» на вход хэш-функции, получаем значение индекса 1 в таблице и видим здесь двусвязный список. На начало этого списка ведет указатель ptr. Сформируем временный указатель:

p = ptr

который также будет ссылаться на начало этого списка. Далее, мы последовательно проходим по элементам этого списка и сравниваем в них ключи на равенство заданного ключа «ba». Этот ключ мы находим во втором элементе списка. На этом поиск останавливается и возвращается значение «ба» этого ключа. Если мы указываем не существующий ключ, например, «t», то либо попадем в пустую ячейку таблицы, либо не найдем этот ключ в списке. Вот так, достаточно просто реализуется алгоритм поиска ключей в хэш-таблице с цепочками.

Алгоритм удаления ключей

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

del T["ba"]

Вначале также подаем этот ключ на вход хэш-функции и получаем индекс 1 в таблице. По этому индексу хранится несколько ключей в двусвязном списке. С помощью временного указателя p находим элемент с ключом «ba». Это второй элемент. И удаляем его. (Как удалять элементы в двухсвязных списках мы с вами уже говорили на предыдущих занятиях). Все, ключ удален из хэш-таблицы. Если происходит удаление единственного ключа в ячейке, например, ключа «d», то проверяется, что в единственном элементе действительно хранится ключ «d», если так, то объект удаляется и ячейка принимает значение NULL. Наконец, если пытаемся удалить не существующий в таблице ключ, например, «s», то либо сразу попадаем в ячейку со значением NULL, либо на цепочку из ключей, в которой ключ «s» будет отсутствовать. В любом случае, при отсутствии ключа никаких действий с таблицей не выполняется и она остается в неизменном виде.

Задача: спроектируйте и реализуйте хэш-таблицу

Хэш-таблица — это структура данных. Она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Спроектируйте и реализуйте хэш-таблицу, использующую связные списки для обработки коллизий.

Обложка поста Задача: спроектируйте и реализуйте хэш-таблицу

Что такое хэш-таблица?

Хэш-таблица — это структура данных. Она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

О других структурах данных вы можете прочитать в нашем разделе.

Условие задачи

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

Решение

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

class Hash  < Linkedlist [] items; public void put (K key, V value ) < . >public V get (K key) < . >> 

items — массив связных списков, а items[i] — связный список всех объектов с клю­чами, которым сопоставляется индекс i (все коллизии для индекса i ). Вроде бы все работает… пока мы не задумаемся о коллизиях. Допустим, у нас очень простая хэш-функция, которая использует длину строки:

int hashCodeOfKey(K key)

Ключи jim и bob будут соответствовать одному индексу массива, хотя это разные ключи (с одинаковой длиной строки). Нам нужно произвести поиск по связному списку, чтобы найти правильные объекты, соответствующие ключам. Но как это сделать? Ведь в связном списке хранится значение, а не исходный ключ. Одно из возможных решений — создание другого объекта (Cell), связывающего ключи со значениями. В этой реализации наш связный список будет иметь тип Cell. Следующий код использует эту реализацию:

import java.util.ArrayList; public class Hasher  < /* Класс узла связного списка . Используется только в хэш-таблице, * реализуется в виде двусвязного списка . */ private static class LinkedListNode < public LinkedListNodenext; public LinkedListNode prev; public K key; public V value; public LinkedListNode(K k, V v) < key = k; value = v; >public String printForward() < String data = "(" + key + "," + value + ")"; if (next != null) < return data + "->" + next.printForward(); > else < return data; >> > private ArrayList arr; public Hasher(int capacity) < /* Создание списка связных списков . Список заполняется значениями * пull (единственный способ создания массива заданного размера ). */ arr = new ArrayList(); arr.ensureCapacity(capacity); for (int i = 0; i < capacity; i++) < arr.add(null); >> /* Вставка ключа и значения в хэш-таблицу . */ public V put(K key, V value) < LinkedListNodenode = getNodeForKey(key); if (node != null) < V oldValue = node.value; node.value = value; // Просто обновить значение. return oldValue; >node = new LinkedListNode(key, value); int index = getIndexForKey(key); if (arr.get(index) != null) < node.next = arr.get(index); node.next.prev = node; >arr.set(index, node); return null; > /* Удаление узла для ключа . */ public V remove(K key) < LinkedListNodenode = getNodeForKey(key); if (node == null) < return null; >if (node.prev != null) < node.prev.next = node.next; >else < /* Удаление начального узла - обновление. */ int hashKey = getIndexForKey(key); arr.set(hashKey, node.next); >if (node.next != null) < node.next.prev = node.prev; >return node.value; > /* Получение значения для ключа . */ public V get(K key) < if (key == null) return null; LinkedListNodenode = getNodeForKey(key); return node == null ? null : node.value; > /* Получение узла связного списка для заданного ключа . */ private LinkedListNode getNodeForKey(K key) < int index = getIndexForKey(key); LinkedListNodecurrent = arr.get(index); while (current != null) < if (current.key == key) < return current; >current = current.next; > return null; > /* Очень наивная функция для связывания ключа с индексом . */ public int getIndexForKey(K key) < return Math.abs(key.hashCode() % arr.size()); >public void printTable() < for (int i = 0; i < arr.size(); i++) < String s = arr.get(i) == null ? "" : arr.get(i).printForward(); System.out.println(i + ": " + s); >> > 

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

Если вас заинтересовала данная тема, то вы можете прочитать интересный материал о сопоставлении хэш-таблиц и map в С++.

30.6. Java – Класс Hashtable

Класс Hashtable в Java был частью оригинального java.util и представляет собой конкретную реализацию Dictionary.

Однако, Java 2 переработал Hashtable, чтобы он также реализовал интерфейс Map. Таким образом, Hashtable теперь интегрирован в структуру коллекций. Он схож с HashMap, но синхронизован.

Как и HashMap, в Java Hashtable хранит пары ключей/значений в хэш-таблице. Используя Hashtable, вы указываете объект, который используется как ключ, и значение, которое вы ходите связать с этим ключом. Этот ключ затем хэшируется, а полученный хэш-код используется как индекс, в котором значение хранится в таблице.

Конструкторы

Вот список конструкторов, предоставляемые классом HashTable.

Конструктор и описание
1 Hashtable()
Этот стандартный конструктор хэщ-таблицы, который создаёт экземпляр класса Hashtable.
2 Hashtable(int size)
Этот конструктор принимает целочисленный параметр и создаёт хэш-таблицу, имеющая начальный размер, заданный размером целочисленного значения.
3 Hashtable(int size, float fillRatio)
Это создаёт хэш-таблицу, в которой есть начальный размер, указанный в size, и коэффициент заполнения, заданный fillRatio. Этот коэффициент должен принимать значение между 0.0 и 1.0, и он определяет, насколько полной может быть хэш-таблица прежде чем она будет изменена в размерах.
4 Hashtable(Map t)
Это построит Hashtable с указанными отображениями.

Методы

Помимо методов, определённых интерфейсом Map, Hashtable определяет следующие методы:

Метод и описание
1 void clear()
Сбрасывает и очищает хэш-таблицу.
2 Object clone()
Возвращает дубликат вызываемого объекта.
3 boolean contains(Object value)
Возвращает true, если некое значение равняется значению, существующему в хэш-таблице. Возвращает false, если значение не было найдено.
4 boolean containsKey(Object key)
Возвращает true, если некий ключ равняется ключу, существующему в хэш-таблице. Возвращает false, если ключ не был найден.
5 boolean containsValue(Object value)
Возвращает true, если некое значение равняется значению, существующему в хэш-таблице. Возвращает false если значение не было найдено.
6 Enumeration elements()
Возвращает перечисление значений, содержащихся в хэш-таблице.
7 Object get(Object key)
Возвращает объект, содержащий значение, связанное с ключом. Если ключ не находится в хэш-таблицы, возвращается нулевой объект.
8 boolean isEmpty()
Возвращает true, если хэш-таблица пустая; возвращает false, если она содержит хотя бы один ключ.
9 Enumeration keys()
Возвращает перечисление ключей, содержащихся в хэш-таблице.
10 Object put(Object key, Object value)
Вставляет ключ и значение в хэш-таблицу. Возвращает ноль, если ключ ещё не в хэш-таблице, возвращает предыдущее значение, связанное с ключом, если ключ уже в хэш-таблице.
11 void rehash()
Увеличивает размер хэш-таблицы и переопределяет все её ключи.
12 Object remove(Object key)
Удаляет ключ и его значение. Возвращает значение, связанное с ключом. Если ключ отсутствует в хэш-таблице, возвращается нулевой объект.
13 int size()
Возвращает количество записей в хэш-таблице.
14 String toString()
Возвращает строковый эквивалент хэш-таблицы.

Пример

Следующая программа показывает несколько методов, поддерживаемых структурой данных Hashtable в Java:

import java.util.*; public class HashTableDemo < public static void main(String args[]) < // Создаёт хэш-карту Hashtable balance = new Hashtable(); Enumeration names; String str; double bal; balance.put("Маша", new Double(3434.34)); balance.put("Михаил", new Double(123.22)); balance.put("Олег", new Double(1378.00)); balance.put("Денис", new Double(99.22)); balance.put("Антон", new Double(-19.08)); // Показывает все балансы в хэш-таблицы. names = balance.keys(); while(names.hasMoreElements()) < str = (String) names.nextElement(); System.out.println(str + ": " + balance.get(str)); >System.out.println(); // Вносим 1,000 в аккаунт Маши. bal = ((Double)balance.get("Маша")).doubleValue(); balance.put("Маша", new Double(bal + 1000)); System.out.println("Новый баланс Маши: " + balance.get("Маша")); > > 
Антон: -19.08 Маша: 3434.34 Михаил: 123.22 Денис: 99.22 Олег: 1378.0 Новый баланс Маши: 4434.34 

Оглавление

  • 1. Java – Самоучитель для начинающих
  • 2. Java – Обзор языка
  • 3. Java – Установка и настройка
  • 4. Java – Синтаксис
  • 5. Java – Классы и объекты
  • 6. Java – Конструкторы
  • 7. Java – Типы данных и литералы
  • 8. Java – Типы переменных
  • 9. Java – Модификаторы
  • 10. Java – Операторы
  • 11. Java – Циклы и операторы цикла
  • 11.1. Java – Цикл while
  • 11.2. Java – Цикл for
  • 11.3. Java – Улучшенный цикл for
  • 11.4. Java – Цикл do..while
  • 11.5. Java – Оператор break
  • 11.6. Java – Оператор continue
  • 12. Java – Операторы принятия решений
  • 12.1. Java – Оператор if
  • 12.2. Java – Оператор if..else
  • 12.3. Java – Вложенный оператор if
  • 12.4. Java – Оператор switch..case
  • 12.5. Java – Условный оператор (? 🙂
  • 13. Java – Числа
  • 13.1. Java – Методы byteValue(), shortValue(), intValue(), longValue(), floatValue(), doubleValue()
  • 13.2. Java – Метод compareTo()
  • 13.3. Java – Метод equals()
  • 13.4. Java – Метод valueOf()
  • 13.5. Java – Метод toString()
  • 13.6. Java – Метод parseInt()
  • 13.7. Java – Метод Math.abs()
  • 13.8. Java – Метод Math.ceil()
  • 13.9. Java – Метод Math.floor()
  • 13.10. Java – Метод Math.rint()
  • 13.11. Java – Метод Math.round()
  • 13.12. Java – Метод Math.min()
  • 13.13. Java – Метод Math.max()
  • 13.14. Java – Метод Math.exp()
  • 13.15. Java – Метод Math.log()
  • 13.16. Java – Метод Math.pow()
  • 13.17. Java – Метод Math.sqrt()
  • 13.18. Java – Метод Math.sin()
  • 13.19. Java – Метод Math.cos()
  • 13.20. Java – Метод Math.tan()
  • 13.21. Java – Метод Math.asin()
  • 13.22. Java – Метод Math.acos()
  • 13.23. Java – Метод Math.atan()
  • 13.24. Java – Метод Math.atan2()
  • 13.25. Java – Метод Math.toDegrees()
  • 13.26. Java – Метод Math.toRadians()
  • 13.27. Java – Метод Math.random()
  • 14. Java – Символы
  • 14.1. Java – Метод Character.isLetter()
  • 14.2. Java – Метод Character.isDigit()
  • 14.3. Java – Метод Character.isWhitespace()
  • 14.4. Java – Метод Character.isUpperCase()
  • 14.5. Java – Метод Character.isLowerCase()
  • 14.6. Java – Метод Character.toUpperCase()
  • 14.7. Java – Метод Character.toLowerCase()
  • 14.8. Java – Метод Character.toString()
  • 15. Java – Строки
  • 15.1. Java – Метод charAt()
  • 15.2. Java – Метод compareTo()
  • 15.3. Java – Метод compareToIgnoreCase()
  • 15.4. Java – Метод concat()
  • 15.5. Java – Метод contentEquals()
  • 15.6. Java – Метод copyValueOf()
  • 15.7. Java – Метод endsWith()
  • 15.8. Java – Метод equals()
  • 15.9. Java – Метод equalsIgnoreCase()
  • 15.10. Java – Метод getBytes()
  • 15.11. Java – Метод getChars()
  • 15.12. Java – Метод hashCode()
  • 15.13. Java – Метод indexOf()
  • 15.14. Java – Метод intern()
  • 15.15. Java – Метод lastIndexOf()
  • 15.16. Java – Метод length()
  • 15.17. Java – Метод matches()
  • 15.18. Java – Метод regionMatches()
  • 15.19. Java – Метод replace()
  • 15.20. Java – Метод replaceAll()
  • 15.21. Java – Метод replaceFirst()
  • 15.22. Java – Метод split()
  • 15.23. Java – Метод startsWith()
  • 15.24. Java – Метод subSequence()
  • 15.25. Java – Метод substring()
  • 15.26. Java – Метод toCharArray()
  • 15.27. Java – Метод toLowerCase()
  • 15.28. Java – Метод toString()
  • 15.29. Java – Метод toUpperCase()
  • 15.30. Java – Метод trim()
  • 15.31. Java – Метод valueOf()
  • 15.32. Java – Классы StringBuilder и StringBuffer
  • 15.32.1. Java – Метод append()
  • 15.32.2. Java – Метод reverse()
  • 15.32.3. Java – Метод delete()
  • 15.32.4. Java – Метод insert()
  • 15.32.5. Java – Метод replace()
  • 16. Java – Массивы
  • 17. Java – Дата и время
  • 18. Java – Регулярные выражения
  • 19. Java – Методы
  • 20. Java – Потоки ввода/вывода, файлы и каталоги
  • 20.1. Java – Класс ByteArrayInputStream
  • 20.2. Java – Класс DataInputStream
  • 20.3. Java – Класс ByteArrayOutputStream
  • 20.4. Java – Класс DataOutputStream
  • 20.5. Java – Класс File
  • 20.6. Java – Класс FileReader
  • 20.7. Java – Класс FileWriter
  • 21. Java – Исключения
  • 21.1. Java – Встроенные исключения
  • 22. Java – Вложенные и внутренние классы
  • 23. Java – Наследование
  • 24. Java – Переопределение
  • 25. Java – Полиморфизм
  • 26. Java – Абстракция
  • 27. Java – Инкапсуляция
  • 28. Java – Интерфейсы
  • 29. Java – Пакеты
  • 30. Java – Структуры данных
  • 30.1. Java – Интерфейс Enumeration
  • 30.2. Java – Класс BitSet
  • 30.3. Java – Класс Vector
  • 30.4. Java – Класс Stack
  • 30.5. Java – Класс Dictionary
  • 30.6. Java – Класс Hashtable
  • 30.7. Java – Класс Properties
  • 31. Java – Коллекции
  • 31.1. Java – Интерфейс Collection
  • 31.2. Java – Интерфейс List
  • 31.3. Java – Интерфейс Set
  • 31.4. Java – Интерфейс SortedSet
  • 31.5. Java – Интерфейс Map
  • 31.6. Java – Интерфейс Map.Entry
  • 31.7. Java – Интерфейс SortedMap
  • 31.8. Java – Класс LinkedList
  • 31.9. Java – Класс ArrayList
  • 31.10. Java – Класс HashSet
  • 31.11. Java – Класс LinkedHashSet
  • 31.12. Java – Класс TreeSet
  • 31.13. Java – Класс HashMap
  • 31.14. Java – Класс TreeMap
  • 31.15. Java – Класс WeakHashMap
  • 31.16. Java – Класс LinkedHashMap
  • 31.17. Java – Класс IdentityHashMap
  • 31.18. Java – Алгоритмы Collection
  • 31.19. Java – Iterator и ListIterator
  • 31.20. Java – Comparator
  • 32. Java – Дженерики
  • 33. Java – Сериализация
  • 34. Java – Сеть
  • 34.1. Java – Обработка URL
  • 35. Java – Отправка Email
  • 36. Java – Многопоточность
  • 36.1. Java – Синхронизация потоков
  • 36.2. Java – Межпоточная связь
  • 36.3. Java – Взаимная блокировка потоков
  • 36.4. Java – Управление потоками
  • 37. Java – Основы работы с апплетами
  • 38. Java – Javadoc

Хеш-таблицы

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

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

image

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

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

Контейнер \ операция 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)

Все данные при условии хорошо выполненных контейнерах, хорошо подобранных хеш-функциях

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

Понятие хеш-таблицы

Хеш-таблица — это контейнер, который используют, если хотят быстро выполнять операции вставки/удаления/нахождения. В языке C++ хеш-таблицы скрываются под флагом unoredered_set и unordered_map. В Python вы можете использовать стандартную коллекцию set — это тоже хеш-таблица.
Реализация у нее, возможно, и не очевидная, но довольно простая, а главное — как же круто использовать хеш-таблицы, а для этого лучше научиться, как они устроены.

Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.

Теперь стало понятно, почему же это именно хеш-таблица.

Проблема коллизии

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

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

Решения проблемы коллизии методом двойного хеширования

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

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

Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).

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

Реализация хеш-таблицы

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

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

int HashFunctionHorner(const std::string& s, int table_size, const int key) < int hash_result = 0; for (int i = 0; s[i] != s.size(); ++i) hash_result = (key * hash_result + s[i]) % table_size; hash_result = (hash_result * 2 + 1) % table_size; return hash_result; >struct HashFunction1 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size - 1); // ключи должны быть взаимопросты, используем числа плюс и минус один. > >; struct HashFunction2 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size + 1); >>;

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

Помня о данной проблеме построим наш класс.

template class HashTable < static const int default_size = 8; // начальный размер нашей таблицы constexpr static const double rehash_size = 0.75; // коэффициент, при котором произойдет увеличение таблицы struct Node < T value; bool state; // если значение флага state = false, значит элемент массива был удален (deleted) Node(const T& value_) : value(value_), state(true) <>>; Node** arr; // соответственно в массиве будут хранится структуры Node* int size; // сколько элементов у нас сейчас в массиве (без учета deleted) int buffer_size; // размер самого массива, сколько памяти выделено под хранение нашей таблицы int size_all_non_nullptr; // сколько элементов у нас сейчас в массиве (с учетом deleted) >;

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

. public: HashTable() < buffer_size = default_size; size = 0; size_all_non_nullptr = 0; arr = new Node*[buffer_size]; for (int i = 0; i < buffer_size; ++i) arr[i] = nullptr; // заполняем nullptr - то есть если значение отсутствует, и никто раньше по этому адресу не обращался >~HashTable()

Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

Увеличиваем размер мы стандартно вдвое.

void Resize() < int past_buffer_size = buffer_size; buffer_size *= 2; size_all_non_nullptr = 0; size = 0; Node** arr2 = new Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < past_buffer_size; ++i) < if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); // добавляем элементы в новый массив > // удаление предыдущего массива for (int i = 0; i

Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).

Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.

Но к чему слова, код все разъяснит:

void Rehash() < size_all_non_nullptr = 0; size = 0; Node** arr2 = new Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < buffer_size; ++i) < if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); > // удаление предыдущего массива for (int i = 0; i

Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

Начнем с самого простого — метод Find элемент по значению.

bool Find(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2()) < int h1 = hash1(value, buffer_size); // значение, отвечающее за начальную позицию int h2 = hash2(value, buffer_size); // значение, ответственное за "шаг" по таблице int i = 0; while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) return true; // такой элемент есть h1 = (h1 + h2) % buffer_size; ++i; // если у нас i >= buffer_size, значит мы уже обошли абсолютно все ячейки, именно для этого мы считаем i, иначе мы могли бы зациклиться. > return false; >

Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.

bool Remove(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2()) < int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) < arr[h1]->state = false; --size; return true; > h1 = (h1 + h2) % buffer_size; ++i; > return false; >

Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.

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

bool Add(const T& value, const THash1& hash1 = THash1(),const THash2& hash2 = THash2()) < if (size + 1 >int(rehash_size * buffer_size)) Resize(); else if (size_all_non_nullptr > 2 * size) Rehash(); // происходит рехеш, так как слишком много deleted-элементов int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; int first_deleted = -1; // запоминаем первый подходящий (удаленный) элемент while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) return false; // такой элемент уже есть, а значит его нельзя вставлять повторно if (!arr[h1]->state && first_deleted == -1) // находим место для нового элемента first_deleted = h1; h1 = (h1 + h2) % buffer_size; ++i; > if (first_deleted == -1) // если не нашлось подходящего места, создаем новый Node < arr[h1] = new Node(value); ++size_all_non_nullptr; // так как мы заполнили один пробел, не забываем записать, что это место теперь занято >else < arr[first_deleted]->value = value; arr[first_deleted]->state = true; > ++size; // и в любом случае мы увеличили количество элементов return true; >

В заключение приведу полную реализацию хеш-таблицы.

int HashFunctionHorner(const std::string& s, int table_size, const int key) < int hash_result = 0; for (int i = 0; s[i] != s.size(); ++i) < hash_result = (key * hash_result + s[i]) % table_size; >hash_result = (hash_result * 2 + 1) % table_size; return hash_result; > struct HashFunction1 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size - 1); >>; struct HashFunction2 < int operator()(const std::string& s, int table_size) const < return HashFunctionHorner(s, table_size, table_size + 1); >>; template class HashTable < static const int default_size = 8; constexpr static const double rehash_size = 0.75; struct Node < T value; bool state; Node(const T& value_) : value(value_), state(true) <>>; Node** arr; int size; int buffer_size; int size_all_non_nullptr; void Resize() < int past_buffer_size = buffer_size; buffer_size *= 2; size_all_non_nullptr = 0; size = 0; Node** arr2 = new Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < past_buffer_size; ++i) < if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); > for (int i = 0; i < past_buffer_size; ++i) if (arr2[i]) delete arr2[i]; delete[] arr2; >void Rehash() < size_all_non_nullptr = 0; size = 0; Node** arr2 = new Node * [buffer_size]; for (int i = 0; i < buffer_size; ++i) arr2[i] = nullptr; std::swap(arr, arr2); for (int i = 0; i < buffer_size; ++i) < if (arr2[i] && arr2[i]->state) Add(arr2[i]->value); > for (int i = 0; i < buffer_size; ++i) if (arr2[i]) delete arr2[i]; delete[] arr2; >public: HashTable() < buffer_size = default_size; size = 0; size_all_non_nullptr = 0; arr = new Node*[buffer_size]; for (int i = 0; i < buffer_size; ++i) arr[i] = nullptr; >~HashTable() < for (int i = 0; i < buffer_size; ++i) if (arr[i]) delete arr[i]; delete[] arr; >bool Add(const T& value, const THash1& hash1 = THash1(),const THash2& hash2 = THash2()) < if (size + 1 >int(rehash_size * buffer_size)) Resize(); else if (size_all_non_nullptr > 2 * size) Rehash(); int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; int first_deleted = -1; while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) return false; if (!arr[h1]->state && first_deleted == -1) first_deleted = h1; h1 = (h1 + h2) % buffer_size; ++i; > if (first_deleted == -1) < arr[h1] = new Node(value); ++size_all_non_nullptr; >else < arr[first_deleted]->value = value; arr[first_deleted]->state = true; > ++size; return true; > bool Remove(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2()) < int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) < arr[h1]->state = false; --size; return true; > h1 = (h1 + h2) % buffer_size; ++i; > return false; > bool Find(const T& value, const THash1& hash1 = THash1(), const THash2& hash2 = THash2()) < int h1 = hash1(value, buffer_size); int h2 = hash2(value, buffer_size); int i = 0; while (arr[h1] != nullptr && i < buffer_size) < if (arr[h1]->value == value && arr[h1]->state) return true; h1 = (h1 + h2) % buffer_size; ++i; > return false; > >;

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *