Лучшая структура данных для этой проблемы?

Question

Я использую Java для этой программы, и в настоящее время у меня возникает ситуация, когда я хочу добавить пары ключ / значение в таблицу с целочисленными ключами, например

add (1, "Bobby")
add (6, "Sue")
add (3, "Mary")
add (8, "John")
add (15, "Joe")

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

Так, например,если я посмотрю 7, он должен вернуть «Сью», но если я посмотрю 9, он должен вернуть «Джон»

Я надеюсь использовать один из классов утилит Java (HashTable, TreeMap и т. д.), ноЯ не совсем уверен, как это сделать.

Answer 1

NavigableMap сделает свое дело.

Answer 2

TreeMap из библиотеки коллекций обеспечивает необходимую функциональность

TreeMap<Integer,String> tree = new TreeMap<Integer,String>();
tree.put (1, "Bobby");
tree.put(6, "Sue");
tree.put (3, "Mary");
tree.put (8, "John");
tree.put (15, "Joe");
System.out.println(tree.floorEntry(7)); // Sue
System.out.println(tree.floorEntry(9)); // John

Answer 3

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

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

Answer 4

Если вы хотите сделать это с помощью sql, то подойдет что-то вроде:

select top 1 * from hashTable where keyColumnId >= @passedValueId

.