实现BlackList的最有效方法
我正在开发一个Ipfilter并猜测我如何使用任何类型的esque数据结构，开发出非常高效和快速的BlackListfilter。
我想要做的是简单，每个传入/传出连接我必须检查被阻止的IP列表。
IP是分散的，内存使用应该是线性的（不依赖于阻塞列表的数量，因为我想在有限的系统（自制路由器）上使用）。
我有时间，可以从零创建任何东西。 困难对我来说并不重要。 如果你可以使用任何东西，你应该怎么做？
提高此类系统性能的一种方法是使用Bloom Filter。 这是一种概率数据结构，占用的内存非常少，其中可能存在误报，但误报则不然。
如果要查找IP地址，首先要检查Bloomfilter。 如果有错过，您可以立即允许交通。 如果有命中，您需要检查您的权威数据结构（例如哈希表或前缀树）。
您还可以在Bloom Filter之后但在权威数据结构之前创建一个“Bloom Filter中的命中但实际允许”的小缓存。
基本上，这个想法是以慢速路径（IP地址被拒绝）为代价加速快速路径（允许IP地址）。
“最有效”是一个难以量化的术语。 显然，如果你有无限的内存，那么每个IP地址都有一个bin，可以立即索引。
常见的权衡是使用B树型数据结构。 可以为IP地址的前8位预设第一级容器，其可以存储指向包含所有当前被阻止的IP地址的列表的大小。 第二个列表将被填充以防止不必要的memmove()调用并可能进行排序。 （在内存中具有列表的大小和长度允许在插入时间稍微昂贵的情况下在列表上进行就地二进制搜索。）
例如：
127.0.0.1 =insert=> { 127 :: 1 } 127.0.1.0 =insert=> { 127 :: 1, 256 } 12.0.2.30 =insert=> { 12 : 542; 127 :: 1, 256 }
这种数据结构的开销很小，总存储大小是固定的。 更糟糕的情况显然是具有相同最高阶位的大量IP地址。
哈希表是要走的路。 它们在查找，插入和删除方面具有平均O（1）复杂度！ 他们往往比树木占用更多的记忆，但速度要快得多。
由于您只使用32位整数（当然可以将IP转换为32位整数），所以事情会非常简单快速。
您只需使用已排序的数组即可。 插入和删除成本是O（n）但查找是O（log n），特别是每个ip的内存只有4个字节。 实现非常简单，也许太多了：D
二叉树具有查找，插入和删除的O（log n）的复杂性。 然而，一个简单的二叉树是不够的，你需要一个AVL树或一个红黑树，它可能非常烦人且实现起来很复杂。 AVL和RBT树能够平衡自己，我们需要这样，因为不平衡树的查找时O（n）的时间复杂度最差，这与简单的链表相同！
如果不是单一且唯一的ip你需要禁用ip范围，可能你需要一个Patricia Trie，也称为Radix Tree，它们是为词典和ip词典而发明的。 然而，如果没有很好的书写\平衡，这些树可能会更慢。 对于简单的查找，Hashtable总是更好！ 它们太快而不真实:)
现在关于同步：
如果在应用程序启动时只填充黑名单一次，则可以使用没有multithreading和锁定问题的普通只读哈希表（或基数树）。
如果你不经常更新它，我建议你使用读写器锁。
如果您需要非常频繁的更新，我建议您使用并发哈希表。 警告：不要自己编写，它们非常复杂且容易出错，在网上找到实现！ 他们使用了很多新的处理器（相对）新的primefacesCAS操作（CAS意味着比较和交换）。 这些是一组特殊的指令或指令序列，允许在单个primefaces操作中比较和交换存储器上的32位或64位字段，而无需锁定。 使用它们可能很复杂，因为您必须非常了解您的处理器，操作系统，编译器和算法本身是违反直觉的。 有关CAS的更多信息，请参见http://en.wikipedia.org/wiki/Compare-and-swap 。
并发AVL树是发明的，但它太复杂了，我真的不知道该怎么说:)例如， http：//hal.inria.fr/docs/00/07/39/31/PDF/ RR-2761.pdf
我刚刚发现并发基数树存在： ftp ： //82.96.64.7/pub/linux/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf但它也很复杂。
并发排序数组当然不存在，您需要一个读写器锁来进行更新。
还要考虑处理非并发哈希表所需的内存量可能非常少：对于每个IP，您需要4个字节用于IP和指针。 你还需要一个大的指针数组（或带有一些技巧的32位整数），其大小应该是一个大于应该存储的项目数的素数。 Hashtables当然也可以根据需要调整自己的大小，但是它们可以存储比素数更多的项目，但代价是查找时间较慢。
对于树和散列表，空间复杂度是线性的。
我希望这是一个multithreading应用程序而不是多进程应用程序（fork）。 如果不是multithreading，则无法以快速可靠的方式共享内存的一部分。