时间戳

首页 > 解决方案 > 实现以键为谓词的 KV 结构的恒定查找时间

java - 实现以键为谓词的 KV 结构的恒定查找时间

问题描述

我有大量的业务规则，我希望以一种连贯的方式组织起来。

这些业务规则大致匹配

When (predicate) then (action)

例如在 Java 中：

Predicate<String> when = x -> x.equals("foo");
Supplier<String>  then = () -> "bar";

Predicate<Integer> when2 = x -> !x.equals("fizz");
Consumer<Void>     then2 = () -> System.out.println("buzz");
//etc..

我在这里说明的是任意条件when及其相关操作的列表then。他们可以获取不同类型的值，并返回一些东西或什么都不返回。

我的第一种方法是使用 aHashMap来链接每个 thewhen和 thethen以形成规则集合。然后过滤它，如下所示：

ruleMap.entrySet().stream()
                  .filter(entry -> entry.getKey().test(value))
                  .findFirst()
                  .getValue();

这种方法的问题是我必须遍历整个集合才能这样做。有没有一种方法可以实现恒定的查找时间？

标签： javadata-structures

解决方案

如果您的键选择是整数（使用常量，或按序数顺序使用整数值的枚举），您始终可以为此使用调度表（注意： 未经测试的代码 - 就示例而言）：

// Note: this is a simplistic implementation of an Enum enclosing
// integer values, so that you get the idea. There might be simpler approaches
// on this, such as defining some constants, etc
public enum DispatchKeys {
    FOO(0), BAR(1);

    private final int value;
    private DispatchKeys(int key) {
        this.key = key;
    }

    public int getIntegerKey() {
        return key;
    }
}

Supplier<String>[] dispatcher = new Supplier<String>[] {
  () -> { return "foo"; },
  () -> { return "bar"; }
};

这样您就可以执行以下操作：

// O(1) selection, you practically index an array.
String result = (dispatcher[Dispatchers.FOO.getIntegerKey()])();
System.out.println(result);

如果您的键是另一种类型（String等）或您计划使用比较器箭头功能，建议您使用适合您需要的哈希表实现（例如，HashMap），它具有O(n)最坏情况的复杂性，但摊销复杂性是O(1)。

推荐阅读