[Kamailio-Users] What happens with filled htables?

[Alex Balashov]

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