Login | Register
My pages Projects Community openCollabNet

Discussions > users > [Fwd: Re: Charles container library]

charles
Discussion topic

Back to topic list

[Fwd: Re: Charles container library]

Reply

Author Matthew Heaney <mheaney at on2 dot com>
Full name Matthew Heaney <mheaney at on2 dot com>
Date 2004-05-18 12:59:24 PDT
Message -------- Original Message --------
Subject: Re: Charles container library
Date: Tue, 18 May 2004 21:57:14 +0200
From: Florian Weimer <fw at deneb dot enyo dot de>
To: Matthew Heaney <matthewjheaney@e​arthlink.net>
CC: <mheaney at on2 dot com>
References: <002601c41734$09​506b20$0202a8c0@alb​.on2.com>

* Matthew Heaney:

>> -----Original Message-----
>> From: Florian Weimer [mailto:fw at deneb dot enyo dot de]
>> Sent: Wednesday, March 31, 2004 12:24 AM
>
>> You probably have to reconsider your approach towards hashing, see:
>>
>> http://www.cs.rice.e​du/~scrosby/hash/
>
> The ordered set in AI-302 has a nested generic package that allows you
> to do key-based insertion and searching. If the hashed map couldn't be
> used, then you could always use the a key-based ordered set. (The
> ordered set is implemented using a balanced tree, which guarantees a
> worst case behavior of O(log n).)

Hashing tends to be faster on large data sets, that's why it's
interesting. 8-)

As a countermeasure against the attack described above, quite a few
developers use the hash function described at

   <http://burtleburtle.​net/bob/hash/doobs.h​tml>,

and start with a randomly chosen initval for each hash table.

This hash function has an interesting advantage: the bucket count of
the hash table needn't be a prime number. You can store a mask and
use bitwise AND to reduce the hash to the bucket count. Given that
integer divisions are very slow, this could result in a tremendous
speed improvement.


--------------------​--------------------​--------------------​---------
To unsubscribe, e-mail: users-unsubscribe@ch​arles.tigris.org
For additional commands, e-mail: users-help at charles dot tigris dot org

« Previous message in topic | 1 of 1 | Next message in topic »

Messages

Show all messages in topic

[Fwd: Re: Charles container library] Matthew Heaney <mheaney at on2 dot com> Matthew Heaney <mheaney at on2 dot com> 2004-05-18 12:59:24 PDT
Messages per page: