diff options
author | Richard Henderson <rth@gcc.gnu.org> | 2001-08-17 12:58:05 -0700 |
---|---|---|
committer | Richard Henderson <rth@gcc.gnu.org> | 2001-08-17 12:58:05 -0700 |
commit | 0ed5305d8db372b0bbaca3401326b04d19786b51 (patch) | |
tree | 4b897d33bbc1a1878fd5aa8044cc90360e4666cd /libiberty/hashtab.c | |
parent | 32fa4d4a5d61299e741e147e46580cef298ad639 (diff) | |
download | gcc-0ed5305d8db372b0bbaca3401326b04d19786b51.zip gcc-0ed5305d8db372b0bbaca3401326b04d19786b51.tar.gz gcc-0ed5305d8db372b0bbaca3401326b04d19786b51.tar.bz2 |
Add commentary.
From-SVN: r44978
Diffstat (limited to 'libiberty/hashtab.c')
-rw-r--r-- | libiberty/hashtab.c | 25 |
1 files changed, 24 insertions, 1 deletions
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index 2807802..89bfe08 100644 --- a/libiberty/hashtab.c +++ b/libiberty/hashtab.c @@ -562,7 +562,30 @@ htab_collisions (htab) return (double) htab->collisions / (double) htab->searches; } -/* Hash P as a null-terminated string. */ +/* Hash P as a null-terminated string. + + Copied from gcc/hashtable.c. Zack had the following to say with respect + to applicability, though note that unlike hashtable.c, this hash table + implementation re-hashes rather than chain buckets. + + http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html + From: Zack Weinberg <zackw@panix.com> + Date: Fri, 17 Aug 2001 02:15:56 -0400 + + I got it by extracting all the identifiers from all the source code + I had lying around in mid-1999, and testing many recurrences of + the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either + prime numbers or the appropriate identity. This was the best one. + I don't remember exactly what constituted "best", except I was + looking at bucket-length distributions mostly. + + So it should be very good at hashing identifiers, but might not be + as good at arbitrary strings. + + I'll add that it thoroughly trounces the hash functions recommended + for this use at http://burtleburtle.net/bob/hash/index.html, both + on speed and bucket distribution. I haven't tried it against the + function they just started using for Perl's hashes. */ hashval_t htab_hash_string (p) |