Зачем использовать массив для реализации «списка» вместо хеш-таблицы?

Question

Рассмотрим массив по сравнению с хеш-таблицей, где ключи являются просто интегральными индексами списка.

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

Какие еще существенные (или небольшие) контрасты я упускаю?

Контекст: иногда я вступаю в дискуссию об этом, когда беру интервью у кандидатов в программистов. Обычно контекст таков: «Как бы вы реализовали тип массива Javascript внутри виртуальной машины JS?» Для плотно упакованных данных я поддерживаю собственный массив, но я хочу иметь лучшую аргументацию, чем интуиция о том, что «это выглядит как избыточное убийство».

Answer 1

Массив - это особый случай хеш-таблицы, где хеш-функция очень проста

f(x) := x;

, а используемый модуль равен размеру слова данных (и, следовательно, размеру массива).

Если вы не разрешаете неуникальные значения, вам не нужны «следующие» указатели и вуаля, у нас есть массив.

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

Answer 2

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

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

Вставка, поиск и удаление также являются O (1) для массивов во всех случаях, но имеют гораздо более низкую постоянную O, чем хеш-таблицы (это не только из-за локальности кэша). И массивам нужно меньше места для каждой записи. Если вы хотите удалить и вставить записи таким образом, чтобы следующие записи соответствующим образом изменили свой индекс, это будет O (n), где n соответствует количеству записей, которые необходимо переместить, но это также будет O (n). для хэш-таблиц, чтобы сделать это и снова с гораздо более высокими постоянными издержками. Это та операция, для которой вам лучше использовать связанный список. Кроме того, увеличение массива обходится дешевле, чем создание хеш-таблицы, которая может потребовать перефразирования всех его записей.

У всех различных типов коллекций есть свои преимущества и недостатки. Вот почему их так много.

Answer 3

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

Answer 4

Потому что хеш-функции не являются бесплатными. Линейные факторы важны. Наихудшие времена важны. Считайте инструкции.

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