快速查找表中的行的java算法

Question

我有一个包含以下字段的文档：

• 字段1
• 字段2
• 字段3
• 字段4

我有以下表格结构：

field1  |  field2  |  field3  |  field4  || result
--------------------------------------------------
foo                   bar                   MC
foo        test1                            MR
           test2                 test3      OM
foo        test1      bar                   CM

当一个文档输入时，字段1为foo，字段2（空值），字段3为bar，应选择结果MC。 当一个文档进来时，字段1是foo，字段2是test1，字段3是bar，结果CM应该被选择

当然，您可以检查每一列并保持匹配行处于打开状态，直到循环每一行。 但是，这个表结构可能会变得非常大，我正在寻找某种算法来解决上述问题，以一种性能良好的方式

有什么想法吗

Answer 1

对于任何这样的字符串搜索，最快的选项是基数树。创建4个基数树，每个字段一个，其中树的叶子是值参与的记录的排序列表。例如，对于字段1，如果搜索Foo，它应该返回类似{1，2，4}的列表，表明Foo位于字段1的记录1，2和4中。结果是你将有4组数字，它们的交点就是答案

求交可以在线性时间内完成，因为它们是按顺序排列的。下面是一个简单的排序集求交算法，可以在C中实现这一点：

#define int32 unsigned int

// A, B - operands, sorted arrays
// s_a, s_b - sizes of A and B
// C - result buffer
// return size of the result C
size_t intersect_sorted_list(int32 *A, int32 *B, size_t s_a, size_t s_b, int32 *C) {
    size_t i_a = 0, i_b = 0;
    size_t counter = 0;

    while(i_a < s_a && i_b < s_b) {
        if(A[i_a] < B[i_b]) {
            i_a++;
        } else if(B[i_b] < A[i_a]) {
            i_b++;
        } else {
            C[counter++] = A[i_a];
            i_a++; i_b++;
        }
    }
    return counter;
}

Answer 2

正如@MarkoTopolnik所写，RDBMS做你想做的事情。但是，如果您仍然想要实现自己的算法，一个选项是创建一个树：级别1是field1，级别2是field2，等等。每个分支是表中的一行。如果你只有两个字段，它看起来像这样：

root  field1.valueA  field2.valueC -result1
    \                \
     \                \ field2.valueD -result2
      \
       \field1.valueB  field2.valueC -result3
                     \
                      \ field2.valueD -result4

您可以在每个级别使用哈希表实现此树。首先，您有一个哈希表，其中field1值作为键，hastable作为值。这些哈希表以field2作为键，以result作为值。由于允许null作为值，因此必须使用HashMap而不是Hashtable