Re: [Caml-list] Hardening [Perl's] hash function further

[Yaron Minsky <yminsky@janestreet.com>]

For what it's worth, Core's Hashtbl module uses AVL trees for the
buckets, so the behavior on large numbers of collisions degrades to
logarithmic rather than linear.

y

On Mon, Nov 25, 2013 at 8:51 AM, Goswin von Brederlow <goswin-v-b@web.de> wrote:
> On Wed, Nov 20, 2013 at 10:47:10PM +0100, Gerd Stolpmann wrote:
>> Generally, I think it is better to change the hash table algorithm in
>> situations where data from untrusted sources is processed. That means
>> using balanced trees for the buckets. Consumes more RAM, but is provably
>> safe. (Or, at minimum, limit the length of the buckets.)
>>
>> Gerd
>
> If you truely have hash collisions then you can't limit the length of
> the buckets. There is no way to make 2 keys with identical hash not
> land in the same bucket.
>
> Or did you mean use a list up to N items and then switch to a tree?
>
> MfG
>         Goswin
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs