[Kamailio-Users] What happens with filled htables?

Daniel-Constantin Mierla miconda at gmail.com
Wed Aug 26 16:06:17 CEST 2009



On 26.08.2009 16:32 Uhr, Alex Balashov wrote:
> Oh, and dynamically instantiating hash tables without having to 
> enumerate them statically in modparam("htable", "htable", ...) would 
> be a huge plus.  :-)

could be possible to do this way, but the number of slots has to be 
initialized at startup. Unlike in other cases, here the hash table is in 
shared memory, each slot being protected by a mutex to prevent access 
conflicts.

Might be better to create a issue on the tracker collecting these ideas 
-- as time allows, somebody may contribute.

Cheers,
Daniel


>
> 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
>>>>>>
>>>>
>>>>
>>>
>>
>>
>
>

-- 
Daniel-Constantin Mierla
* http://www.asipto.com/




More information about the Users mailing list