Hashmap(O(1))支持joker/匹配所有密钥

题目不太清楚，因为我不能把我的问题放在一个句子里(如果你对这个问题有更好的题目，请建议)。我将尝试用一个例子来澄清我的要求：

假设我有一张这样的桌子：

| Origin | Destination | Airline   | Free Baggage |
===================================================
| NYC    | London      | American  | 20KG         |
---------------------------------------------------
| NYC    | *           | Southwest | 30KG         |
---------------------------------------------------
| *      | *           | Southwest | 25KG         |
---------------------------------------------------
| *      | LA          | *         | 20KG         |
---------------------------------------------------
| *      | *           | *         | 15KG         |
---------------------------------------------------
and so on ...

此表描述了航空公司在不同航线上提供的免费行李数量。您可以看到，有些行具有*值，这意味着它们匹配所有可能的值(这些值不一定是已知的)。

因此，我们有一个行李规则的大列表(如上表所示)和一个航班(其出发地、目的地和航空公司已知)的大列表，我们打算以最有效的方式找到每一个航班的行李量(显然，迭代列表不是一种有效的方式，因为它将花费O(N)计算)。每个航班可能存在多个结果，但我们假设在这种情况下，首选第一个匹配或最具体的匹配(以更简单的为准)。

如果表中没有*符号，问题就会很容易，我们可以使用值为Tuple的Hashmap或Dictionary作为键。但由于存在这些*(比方说匹配所有)密钥，所以提供一个通用的解决方案并不是那么简单。

请注意，上面的例子只是一个例子，我需要一个可以用于任何数量的密钥的解决方案，而不仅仅是三个。

对于这个问题，您有什么想法或实现吗？查找方法的时间复杂度等于或接近O(1)，就像常规的哈希图一样(内存不会是问题)？最好的解决方案是什么？

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

一个琐碎而简单的解决方案可以是内存中的SQlite数据库。但它可能是O(log2(n))中的某些内容，而不是O(1)。主要优点是易于设置，IF性能足够好，这可能是最终解决方案。这里的关键是使用适当的索引、LIKE运算符，当然还有定义良好的JOIN子句。

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

数据必须存储在类似向量的容器VECDATA中，由O(1)中的简单索引访问。将其视为数据库中的主键，我们将其称为PK。在O(1)中，知道PK会立即为您提供所需的数据。总共有N行。
对于不包含任何*的每一行，您将在一个名为MAINHASH的实际哈希映射中插入对(<tuple>, PK)。这是您的主要索引，以获得确切的结果。它将在O(1)中，但您的请求可能不在。。。显然，您必须保持MAINHASH和VECDATA之间的一致性，无论需要什么(互斥、锁，只要两者都一致，就不在乎)。此哈希最多包含N条目。如果没有任何玩笑，它将充当一个标准的hashmap，但间接指向VECDATA。在这种情况下仍然是O(1)。
对于每个可搜索的列，您将构建一个专门用于该列的特定索引。该索引包含N条目。它将是一个标准的hashmap，但它必须为给定的键允许多个值。这是一个非常常见的容器，所以它不应该是一个问题。对于每一行，索引条目将为：( <VECDATA value>, PK )。容器存储在索引向量INDEX[i]中(与0<=i<M一起)。与MAINHASH相同，必须强制执行一致性。

显然，所有这些索引/子容器都应该在将条目插入VECDATA时构建，并在需要时跨会话保存在磁盘上-您不希望每次启动应用程序时都重新构建所有这些。。。

搜索一行

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

在MAINHASH中搜索。如果找到，返回，搜索完成。升级(见下文)：在进入步骤#2之前，也在CACHE中进行搜索。
对于每个元组元素tuple[0<=i<M]，在INDEX[i]中搜索两个tuple[i](返回PK、EXACT[i]的向量)AND以搜索*(返回另一个PK、FUZZY[i]的向量)。
使用这两个向量，构建另一个(临时)散列TMPHASH，关联( PK, integer COUNT )。非常简单：如果条目来自EXACT，则COUNT被初始化为1，如果条目来自于FUZZY，则0被初始化。
对于下一列，构建EXACT和FUZZY(请参见#2)。但是，您将将结果合并到中，而不是创建新的临时哈希，而不是生成新的TMPHASH。方法是：如果TMPHASH没有这个PK条目，则丢弃这个条目：它根本不匹配。否则，读取COUNT值，根据其来源将1或0添加到其中，然后将其重新注入TMPHASH。
完成所有列之后，您必须分析TMPHASH。

分析`TMPHASH`

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

分析整个TMPHASH容器，搜索最大的COUNT。在存储器中维护与COUNT的当前最大值相关联的PK
开发人员的选择：如果多个COUNT具有相同的最大值，您可以全部返回，也可以返回第一个或最后一个
如果COUNT显然总是严格低于M，否则，您会在MAINHASH中找到元组。与M相比，该值可以为您的结果提供置信度标记(=置信度的100*COUNT/M%)
现在，您还可以将搜索到的原始元组和相应的PK存储在另一个名为CACHE的哈希映射中。由于在VECDATA中添加/修改某些内容时，要正确更新CACHE太复杂了，所以在发生CACHE时只需清除即可。毕竟这只是一个缓存

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

精确匹配/缓存的匹配在O(1)中。模糊搜索在O(n.M)中，n是匹配行的数量(当然还有0<=n<N)。

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

我建议使用修饰了一些数据的Tries。对于路线，您想知道最低的路线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)。只有当M是一个常数时，才能得到O(1)。

您可以很容易地在O(2^M)中解决您的问题，这对于小型M来说是实用的，如果您将M视为常数，则它实际上是O(1)。

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

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种可能性——不错！也许你会更早地找到答案。

搜索一行

分析`TMPHASH`

相关内容

最新更新

热门标签：

Hashmap(O(1))支持joker/匹配所有密钥

搜索一行

分析TMPHASH

相关内容

最新更新

热门标签：

分析`TMPHASH`