Какова пространственная сложность хеш-таблицы?
Каков размер хеш-таблицы с 32-битным ключом и 32-битными указателями на значения, хранящиеся отдельно?
Это будет 2^32 слота * (4 байта (ключ) + 4 байта (указатели на значения)) = 4 * 10^9 * (4 + 4) = 32 ГБ?
Я пытаюсь понять сложность пространства хеш-таблиц.
4 ответа
Хеш-таблицы не соответствуют значениям хеш-функций и слотам. Хэш-функция вычисляется по модулю размера опорного вектора, который намного меньше, чем диапазон хэш-функции. Поскольку это значение является фиксированным, оно не учитывается при вычислении сложности пространства.
Следовательно, пространственная сложность каждой разумной хеш-таблицы равна O(n).
В целом, это работает довольно хорошо. Несмотря на то, что пространство клавиш может быть большим, количество сохраняемых значений обычно довольно легко предсказать. Конечно, объем памяти, который является функционально приемлемым для издержек структуры данных, обычно очевиден.
Вот почему хеш-таблицы так вездесущи. Они часто обеспечивают лучшую структуру данных для конкретной задачи, смешивая строго ограниченные накладные расходы памяти с лучшей, чем log2 n, сложностью по времени. Я люблю бинарные деревья, но они обычно не бьют хеш-таблицы.
Я думаю, что вы задаете неправильный вопрос. Пространственная сложность структуры данных указывает, сколько места она занимает по отношению к количеству элементов, которые она содержит. Например, сложность пространства O(1) будет означать, что структура данных всегда занимает постоянное пространство независимо от того, сколько элементов вы там поместите. O(n) будет означать, что потребление пространства растет линейно с количеством элементов в нем.
Хеш-таблица обычно имеет сложность пространства O(n),
Итак, чтобы ответить на ваш вопрос: это зависит от количества элементов, которые он в данный момент хранит, и в реальном мире также от фактической реализации.
Нижняя граница для потребления памяти вашей хеш-таблицы: (количество значений для хранения) * (размер значения). Таким образом, если вы хотите сохранить 1 миллион значений в хеш-таблице, и каждое из них занимает 4 байта, тогда оно будет использовать не менее 4 миллионов байтов (примерно 4 МБ). Обычно реализации реального мира используют немного больше памяти для инфраструктуры, но опять же: это сильно зависит от фактической реализации, и нет способа узнать наверняка, кроме как измерить ее.
Давайте представим, что у нас есть наивная хеш-таблица, в которой количество сегментов равно удвоенному размеру элементов. То есть O(2n) количество элементов, которое является O(n).
Когда количество элементов превышает половину количества доступных сегментов, вам необходимо создать новый массив блоков, удвоить размер и перефразировать все элементы в их новые положения в новом массиве блоков.
386 public V put(K key, V value) {
387 if (key == null)
388 return putForNullKey(value);
389 int hash = hash(key.hashCode());
390 int i = indexFor(hash, table.length);
391 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392 Object k;
393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394 V oldValue = e.value;
395 e.value = value;
396 e.recordAccess(this);
397 return oldValue;
398 }
399 }
401 modCount++;
402 addEntry(hash, key, value, i);
403 return null;
404 }
768 void addEntry(int hash, K key, V value, int bucketIndex) {
769 Entry<K,V> e = table[bucketIndex];
770 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
771 if (size++ >= threshold)
772 resize(2 * table.length);
773 }
471 void resize(int newCapacity) {
472 Entry[] oldTable = table;
473 int oldCapacity = oldTable.length;
474 if (oldCapacity == MAXIMUM_CAPACITY) {
475 threshold = Integer.MAX_VALUE;
476 return;
477 }
479 Entry[] newTable = new Entry[newCapacity];
480 transfer(newTable);
481 table = newTable;
482 threshold = (int)(newCapacity * loadFactor);
483 }
488 void transfer(Entry[] newTable) {
489 Entry[] src = table;
490 int newCapacity = newTable.length;
491 for (int j = 0; j < src.length; j++) {
492 Entry<K,V> e = src[j];
493 if (e != null) {
494 src[j] = null;
495 do {
496 Entry<K,V> next = e.next;
497 int i = indexFor(e.hash, newCapacity);
498 e.next = newTable[i];
499 newTable[i] = e;
500 e = next;
501 } while (e != null);
502 }
503 }
504 }
Рекомендации:
Тем не менее, нет идеального ответа на вопрос. Я не уверен насчет занимаемой площади. Согласно моему пониманию вопроса. Размер является динамическим и зависит от размера ввода.
То есть мы начинаем со случайного числа, размера хеш-таблицы, которое очень мало по сравнению со значением хеш-функции. Затем мы вставляем ввод. Теперь, когда начинается столкновение, мы динамически удваиваем размер хеш-таблицы. Это причина, я думаю, для сложности O(n). Пожалуйста, поправьте меня, если я ошибаюсь.