java - 从基于字符串的键路径快速访问值

Question

我目前正在 ColdFusion 9 中实现类似枢轴数据可视化的通用模型。

我对支持多个度量不感兴趣，并且该模型公开了一个 numeric valueAt(string colKey, string rowKey) 函数， View 可以调用该函数，以便检索基于列和行维度的度量结果聚合。

例如，对于下面的数据集，如果度量为 AVG(Age) 并且列维度为 Rank，则 model.valueOf('3', '') 将返回 2.33。

Wine  Age Rank
WineA 3    3
WineB 4    2
WineC 2    3
WineD 2    3

现在，我自然想到的数据结构是使用 java.util.HashMap 来存储计算数据，使用转换为字符串的列和行值的组合作为键。这意味着根据数据集，我可能有大量以相同前缀开头的键。

我特意创建了一个大型数据集(100 万个条目)，其中包含多个具有相同前缀的字符串，并检查了使用默认 java String.hashCode() 算法和 MurmurHash3 获得的存储桶冲突的百分比。 .

以下是我构建数据集示例的方法:

<cfset maxItemsCount = 1000000>
<cfset tokens = ['test', 'one', 'two', 'tree', 'four', 'five']>
<cfset tokensLen = arrayLen(tokens)>
<cfset items = []>
<cfset loopCount = 1>

<cfloop condition="arrayLen(items) lt maxItemsCount">
    <cfset item = ''>

    <cfloop from="1" to="#tokensLen#" index="i">
        <cfset item = listAppend(item, tokens[i] & loopCount, '_')>
        <cfset arrayAppend(items, item)>
    </cfloop>

    <cfset ++loopCount>
</cfloop>

当数组初始化为 2 * 条目数时，我与 String.hashCode() 发生了 27% 冲突，对于 Murmur 发生了 22% 冲突。 java.util.HashMap 仅存储和检索一次 key 就花费了大约 2580 毫秒。

我正在寻找有关如何提高性能的想法，无论是使用不同的数据结构(可能是嵌套 HashMap ？)还是找到一种方法来减少冲突次数而不损害 API 签名？

谢谢!

Answer 1

对于一百万个条目，总会存在一些冲突(除非您的数组比 1e12 个条目长得多:D)。我猜 MurmurHash 在这里做得很完美，但你可以尝试 MD5 进行比较(这在某种程度上保证了完美的工作)。

Now, the data structure that naturally came to my mind was to use a java.util.HashMap to store the computed data, using a combination of column and row values converted to string as keys. This means that depending on the data set, I might potentially have a very large number of keys that will start with the same prefix.

您正在连接字符串，因此会产生相当多的垃圾。创建一个可能会更好

@Value static class Key {
    private final String row;
    private final String column;
}

作为 HashMap 的键，其中 @Value 是 Lombok注释生成所有无聊的东西，例如 equals、hashCode 和构造函数。

无需 Lombok，您也可以轻松完成，甚至更好:

static class Key {
    Key(String row, String column) {
         // Do NOT use 31 as a multiplier as it increases the number of collisions!
         // Try Murmur, too.
         hashCode = row.hashCode() + 113 * column.hashCode();
         this.row = row;
         this.column = column;
    }

    public int hashCode() {
        return hashCode;
    }

    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Key)) return false;
        Key that = (Key) o;
        // Check hashCode first.
        if (this.hashCode != that.hashCode) return false;
        if (!this.row.equals(that.row)) return false;
        if (!this.column.equals(that.column)) return false;
        return true;
    }

    private final int hashCode;
    private final String row;
    private final String column;
}