using XOR as a hash function

Question

I'm writing a simple small IP hash table on an FPGA for an ARP cache. On the FPGA I need to ensure I can very efficiently calculate the hash due the critical path of the circuit.

I have a 32-bit input that I need to reduce to between 2- and 12-bit hash (Compile time configurable). I'm leaning on simply Xoring the bits together as needed. But when I look in the wild I see sometimes people are using more advanced algorithms such as truncated CRC32 for this. In fact I'm even considering just using the bottom n-bits of the IP as the hash.

I'm definitely not an expert so maybe I am wrong but I really don't see the advantage of using CRC32 for the hash function. Since the Hash is not sensitive I think Xor or even just truncating the IP itself should perform similar.

So my question is: Is doing truncation or xor hash for such a use case considered OK and why?

Answer 1

Well, in this use case (rather than cases which need cryptographic hash functions), what you want is a hash function that, given the distribution of IP addresses you see, assigns each hash result about equally (that is, it acts similarly to if the mapping between IP addresses and ARP cache lines were random, even though we know that it is quite far from random).

So, your question comes down to: will just extracting a few bits from the IP address achieve that? Well, I don't know (and I suspect it would rather depend on how those IP addresses are assigned, and also whether we're talking about IPv4 or IPv6). On the other hand, if all those IP addresses are assigned by a single DHCP server, and that server assigns IP addresses in sequential order, extracting a few low order bits might be exactly what you want (and do a bit better than a true random approach).

On the other hand, perhaps you can't depend on that. The nice thing about a CRC-based approach is that it doesn't have any strong dependancies on how IP addresses are assigned (as long as the assigner wasn't designed with the CRC polynomial in mind).

So, bottom line: it depends on the networking scenario...