2010/10/16 Juha Heinanen <jh(a)tutpro.com>om>: And those collisions mean that I could look for a key name and retrieve another key (as both key names produce the same hash), am I right? So, if I want to handle ~ 300 concurrent entries, with *no* collision, which "size" value is good enough? how to determine it? Thanks a lot. -- Iñaki Baz Castillo <ibc(a)aliax.net>

Iñaki, Just as an addition from experience on hash tables, the first "sweet-spot" on the design is to have a fairly good algorithm so that different keys are mapped on different hash values. You cannot pick this (as far as I read) but we'll think it as fair enough. What you can do to "help" the algorithm is to pick a field already random or large. If you have redundant fields (like username and table ID from a database) try with both "unique" fields as a key and check which gives you better results. Then you should use a table big enough to map a big number of different hash values. As computing is discrete you will find a maximum size, above that size you'll find collisions on some slots and empty slots (because the algorithm cannot generate those hash values). Keep in mind that sizing the hash table will consume memory resources. Last you know that statistically you will bump into collisions, they are inevitable and no real-life practice will guarantee collision-free operation. When you have collisions, what you can do is have a powerful processor to operate searches and inserts quickly. What would be best to optimize the system is to have some statistic information, save every now and then the status of the htable and act accordingly to: - If the table is pretty much or completely used and you have collisions, make the size parameter bigger - If the table is big enough so you'll have some slots free and still have collisions you can try picking some key (if you have redundant ones) that is more "random" so the hash result will be more "random". - If all above is not producing any result, add processor power to the system so searches and inserts are faster Hope these guidelines help, they are some conclusions from hashing and queuing theory books. Cheers, Uriel On Sat, Oct 16, 2010 at 7:47 AM, Juha Heinanen <jh(a)tutpro.com> wrote:

On 10/16/2010 09:18 AM, Juha Heinanen wrote: http://sip-router.org/docbook/sip-router/branch/master/rpc_list/rpc_list.ht… ... is a crude way of visualising the distribution, I imagine. -- Alex Balashov - Principal Evariste Systems LLC 1170 Peachtree Street 12th Floor, Suite 1200 Atlanta, GA 30309 Tel: +1-678-954-0670 Fax: +1-404-961-1892 Web: http://www.evaristesys.com/

Maybe the term entry should be replaced with slot, looks to be more standard. A good doc about hash tables is on wikipedia: http://en.wikipedia.org/wiki/Hash_table The htable module keeps the number of items in a slot, but not exported via rpc, this could be added in the future. Ramona On 10/17/2010 04:39 PM, Iñaki Baz Castillo wrote: