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

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

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

我还认为——但不完全确定——二叉树是否也能正常工作？搜索正确节点应该在的位置，如果未找到该值，则使用其前任。