Какова пространственная сложность хеш-таблицы?

Question

Каков размер хеш-таблицы с 32-битным ключом и 32-битными указателями на значения, хранящиеся отдельно?

Это будет 2 ^ 32 слота * (4 байта (ключ) + 4 байта (указатели на значения)) = 4 * 10 ^ 9 * (4 + 4) = 32 ГБ?

Я пытаюсь понять сложность пространства хеш-таблиц.

Answer 1

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

Хеш-таблица обычно имеет сложность пространства O(n).

Итак, чтобы ответить на ваш вопрос: это зависит от количества элементов, которые он хранит в настоящий момент, и в реальном мире также от фактической реализации.

Нижняя граница для потребления памяти вашей хеш-таблицы: (Количество значений для хранения) * (Размер значения). Таким образом, если вы хотите сохранить 1 миллион значений в хеш-таблице, и каждое из них занимает 4 байта, тогда оно будет использовать не менее 4 миллионов байтов (примерно 4 МБ). Обычно реализации реального мира используют немного больше памяти для инфраструктуры, но опять же: это сильно зависит от фактической реализации, и нет способа узнать наверняка, кроме как измерить ее.

Answer 2

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

Следовательно, пространственная сложность каждой разумной хэш-таблицы равна O (n).

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

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

Answer 3

Давайте представим, что у нас есть наивная хеш-таблица, в которой количество сегментов равно удвоенному размеру элементов. То есть 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  }

Ссылки:

HashMap.put
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.put%28java.lang.Object%2Cjava.lang.Object%29

Answer 4

Тем не менее, нет идеального ответа на вопрос.Я не уверен насчет занимаемого пространства.Согласно моему пониманию вопроса.Размер является динамическим и зависит от размера ввода.

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