一个能够匹配所有密钥的哈希图

关于评论,我想得越多,它就越像一个带索引的关系数据库,而不是一个哈希图。。。

一个琐碎而简单的解决方案可能是 In-memory SQlite database 。但可能是里面的东西 O(log2(n)) ,而不是 O(1) 。主要优点是易于设置,而且 如果 性能足够好,这可能是最终的解决方案。 这里的关键是使用正确的索引 LIKE 运算符,当然定义明确 JOIN 条款。

从零开始,我想不出任何解决方案 N 行和 M 列,至少不在 O(M) …但通常情况下,列要比行少得多。很快——我可能跳过了一个细节,我在飞行中写下了——我可以向你推荐这个算法/容器:

1. 数据必须存储在类似矢量的容器中 VECDATA ,通过中的简单索引访问 O(1) 。将此视为 主键 在数据库中,我们称之为 PK .了解 PK 立即给你 O(1) ,所需的数据。你会有 N 行总计。

2. 对于不包含任何 * ,您将插入一个名为 MAINHASH 这对 (<tuple>, PK) 。这是您的主要索引,以获得确切的结果。它将在 O(1) , 但是 你所要求的可能不在。。。显然,您必须在 主散列 和 矢量数据 ,使用所需的任何东西(互斥、锁,只要两者都是一致的,就不在乎了)。 此哈希最多包含 N 条目。在没有任何玩笑的情况下,它将充当一个标准的hashmap,但对于 矢量数据 .它静止不动 O(1) 在这种情况下。

3. 对于每个可搜索的列,您将构建一个特定的索引,专门用于该列。 该索引具有 N 条目。这将是一个标准的哈希图,但它 必须 允许给定键有多个值。这是一个非常常见的容器,所以它不应该是一个问题。 对于每一行,索引条目将为: ( <VECDATA value>, PK ) 容器被存储在索引的向量中, INDEX[i] (与 0<=i<M )。 与 主散列 ,必须强制执行一致性。

显然,所有这些索引/子容器都应该在插入条目时构造 矢量数据 ,并在需要时跨会话保存在磁盘上-您不想每次启动应用程序时都重新构建所有这些。。。

搜索一行

因此,用户搜索给定的元组。

1. 在中搜索 主散列 。如果找到,返回,搜索完成。 升级(见下文):也可在中搜索 CACHE 然后进行步骤#2。

2. 对于每个元组元素 tuple[0<=i<M] ,在中搜索 索引[i] 对于两者 tuple[i] (返回的向量 PK , EXACT[i] ) 以及 对于 * (返回的另一个矢量 PK , FUZZY[i] )。

3. 使用这两个向量,构建另一个(临时)散列 TMPHASH ,关联 ( PK, integer COUNT ) 。很简单: COUNT 初始化为 1 如果条目来自 EXACT 和 0 如果它来自 FUZZY 。

