Re: I'm a total push-over..

On Wed, 23 Jan 2008, Andreas Ericsson wrote:

Hashing filenames is pretty easy. You can do a reasonable job with any "multiply by an odd number, add in value". Picking the odd number is a random choice, some are better than others (and it depends on whether you end up always having a power-of-two bucket size etc), but it generally won't be horrible.

And considering that we generally won't have tons and tons of pathnames (ie we'd generally have thousands, not millions), and that the underlying hash not only resizes itself but actually uses the ful 32 bits as the lookup key, I don't worry too much. I suspect my random choice is fine.

So no, I didn't think my hash would _suck_, although I also didn't research which odd numbers to pick.

No, it's a joke because it doesn't really give an example of how to do the _expected_ hash collissions.

Here's another hash that is actually going to collide *much* more (and on purpose!), but is actually showing an example of something that actually hashes UTF strings so that upper-case and lower-case (and normalization) will all still hash to the same value:

	static unsigned int hash_name(const char *name, int namelen)
	{
	        unsigned int hash = 0x123;

	        do {
	                unsigned char c = *name++;
			if (c & 0x80)
				c = 0;
			c &= ~0x20;
	                hash = hash*101 + c;
	        } while (--namelen);
	        return hash;
	}

but the above does so by making the hash much much worse (although probably still acceptable for "normal source code name distributions" that don't have very many same-name-in-different-cases and high bit characters anyway).

The above is still fairly fast, but obviously at a serious cost in hash goodness, to the point of being totally unusable for anybody who uses Asian characters in their filenames.

To actually be really useful, you'd have to teach it about the character system and do a lookup into a case/normalization table.

So *that* is mainly why it's a joke. But it should work fine for the case it is used for now (exact match).

Picking a better-researched constant might still be a good idea.

		Linus