[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Does anyone have a better scm_string_hash ?
From: |
Stephen Compall |
Subject: |
Re: Does anyone have a better scm_string_hash ? |
Date: |
Thu, 20 Nov 2003 15:48:58 GMT |
Being ever so useful, I was reading through gnulib in coreutils when I
spotted "hash.c". Thought, I'd better take a look. Anyway, here's
the string hashing code in there, even if you really don't want to
explore this further.
Er, of course, this is GPLed....
/* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1.
This is a convenience routine for constructing other hashing functions. */
#if USE_DIFF_HASH
/* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see
B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm,
Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash
algorithms tend to be domain-specific, so what's good for [diffutils'] io.c
may not be good for your application." */
size_t
hash_string (const char *string, size_t n_buckets)
{
# define ROTATE_LEFT(Value, Shift) \
((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift)))
# define HASH_ONE_CHAR(Value, Byte) \
((Byte) + ROTATE_LEFT (Value, 7))
size_t value = 0;
for (; *string; string++)
value = HASH_ONE_CHAR (value, (unsigned char) *string);
return value % n_buckets;
# undef ROTATE_LEFT
# undef HASH_ONE_CHAR
}
#else /* not USE_DIFF_HASH */
/* This one comes from `recode', and performs a bit better than the above as
per a few experiments. It is inspired from a hashing routine found in the
very old Cyber `snoop', itself written in typical Greg Mansfield style.
(By the way, what happened to this excellent man? Is he still alive?) */
size_t
hash_string (const char *string, size_t n_buckets)
{
size_t value = 0;
while (*string)
value = (value * 31 + (unsigned char) *string++) % n_buckets;
return value;
}
#endif /* not USE_DIFF_HASH */
--
Stephen Compall or s11 or sirian
Better to use medicines at the outset than at the last moment.
Sears Tower rs9512c Sundevil AK-47 lynch red noise Treasury global SHA
SRI Clinton kibo blackjack Rand Corporation Crypto AG