RE: [Hash function Ipv4]
Hi, I did some tests with some subnets Ip /24 and I will share the results. I got very good results with this configuration: Hash table's size: Let x be the number of ip. Y = x*2, then size_table = 'The power of 2 closest to Y, and greater than or equal to Y'. Hash Function: return Ip_in_network_byte_order % size_table; Collision's case: In this case i have used research quadratic: ((unsigned int)( hash_function + 0.5*k + 0.5*k*k )) % size_table ; -- on the other hand When I have used Random Ip, that does not belong to the same subnet ip: unsigned int HASH = 2039; uint32_t h; h = key % HASH; key /= HASH; h ^= key % HASH; h ^= key / HASH; Suggested to me by Poul-Henning Kamp (thanks) works much better. That's all. Bye Enrico ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [Hash function Ipv4]
On (02/06/2012 20:14), enrico d'urso wrote: > > Hi, > I'm looking for an Hash function for Ipv4 addresses. > > What are good ones? Have you tried good general purpose hash functions like murmur3 or cityhash? Another option is to use "hash" function that is bijection on integers and exploit this fact in data structure, e.g. by using hash array mapped trie or another prefix tree. The easiest way to build such function is Feistel network on top of general purpose hash function as round function. Li and Ri will be most and less significant 16 bits of ipv4 address accordingly. At least 3 Fiestel rounds required. Play with function to achieve better performance/distribution. https://en.wikipedia.org/wiki/Feistel_cipher Reduced round and block size RC5 also looks very attractive, but it's patented :( Thanks, Gleb. ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
Re: [Hash function Ipv4]
In message , enrico d'urso writes: > >I'm looking for an Hash function for Ipv4 addresses. > >What are good ones? They are generally very hard to hash well, for all sorts of reasons related to how we use them. One way that used to work reasonably well for me: uint32_t ipv4, h; h = ipv4 % HASH; ipv4 /= HASH; h ^= ipv4 % HASH; h ^= ipv4 / HASH; Where HASH was a prime number near to 2^11 However, I cannot rule out that the good results I saw was a result if RIPE's allocation policy at the time. -- Poul-Henning Kamp | UNIX since Zilog Zeus 3.20 p...@freebsd.org | TCP/IP since RFC 956 FreeBSD committer | BSD since 4.3-tahoe Never attribute to malice what can adequately be explained by incompetence. ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
[Hash function Ipv4]
Hi, I'm looking for an Hash function for Ipv4 addresses. What are good ones? Bye Enrico ___ freebsd-hackers@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
