什么是检查一个数字是否存在于多个集合中而不搜索所有集合的好算法？
What is a good algorithm to check whether or not a number exist in multiple sets without searching them all?
场景
假设您在 3 个区域中有多个数据库。区域 A、B 和 C。每个区域在不同的地理位置。同时，您有一个应用程序将根据用户的地理位置路由用户名和密码。例如，用户 A 将被重定向到区域 A 中的数据库。用户 B 区域 B 等等。
现在，假设用户 A 移动到区域 B。应用程序查询区域 B 将找不到任何内容。查询区域 A 和区域 C 可能需要一些时间，因为区域很远，并且必须查询所有区域中的所有数据库。
我的问题
如何验证 string/number 是否存在于多个集合中？
或
如何在发送查询之前验证数据库中是否存在一行？
我的算法
这并不完美，但可以让您了解我正在尝试做什么
如果我们的数据库有以下 3 个用户
- foo
- 栏
- foobar
我们获取所有 3 个用户的哈希值，如果哈希值不是素数，则寻找下一个素数。
sum = hash(foo).nextPrime() * hash(bar).nextPrime() * hash(foobar).nextPrime()
该金额由所有区域共享。如果我想检查 foo，我可以只取 foo 的散列，寻找下一个素数，然后取 gcd(foo,sum)。如果不等于一。这意味着 foo 存在于某些数据库中。如果它等于一，则意味着 foo 根本不存在。如果我想添加一个新的用户名。我可以简单地做 sum = sum * hash(newUserName).nextPrime().
总和将增长到查询所有数据库速度更快的程度。
你知道解决这个问题的类似算法吗？
适合此应用程序的一种数据结构是 Bloom filter。
布隆过滤器是一种概率数据结构，可让您测试某个项目是否已在集合中。如果测试返回 false 则该项目肯定不在集合中（0% 漏报），如果为 true 则它可能在集合中，但不能保证是（可能出现误报）。
过滤器实现为具有 m 位和一组 k 哈希函数的位数组。要将项目添加到数组（例如用户名），请使用每个哈希函数对项目进行哈希处理，然后取每个哈希值的模 m 来计算要在位数组中设置的索引。要测试一个项目是否在集合中，计算所有的散列和索引并检查数组中的所有相应位是否都设置为 1。如果其中任何一个为零，则该项目肯定不在集合中，如果所有是 1 那么该项目最有可能在集合中，但也有可能不是，使用更大的 m 可以减少误报的百分比。
要实现 k 个散列函数，可以只使用相同的散列算法（例如 CRC32、MD5 等），但在传递给散列函数之前将不同的盐添加到每个用户名字符串中，从而有效地创建 "new" 每种盐的哈希函数。对于给定的 m 和 n（添加的元素数量），哈希函数的最佳数量是 k = (m / n) ln 2
对于您的应用程序，Bloom 过滤器位数组将在所有区域 A B C 等之间共享。当用户尝试登录时，您可以首先检查本地区域的数据库，如果存在则将其登录为普通的。如果本地数据库中不存在，请检查 Bloom 过滤器，如果结果是否定的，那么您可以确定它们不存在于另一个区域中。如果是肯定的，那么您仍然需要检查其他区域中的数据库（因为可能会出现误报），但大概这不是什么大问题，因为无论如何您都会联系其他区域以转移用户的为真阳性的情况下的数据。
使用 Bloom 过滤器的一个缺点是很难（尽管 not impossible）在添加元素后从集合中删除元素。
场景
假设您在 3 个区域中有多个数据库。区域 A、B 和 C。每个区域在不同的地理位置。同时，您有一个应用程序将根据用户的地理位置路由用户名和密码。例如，用户 A 将被重定向到区域 A 中的数据库。用户 B 区域 B 等等。
现在，假设用户 A 移动到区域 B。应用程序查询区域 B 将找不到任何内容。查询区域 A 和区域 C 可能需要一些时间，因为区域很远，并且必须查询所有区域中的所有数据库。
我的问题
如何验证 string/number 是否存在于多个集合中？
或
如何在发送查询之前验证数据库中是否存在一行？
我的算法
这并不完美，但可以让您了解我正在尝试做什么
如果我们的数据库有以下 3 个用户
- foo
- 栏
- foobar
我们获取所有 3 个用户的哈希值，如果哈希值不是素数，则寻找下一个素数。
sum = hash(foo).nextPrime() * hash(bar).nextPrime() * hash(foobar).nextPrime()
该金额由所有区域共享。如果我想检查 foo，我可以只取 foo 的散列，寻找下一个素数，然后取 gcd(foo,sum)。如果不等于一。这意味着 foo 存在于某些数据库中。如果它等于一，则意味着 foo 根本不存在。如果我想添加一个新的用户名。我可以简单地做 sum = sum * hash(newUserName).nextPrime().
总和将增长到查询所有数据库速度更快的程度。
你知道解决这个问题的类似算法吗？
适合此应用程序的一种数据结构是 Bloom filter。
布隆过滤器是一种概率数据结构，可让您测试某个项目是否已在集合中。如果测试返回 false 则该项目肯定不在集合中（0% 漏报），如果为 true 则它可能在集合中，但不能保证是（可能出现误报）。
过滤器实现为具有 m 位和一组 k 哈希函数的位数组。要将项目添加到数组（例如用户名），请使用每个哈希函数对项目进行哈希处理，然后取每个哈希值的模 m 来计算要在位数组中设置的索引。要测试一个项目是否在集合中，计算所有的散列和索引并检查数组中的所有相应位是否都设置为 1。如果其中任何一个为零，则该项目肯定不在集合中，如果所有是 1 那么该项目最有可能在集合中，但也有可能不是，使用更大的 m 可以减少误报的百分比。
要实现 k 个散列函数，可以只使用相同的散列算法（例如 CRC32、MD5 等），但在传递给散列函数之前将不同的盐添加到每个用户名字符串中，从而有效地创建 "new" 每种盐的哈希函数。对于给定的 m 和 n（添加的元素数量），哈希函数的最佳数量是 k = (m / n) ln 2
对于您的应用程序，Bloom 过滤器位数组将在所有区域 A B C 等之间共享。当用户尝试登录时，您可以首先检查本地区域的数据库，如果存在则将其登录为普通的。如果本地数据库中不存在，请检查 Bloom 过滤器，如果结果是否定的，那么您可以确定它们不存在于另一个区域中。如果是肯定的，那么您仍然需要检查其他区域中的数据库（因为可能会出现误报），但大概这不是什么大问题，因为无论如何您都会联系其他区域以转移用户的为真阳性的情况下的数据。
使用 Bloom 过滤器的一个缺点是很难（尽管 not impossible）在添加元素后从集合中删除元素。