哈希表 - 获取索引之前的第一个元素

Question

我有这个哈希table :

private final Hashtable<Integer,Character> htable = new Hashtable<>();

我正在 table 中存储一些元素，其索引可能达到高范围。 然后当我想获取一个项目时，如果它不存在，我想先获取第一个现有的。

一个天真的方法可以是：

int index = given_index;
while(htable.get(index) == null && index >= 0)
    index --;

这样做可能会计算出大量的值。 有没有更好的策略，或者可能是另一种 table 允许计算更少？

Answer 1

NavigableMap（如 user15358848 评论中所述）

参考：NavigableMap

一般来说，实现不应该支持 null 值。如果有支持 null 的实现，将无法检查响应 null 是由于缺失还是实际值。

较低条目

Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.

1. get 键的值
2. 如果获取的值为null，则获取lowerEntry
如果存在实际密钥，
3. getOrDefault(key, navigableMap.lowerEntry(index)) 将是昂贵的，主要是由于额外的 navigableMap.lowerEntry 调用

  Character value = navigableMap.get(index);
  if (value == null) {
    value = navigableMap.lowerEntry(index);
  }
  return value;

楼层入口

Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

1. 阅读使用floorEntry
2. 如果非空条目，return 值
3. 其他returnnull

  Map.Entry<Integer,​ Character> entry = navigableMap.floorEntry(index);
  return null != entry ? entry.getValue() : null;

Answer 2

用lambda得到索引或者前面的索引

htable.keySet().stream().sorted()
  .filter(i -> i <= target).max(Integer::compare).orElse(-1);

… 其中 target 是您正在搜索的索引