Хэш-таблица

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

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

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

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

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

Решение

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

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

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

int hashCodeOfKey(K key) {
    return key.toString( ).length() % items.length;
}

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

import java.util.ArrayList;

public class Hasher<K, V> {

	private static class LinkedListNode<K, V> {
		public LinkedListNode<K, V> next;
		public LinkedListNode<K, V> 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<LinkedListNode<K, V>> arr;
	public Hasher(int capacity) {

		arr = new ArrayList<LinkedListNode<K, V>>();
		arr.ensureCapacity(capacity);
		for (int i = 0; i < capacity; i++) {
			arr.add(null);
		}
	}
	
	
	public V put(K key, V value) {
		LinkedListNode<K, V> node = getNodeForKey(key);
		if (node != null) {
			V oldValue = node.value;
			node.value = value; 
			return oldValue;
		}
		
		node = new LinkedListNode<K, V>(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) {
		LinkedListNode<K, V> node = 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;
		LinkedListNode<K, V> node = getNodeForKey(key);
		return node == null ? null : node.value;
	}
	
	
	private LinkedListNode<K, V> getNodeForKey(K key) {
		int index = getIndexForKey(key);
		LinkedListNode<K, V> current = 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 в С++

Сопоставьте хэш-таблицу и mар из стандартной библиотеки шаблонов (STL). Как организована хэш-таблица? Какая структура данных будет оптимальной для небольших объемов данных?

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

map(STL) вставляет пары ключ/значение в дерево двоичного поиска, основанное на ключах. При этом не требуется обрабатывать коллизии, а так как дерево сбалансировано, время вставки и поиска составляет O(log N).

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

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

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

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

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

Что может заменить хэш-таблицу при работе с небольшими объемами данных?

Можно использовать mар (из STL) или бинарное дерево. Хотя это потребует O(log(n)) времени, объем данных не велик, поэтому временные затраты будут незначительными.

В чём преимущество map?

У дерева есть по крайней мере одно заметное преимущество по сравнению с хеш-таблицей. В map можно пройтись итератором по возрастанию или убыванию ключей и сделать это быстро. Хеш-таблица в этом плане проигрывает.

Разбор основан на переводе книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.

source