[Kamailio-Users] What happens with filled htables?

Alex Balashov abalashov at evaristesys.com
Wed Aug 26 15:32:07 CEST 2009


Oh, and dynamically instantiating hash tables without having to 
enumerate them statically in modparam("htable", "htable", ...) would be 
a huge plus.  :-)

Alex Balashov wrote:

> Hey Daniel,
> 
> Another feature idea:
> 
> Have a way to serialise a hash table and pass it around between elements 
> condensed into a header value.  It can then be deserialised and 
> resurrected into a hash table on the other side.
> 
> I have a setup I run that involves 3 Kamailio proxies that perform 
> different parts of the logic and have to constantly use 5-6 custom 
> headers to shuttle data around.  It is very annoying and messy to manage 
> all this.
> 
> What do you think?
> 
> -- Alex
> 
> Daniel-Constantin Mierla wrote:
> 
>> comprehensive description ... for more, see wikipedia:
>>
>> http://en.wikipedia.org/wiki/Hash_table
>>
>> Cheers,
>> Daniel
>>
>> On 26.08.2009 15:43 Uhr, Alex Balashov wrote:
>>> The size of a hash table only indicates how many buckets it has, not 
>>> how many entries it can hold.  Entries can hash to the same bucket 
>>> ID;  this will result in collisions, which hash table implementations 
>>> can manage.
>>> Various algorithms dealing with collision scenarios account allow the 
>>> buckets to be oversubscribed, if necessary.
>>>
>>> Typical collision management strategies are either to hang a linked 
>>> list off a bucket containing all entries beyond the head that also 
>>> mapped to that bucket, or some sort of mathematical approach that 
>>> computes a different bucket to use at deterministic relation to the 
>>> one that has collided.
>>>
>>> Larger table sizes will - given a decent and appropriate hash 
>>> algorithm - cause fewer (if any) collisions since the factors and/or 
>>> divisors involved in common hash functions are more numerous.  This 
>>> is desirable because a collision-ridden table takes longer to search, 
>>> undermining its usefulness as a data structure of O(1) search 
>>> complexity.
>>>
>>> For example, if a list of collided keys (and value pointers) is hung 
>>> off a bucket, that list is searched linearly once the hash 
>>> computation is run and the first value encountered is not found to be 
>>> the one sought.
>>>
>>> So, a very small table size will cause your table to degenerate into 
>>> a few parallel linear structures, and that's assuming a perfect 
>>> uniform distribution from the hash function and variance in keys.  
>>> Larger table sizes eliminate - or mitigate - this problem.
>>>
>>> catalina oancea wrote:
>>>
>>>> What do you mean with:
>>>> "A hash table is filled when no more shm is available, it is better
>>>> not to get there since not much will work at that time." ?
>>>>
>>>> In the docs I understood that the size parameter decides the number 
>>>> of entries:
>>>> "size - number specifying the size of hash table. The number of
>>>> entries in the table is 2^size "
>>>>
>>>>
>>>> 2009/8/26 Daniel-Constantin Mierla <miconda at gmail.com>:
>>>>>
>>>>> On 26.08.2009 14:38 Uhr, Alex Balashov wrote:
>>>>>> Daniel-Constantin Mierla wrote:
>>>>>>> Hi,
>>>>>>>
>>>>>>> On 26.08.2009 14:26 Uhr, catalina oancea wrote:
>>>>>>>> Hello
>>>>>>>>
>>>>>>>> I use the htable module a lot but the only problem, when I add a 
>>>>>>>> new
>>>>>>>> entry in a htable, is when I will delete it. My question is: if the
>>>>>>>> hash table is completely filled and I try to add a new value to 
>>>>>>>> it, do
>>>>>>>> I get an error or is an old value automatically deleted to be 
>>>>>>>> able to
>>>>>>>> write my new value? If an old value was automatically deleted 
>>>>>>>> whenever
>>>>>>>> a new value is added, I wouldn't have to bother deleting the 
>>>>>>>> values I
>>>>>>>> no longer need.
>>>>>>>>
>>>>>>> the are deleted only if you have auto-expire set for htable -- 
>>>>>>> see readme
>>>>>>> for defining htables.
>>>>>>>
>>>>>>> A hash table is filled when no more shm is available, it is 
>>>>>>> better not to
>>>>>>> get there since not much will work at that time.
>>>>>> There is no way to manually delete a key->value in a bucket?
>>>>> it is (was there from first day):
>>>>>
>>>>> $sht(a=>x) = null;
>>>>>
>>>>> I have been talking about auto-delete.
>>>>>
>>>>> There are options to delete by regular expression matching against 
>>>>> key or
>>>>> value, see:
>>>>> http://kamailio.org/docs/modules/1.5.x/htable.html#id2491912
>>>>>
>>>>> Cheers,
>>>>> Daniel
>>>>>
>>>>> -- 
>>>>> Daniel-Constantin Mierla
>>>>> * http://www.asipto.com/
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Kamailio (OpenSER) - Users mailing list
>>>>> Users at lists.kamailio.org
>>>>> http://lists.kamailio.org/cgi-bin/mailman/listinfo/users
>>>>> http://lists.openser-project.org/cgi-bin/mailman/listinfo/users
>>>>>
>>>
>>>
>>
> 
> 


-- 
Alex Balashov - Principal
Evariste Systems
Web     : http://www.evaristesys.com/
Tel     : (+1) (678) 954-0670
Direct  : (+1) (678) 954-0671



More information about the Users mailing list