Приблизительная хеш-таблица, существует ли такая структура данных?

Question

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

Hashtable h = new Hashtable(); 
... 
x = h.get(y); 

Если х является результатом применения отображения ч к аргументу у, т.е. в основном в математике это была бы функция , а именно x = h (y). Теперь для приближенного матча, что о структуре данных, который дает мне быстро:

x = h(k) where k=max { z<=y | h(z)!=null } 

Проблема в том, к может быть очень далеко от заданного у. Например, y может быть 2000, а следующий занятый слот k может составлять 1000. Некоторое число линейного поиска было бы дорогостоящим, структура данных должна быстрее выполнять задание .

Я знаю, как это сделать с деревом (*), но что-то с хешем, может ли это также работать? Или, может быть, объединить некоторые свойства дерева и хэша в искомой структуре данных ? Некоторая структура данных, которая стремится к доступу O (1)?

Bye

(*) Вы можете использовать дерево, заказанный у, и найти что-то в следующем ниже или равный у.

Answer 1

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

Его можно использовать, когда hash сообщает вам что-то о логической компоновке объектов. Поэтому, когда |hash(a)-hash(b)| < |hash(a)-hash(c)| означает b is ближе/больше похожих до a than c есть.

Тогда основная идея состоит в том, что вы разделите пространство на ведра (например, сбросьте наименее значимые цифры хэша - наивный подход), а ваш пространственный хэш - это bucket ID. Вы должны заботиться о краях, когда объекты очень близки друг к другу, находясь на границе ведер (например, h(1999) = 1, но h(2000)=2). Вы можете решить эту проблему с помощью двух перекрывающихся и хешей, имеющих два отдельных хэш-карты для них, и запрашивая их обоих, или глядя на соседние ведра и т.д ...

Как я ВОФК в начале, это должно быть продумано через очень хорошо.

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

Answer 2

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

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

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

Для подхода на основе массива время выполнения будет O (log n) для извлечения и O (n) для вставки одного элемента. Если «добавить все» сортирует добавленные элементы, а затем их объединяет, это может быть O (n log n).

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

---

_{1. Конечно, доказать, что это не возможно, трудно, так как один не может легко доказать, что не существует простой повторяемый запрос постоянная времени, которая будет надежно убедить оракул (или Бога, если бы Бог так легко манипулировал), чтобы дать вам ответ на интересующий вас вопрос, но это кажется маловероятным.}