Является ли таблица поиска формой хэш-таблицы?
Я пытаюсь понять, правильно ли я здесь концептуально. ,
Если я пытаюсь избежать необходимости вычислять вычислительно дорого someExpensiveFun(x) для каждого элемента в массиве данных с плавающей запятой xСкажем, ограниченный значениями от нуля до единицы, можно предварительно рассчитать вывод дорогой функции и сохранить ее в таблице. , ,
for (int nn = 0; nn < 1000; ++nn)
{
float tmp = ((float)nn) / 1000.f;
lookup[nn] = someExpensiveFun(tmp);
}
Тогда в основной части критичного к производительности кода я могу использовать. , ,
y = lookup[(int)floor(x*1000.f)];
Является ли концептуально правильным (а не злоупотреблением терминологией) называть lookup форма хэш-таблицы и x*1000 связанная функция хеширования?
Решение
Лично я бы сказал, что это злоупотребление терминологией. В нем отсутствуют свойства, которые люди естественно ожидают от хеш-таблицы, в частности, возможность что-то делать с неравными ключами с равными хешами. И я уверен, что ваша «хэш-функция» должна рассматриваться как floor(x*1000.f) или же (int)floor(x*1000.f), не просто x*1000.f,
Хеш-таблицы также обычно могут принимать в качестве ключа любое значение их типа ключа, а не только значения в диапазоне, но, возможно, я слишком разборчив в этом. Я бы не назвал обычную хеш-таблицу, которая не позволяла бы NaN в качестве ключа «не хеш-таблица».
Он имеет некоторые общие свойства с хеш-таблицами (неинъективная функция, которая отображает ключи на целые числа, причем указанные целые числа используются в качестве индекса в массиве). Если кто-то хочет решить, что эти две вещи вместе характеризуют «хеш-таблицу», хорошо, удачи им, это хеш-таблица 🙂
Другие решения
Нет, концептуально не правильно называть таблицу поиска хеш-таблицей: в вашем случае таблица поиска — это простой массив. Вызов чего-либо из хеш-таблицы подразумевает определенное поведение в случаях, когда хеш-функция не является совершенной (т.е. при наличии коллизий хеш-функции); Массивы не имеют такого поведения, поэтому, называя это «поиском по хешу», вы, вероятно, введете в заблуждение ваших слушателей или читателей.
В общем, для выполнения операций поиска можно использовать любой тип ассоциативного хранилища, включая хеш-таблицы, различные деревья и т. Д. В вашем случае индекс массива связан со значением, хранящимся в этом индексе, что позволяет вам искать значение в постоянном времени.
У тебя это задом наперед. Хеш-таблица всегда может использоваться в качестве медленной замены массива, но массив не может использоваться в качестве замены хеш-таблицы (если не выполнены некоторые очень строгие предварительные условия).
В вашем случае поиск даже не дает те же результаты, что и вычисления, только близкое приближение. Истинная хеш-таблица будет отличать разные входы, которые хэшируются с одним и тем же индексом.
Да, если вы принимаете определение Википедии хеш-таблица. Цитируя это определение:
Ideally, the hash function should map each possible key to a unique slot index,
but this ideal is rarely achievable in practice (unless the hash keys are fixed;
i.e. new entries are never added to the table after it is created).
Вы выбрали массив, потому что область вашей функции является хорошо определенным и относительно небольшим и может быть индексом массива — домен функции имеет на отображение на индекс массива. Вы можете думать об индексе как key к hash table и выходная функция является ассоциированным значением.
Вы можете заменить все таблицы поиска на хеш-таблицы, но вы не можете заменить все таблицы хешей на таблицы поиска. Так что да, справочную таблицу можно рассматривать как особую форму хеш-таблицы, а хеш-таблицу можно рассматривать как общую форму справочной таблицы.
Аналогичным образом, список можно рассматривать как особую форму 2D-таблицы (с одним столбцом).
Тем не менее, мы говорим о программном обеспечении здесь. Существует множество разных решений для данной проблемы и множество разных возможностей для построения ваших структур данных. Например, со статическим размером или динамическим ростом, с необходимыми уникальными записями или с обработкой коллизий, с фиксированной или настраиваемой хэш-функцией и т. Д. Существует много способов между простой таблицей поиска и полной хэш-таблицей без четкая граница, где вы могли бы сказать вот это, но там это стало тем.
Однако (опять же), когда конкретная структура данных оказывается полезной, она обычно получает свое собственное имя. Как уже было сказано, с таким названием связаны ожидания относительно функциональности. Может даже быть строгое определение о требуемой минимальной функциональности. Если вы хотите, чтобы ваш код читался другими, лучше придерживайтесь известных терминов. Таким образом, вы должны называть вашу справочную таблицу справочной таблицей, хотя технически это особая форма хеш-таблицы.