On Tue, 12 Aug 2003 00:39:58 +0200 Michael Bellion and Thomas Heinz <nf@hipac.org> wrote: > This is a fundamental issue related to the use of hashes in this > context. It shows that it is _impossible_ to create a hash which > meets the requirement of O(1) rules per bucket in the setting > described above regardless how clever you choose the hash function. > > What do you think about it? Do you agree? The ipv4 FIB hash tables tackle exactly this problem. The resulting worse cast complexity is O(n_bits_in_prefix_mask). The problem you've described is exactly the same as trying to use hashing for routing tables. - : send the line "unsubscribe linux-net" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
