[Caml-list] What is the default hash function of string in 3.12?

[Caml-list] What is the default hash function of string in 3.12?

[Jianzhou Zhao]

Hi,

I have a table (with size > 30000) implemented by both Hashtbl and
Map. I found their performance are almost the same. But I think
Hashtbl should be much faster than Map. So, I was wondering what hash
function of String OCaml 3.12 uses, and if I can define my own.

Thanks!
-- 
Jianzhou

Re: [Caml-list] What is the default hash function of string in 3.12?

[rixed]

-[ Tue, Jun 12, 2012 at 04:23:46PM -0400, Jianzhou Zhao ]----
> So, I was wondering what hash
> function of String OCaml 3.12 uses, and if I can define my own.

Here is the relevant part of the code:

--[ byterun/hash.c ]--

    switch (tag) {
    case String_tag:
      hash_univ_count--;
      i = caml_string_length(obj);
      for (p = &Byte_u(obj, 0); i > 0; i--, p++)
        Combine_small(*p);
      break;

----

If I can read C (which sometime I can't) then it seams hashing a string
requires an amount of CPU proportional to the length of the string, and that a
string count as one value only for the depth limit.  We could imagine for
instance that each char decrease the hash_univ_count, but then you need to
choose the chars of the string you consider very wisely.  For instance if you
choose to hash only the first of last N chars then you risk hashing many
strings that ends/starts with the same substrings to the same value. If you
choose one char every N you'r still at risk (for instance strings that differs
only by a few chars may all end with the same hash).  So all in all its not
easy to _not_ process all chars.

As for changing the hash function, you can use the Hashtbl.Make functor to
build your own hash out of the hash function you want.  But there is no way to
change the default hash function for strings AFAICT.