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

Хэш-таблица

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

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

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

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

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

Решение

Предположим, вы реализуете хэш-таблицу 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) {
/* Создание списка связных списков . Список заполняется значениями
* пull (единственный способ создания массива заданного размера ). */
		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 в С++.

Источник: Карьера программиста

Ещё интересное для вас:
Тест: чьё это рабочее место? Угадываем айтишников по их столам
Тест: что вы знаете о работе мозга?
Тест: какой язык программирования вам стоит выбрать для изучения?