What hash functions (and how many of them) does Squid use?
The protocol design allows for a variable number of hash functions (k). However, Squid employs a very efficient method using a fixed number – four. Rather than computing a number of independent hash functions over a URL Squid uses a 128-bit MD5 hash of the key (actually a combination of the URL and the HTTP retrieval method) and then splits this into four equal chunks. Each chunk, modulo the digest size (m), is used as the value for one of the hash functions – i.e. an index into the bit array. Note: As Squid retrieves objects and stores them in its cache on disk, it adds them to the in-RAM index using a lookup key which is an MD5 hash – the very one discussed above. This means that the values for the Cache Digest hash functions are already available and consequently the operations are extremely efficient! Obviously, modifying the code to support a variable number of hash functions would prove a little more difficult and would most likely reduce efficiency.
