[Kamailio-Users] What happens with filled htables?

[Daniel-Constantin Mierla]

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/