 19 Dec, 1998 1 commit


Martin Mareš authored
we can use very simple function which is monotonic with respect to rehashing: n ^= n >> 16; n ^= n << 10; h = (n >> (16  o)) & ((1 << o)  1); where o is table order. Statistical analysis for both backbone routing table and local OSPF routing tables gives values near theoretical optimum for uniform distribution (see ips.c for formulae). The trick is very simple: We always calculate a 16bit hash value n and use o most significant bits (this gives us monotonity wrt. rehashing if we sort the chains by the value of n). The first shift/xor pair reduces the IP address to a 16bit one, the second pair makes higher bits of the 16bit value uniformly distributed even for tables containing lots of long prefixes (typical interior routing case with 24bit or even longer prefixes).
