[Kamailio-Users] What happens with filled htables?

catalina oancea catalina.oancea at gmail.com
Wed Aug 26 15:37:09 CEST 2009


That seems like an interesting idea, Alex.

I still have problems understanding the size parameter. For example
what exactly does size=4 mean?



2009/8/26 Alex Balashov <abalashov at evaristesys.com>:
> 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
>
> _______________________________________________
> 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
>




More information about the sr-users mailing list