4. 对于下一列,生成 精确的 和 模糊的 (参见#2)。但是 TMPHASH ,你会 合并 将结果放入,而不是创建新的临时哈希。 方法是:如果 TMPHASH 没有这个 PK 条目,丢弃此条目:它根本不匹配。否则,请阅读 计数 值,添加 1. 或 0 根据它的来源,重新注入 TMPHASH 。

5. 完成所有列后,您必须进行分析 TMPHASH 。

正在分析 TMPHASH

首先,如果 TMPHASH 是空的,那么你没有任何合适的答案。将其返回给用户。若它只包含一个条目,则相同:直接返回给用户。 对于中的多个元素 TMPHASH :

• 分析整体 TMPHASH 容器,搜索最大值 计数 .将 PK 与的当前最大值关联 计数 。
• 开发人员的选择:在多重情况下 计数 在相同的最大值下,可以全部返回,也可以返回第一个或最后一个。
• 计数 如果明显总是低于 M -否则,您会在中找到元组 主散列 。此值与 M ,可以给你的结果打上信心(= 100*COUNT/M %信心)。
• 现在,您还可以存储搜索到的原始元组,以及相应的 PK ,在另一个名为 高速缓存 。 因为它太复杂了,无法正确更新 高速缓存 在中添加/修改内容时 矢量数据 ,只需清除 高速缓存 当它发生时。毕竟这只是一个缓存。。。

如果该语言对您没有帮助,尤其是允许重新定义运算符并使所有基本容器可用,那么实现起来就相当复杂,但它应该可以工作。

精确匹配/缓存的匹配在 O(1) 。模糊搜索处于 O(n.M) , n 是匹配行的数量(以及 0<=n<N 当然)。

如果没有进一步的研究,我看不出比这更好的了。它会消耗大量的内存,但你说过这不会是个问题。

我建议用 Trie 有一点数据修饰的。对于路线,您想知道最低的路线ID,这样我们就可以匹配到第一条可用的路线。对于要跟踪还有多少航班需要匹配的航班。

例如,这将使你能够在比赛进行到一半时意识到从城市1到城市2的航班可能与出发路线相匹配 city1, city2 或 city1, * 或 *, city2 或 *, * 而不必为每条路线或航班重复该逻辑。

以下是Python中的概念验证:

import heapq
import weakref

class Flight:
    def __init__(self, fields, flight_no):
        self.fields = fields
        self.flight_no = flight_no

class Route:
    def __init__(self, route_id, fields, baggage):
        self.route_id = route_id
        self.fields = fields
        self.baggage = baggage

class SearchTrie:
    def __init__(self, value=0, item=None, parent=None):
        # value = # unmatched flights for flights
        # value = lowest route id for routes.
        self.value = value
        self.item = item
        self.trie = {}
        self.parent = None
        if parent:
            self.parent = weakref.ref(parent)

    def add_flight (self, flight, i=0):
        self.value += 1
        fields = flight.fields
        if i < len(fields):
            if fields[i] not in self.trie:
                self.trie[fields[i]] = SearchTrie(0, None, self)
            self.trie[fields[i]].add_flight(flight, i+1)
        else:
            self.item = flight

    def remove_flight(self):
        self.value -= 1
        if self.parent and self.parent():
            self.parent().remove_flight()

    def add_route (self, route, i=0):
        route_id = route.route_id
        fields = route.fields
        if i < len(fields):
            if fields[i] not in self.trie:
                self.trie[fields[i]] = SearchTrie(route_id)
            self.trie[fields[i]].add_route(route, i+1)
        else:
            self.item = route

    def match_flight_baggage(route_search, flight_search):
        # Construct a heap of one search to do.
        tmp_id = 0
        todo = [((0, tmp_id), route_search, flight_search)]
        # This will hold by flight number, baggage.
        matched = {}

        while 0 < len(todo):
            priority, route_search, flight_search = heapq.heappop(todo)
            if 0 == flight_search.value: # There are no flights left to match
                # Already matched all flights.
                pass
            elif flight_search.item is not None:
                # We found a match!
                matched[flight_search.item.flight_no] = route_search.item.baggage
                flight_search.remove_flight()
            else:
                for key, r_search in route_search.trie.items():
                    if key == '*': # Found wildcard.
                        for a_search in flight_search.trie.values():
                            if 0 < a_search.value:
                                heapq.heappush(todo, ((r_search.value, tmp_id), r_search, a_search))
                                tmp_id += 1
                    elif key in flight_search.trie and 0 < flight_search.trie[key].value:
                        heapq.heappush(todo, ((r_search.value, tmp_id), r_search, flight_search.trie[key]))
                        tmp_id += 1

        return matched

# Sample data - the id is the position.
route_data = [
    ["NYC", "London", "American", "20KG"],
    ["NYC", "*", "Southwest", "30KG"],
    ["*", "*", "Southwest", "25KG"],
    ["*", "LA", "*", "20KG"],
    ["*", "*", "*", "15KG"],
]
routes = []
for i in range(len(route_data)):
    data = route_data[i]
    routes.append(Route(i, [data[0], data[1], data[2]], data[3]))

flight_data = [
    ["NYC", "London", "American"],
    ["NYC", "Dallas", "Southwest"],
    ["Dallas", "Houston", "Southwest"],
    ["Denver", "LA", "American"],
    ["Denver", "Houston", "American"],
]
flights = []
for i in range(len(flight_data)):
    data = flight_data[i]
    flights.append(Flight([data[0], data[1], data[2]], i))

# Convert to searches.
flight_search = SearchTrie()
for flight in flights:
    flight_search.add_flight(flight)

route_search = SearchTrie()
for route in routes:
    route_search.add_route(route)


print(route_search.match_flight_baggage(flight_search))

正如Wisblade在他的回答中所注意到的 N 行和 M 列的最大复杂度是 O(M) .你可以 O(1) 只有当你考虑 M 成为常数。

你可以很容易地解决你的问题 O(2^M) 对于小型 M 并且有效 O(1) 如果你考虑 M 成为常数。

创建一个散列映射,其中包含(作为键)串联列值的字符串,可能由一些特殊字符分隔,例如斜线:

map.put("NYC/London/American", "20KG");
map.put("NYC/*/Southwest", "30KG");
map.put("*/*/Southwest", "25KG");
map.put("*/LA/*", "20KG");
map.put("*/*/*", "15KG");

然后,当您进行查询时,您可以尝试实际数据和通配符的不同组合。例如,假设您想查询 NYC/LA/Southwest ;那么您可以尝试以下组合:

map.get("NYC/LA/Southwest"); // null
map.get("NYC/LA/*"); // null
map.get("NYC/*/Southwest"); // found: 30KG

如果第三步中的答案为空,您将按如下方式继续:

map.get("NYC/*/*"); // null
map.get("*/LA/Southwest"); // null
map.get("*/LA/*"); // found: 20KG

仍然有两种选择:

map.get("*/*/Southwest"); // found: 25KG
map.get("*/*/*"); // found: 15KG

基本上,对于三个数据列,您可以在hashmap中检查8种可能性——不错!也许你会更早地找到答案。