Re: BSD license compatible hash algorithm?

From: "Aryeh M. Friedman" <aryeh.friedman@xxxxxxxxx>
Date: Fri, 28 Dec 2007 07:49:31 -0500

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

All hashs have issues with pooling.... see
http://www.burtleburtle.net/bob/hash/index.html... btw it is a old
wives tale that the number of buckets should be prime (mostly based
on the very weak implementation Knuth offered)

Forgot to mention this is a theortical not an implementation issue
namely if the range of H is a proper subset of it's domain (which by
definition all finite operations are when considering them over all
integers) then there exists no bijective (i.e. one to one mapping)
function between the two... thus even if the bucket count is equal to
the number of elements to be hashed there will be collisions [roughly
1/3] unless you use something like gperf to find a perfect hash (this
is impractical for all non-dictionary [i.e. static compile time
content] applications)

- --
Aryeh M. Friedman
FloSoft Systems
http://www.flosoft-systems.com
Developer, not business, friendly
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4 (FreeBSD)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHdPDbzIOMjAek4JIRAgE0AJ4y5b52d+8VajtSwugQjqEitlagxgCeMAn5
hY7RqL5Ije6MTusv7k3ORAI=
=HJbs
-----END PGP SIGNATURE-----

_______________________________________________
freebsd-hackers@xxxxxxxxxxx mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@xxxxxxxxxxx"

References:
- BSD license compatible hash algorithm?
  - From: Garrett Cooper
- Re: BSD license compatible hash algorithm?
  - From: Brooks Davis
- Re: BSD license compatible hash algorithm?
  - From: Garrett Cooper
- Re: BSD license compatible hash algorithm?
  - From: Ivan Voras
- Re: BSD license compatible hash algorithm?
  - From: Aryeh M. Friedman

Prev by Date: Re: BSD license compatible hash algorithm?
Next by Date: Re: BSD license compatible hash algorithm?
Previous by thread: Re: BSD license compatible hash algorithm?
Next by thread: Re: BSD license compatible hash algorithm?
Index(es):
- Date
- Thread

Relevant Pages

Re: Perl hashing speedup ?
... I feel that disbalanced bucket usage / and less number of hash buckets ... Now
I have some queries regarding way perl hashing mechanism maps keys ... about how perl
hashes work internally; but I guess we will be needing ... (comp.lang.perl.moderated)
Re: Hashing
... What you have to keep in mind is that a hash table for words in by ... linear
testing of buckets. ... What is important is to ensure that you have an effective collision
... memory for the table, you need two arrays, one is the pointers to the ... (alt.lang.asm)
Re: Hash table in C++? STL?
... > a tree-like structure instead of lists for the buckets). ... > the standard
will require equality or a relational comparator. ... the hashing function is where
all the complexity lies and I'd be ... But we need hash only the first maxchars characters.
... (comp.lang.cpp)
Re: SGI hash_map
... >> studied hash functions you'll find on the web. ... > And before
inserting into the map, each hash value is calculated with: ... a uniform distribution.
... a program to count the number of buckets that contain multiple items. ... (comp.lang.cpp)
Re: Hash table in C++? STL?
... I wouldn't dare claim to be either, without doing some research first. ... by
the number of items that hash to that index. ... perhaps you meant "the size measured in
number of buckets" and I was ... second hash function is used to determine the sequence
of slots to try. ... (comp.lang.cpp)