Основы хеш-таблиц?

Question

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

В принципе, если кто-то ответит на этот вопрос, я думаю, что на все мои вопросы ответят: Если бы у меня было 100 случайно сгенерированных чисел (в виде ключей), как бы я реализовал хеш-таблицу и почему это было бы выгодно по сравнению с массивом?

Psuedo-код или Java были бы оценены как инструмент обучения ...

Answer 1

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

Массив - это просто упорядоченный список объектов. Сам объект на самом деле не имеет значения ... важно то, что если вы хотите перечислить объекты в порядке вставки, это всегда то же самое (это означает, что первый элемент всегда имеет индекс 0 ).

Что касается хеш-таблицы, которая индексируется по ключам, а не по порядку ... Я думаю, что базовый поиск по алгоритмам хеширования даст вам гораздо больше понимания, чем я ... Википедия имеет очень приличную ... определяет «корзину», в которую попадают ключи для быстрого поиска произвольных объектов, используемых в качестве ключей.

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