场景
假设您在3个区域中有多个数据库。区域A，B和C。每个区域位于不同的地理位置。同时，您有一个应用程序，它将根据用户的地理位置路由用户名和密码。例如，用户A将被重定向到Zone A中的数据库。用户B区域B等。
现在，假设用户A移动到区域B。应用程序查询区域B不会找到任何内容。由于区域距离较远，因此查询区域A和区域C可能会花费一些时间，并且必须查询所有区域中的所有数据库。
我的问题
如何验证一个字符串/数字是否存在于多个集合中？
要么
甚至在发送查询之前，如何验证数据库中是否存在行？
我的算法
这不是完美的方法，但是可以让您了解我要做什么
如果我们的数据库具有以下3个用户
我们获取所有3个用户的哈希，如果哈希不是素数，则寻找下一个素数。
sum = hash(foo).nextPrime() * hash(bar).nextPrime() * hash(foobar).nextPrime()
该总和在所有区域之间共享。如果我想检查
foo，我可以只取foo的哈希，并寻找下一个素数，然后取gcd(foo,sum)。如果不等于1。这意味着foo存在于某些数据库中。如果等于1，则表示foo根本不存在。如果要添加新的用户名。我可以简单地做sum = sum * hash(newUserName).nextPrime().总和将增加到查询所有数据库更快的程度。
您知道解决该问题的类似算法吗？
最佳答案
适用于此应用程序的一种数据结构是Bloom filter。
布隆过滤器是一种概率数据结构，可让您测试项目是否已在集合中。如果测试返回假，则该项目肯定不在集合中(0％假阴性)，如果为真，则该项目可能在集合中，但不能保证是(可能出现假阳性)。
该过滤器被实现为具有m个位和一组k个哈希函数的位数组。要将项目添加到数组(例如用户名)，请使用每个哈希函数对项目进行哈希处理，然后对每个哈希值取模，以计算要在位数组中设置的索引。要测试某项是否在集合中，请计算所有哈希值和索引，并检查数组中所有相应的位是否都设置为1。如果它们中的任何一个为零，则该项绝对不在集合中，如果全部如果为1，则该项目最有可能出现在集合中，但可能性很小，可以使用较大的m来减少误报的百分比。
为了实现k个散列函数，可以仅使用相同的散列算法(例如CRC32，MD5等)，但在传递给散列函数之前，在每个用户名字符串后附加不同的盐，从而为每个散列有效地创建"new"散列函数盐。对于给定的m和n(要添加的元素数量)，哈希函数的最佳数量为k =(m/n)ln 2
对于您的应用程序，Bloom过滤器位阵列将在所有区域A B C等中共享。当用户尝试登录时，您可以先检入本地区域的数据库，如果存在，则按常规登录。如果本地数据库中不存在，请检查Bloom过滤器，如果结果是否定的，则可以确定它们在另一个区域中不存在。如果是肯定的，那么您仍然需要检查其他区域中的数据库(因为可能会出现误报)，但这大概不是一个大问题，因为无论如何您都将联系其他区域以转移用户的数据库。如果它是一个真正的积极数据。
使用Bloom过滤器的缺点是(一旦添加了not impossible)就很难从集合中删除它们。