这个问题的最佳数据结构？

Question

我在这个程序中使用Java，目前我想将键/值对添加到带有整数键的表中，就像所以

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

很自然地我想做一些类似哈希表的事情，但是当我进行查找时，如果它找不到确切的值，我希望它返回不大于请求的键的最近的键。

例如，如果我查找 7，它应该返回“Sue”，但如果我查找 9，它应该返回“John”

我希望使用 java util 类之一（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

如果你想使用 sql 来做到这一点，类似：

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

会起作用。

Answer 4

好吧，如果您主要从结构中读取数据并且很少插入数据，那么您可以使用简单的排序数组并进行二分搜索。如果您担心搜索性能，那就再简单不过了。现在，如果您定期更新结构，那就不太好了 - 那么您将不得不使用更复杂的东西。

我还认为 - 但不完全确定 - 二叉树不会同样有效吗？搜索正确节点应该所在的位置，如果未找到该值，则使用其前任节点。