Сбер вакансии Backend
Сбер вакансии Backend
Сбер вакансии Backend
Написать пост

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

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

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

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

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

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

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

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

Решение

Предположим, вы реализуете хэш-таблицу 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 в С++.

Следите за новыми постами
Следите за новыми постами по любимым темам
17К открытий18К показов