On 26.08.2009 14:38 Uhr, Alex Balashov wrote: 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/

On 26.08.2009 15:29 Uhr, Alex Balashov wrote: this is available in kamailio via sqlops and htable module. You can iterate through sql result, have access to column name and value. Not sure right now what it takes to export it to perl or so. The c code has function to add a item in table as simple as add_item(str key, int_str value). Cheers, Daniel -- Daniel-Constantin Mierla * http://www.asipto.com/

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(a)gmail.com>om>:

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: -- Daniel-Constantin Mierla * http://www.asipto.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: -- Alex Balashov - Principal Evariste Systems Web : http://www.evaristesys.com/ Tel : (+1) (678) 954-0670 Direct : (+1) (678) 954-0671

catalina oancea wrote: So, imagine a two-dimensional array. An array of size 4 would mean a 2x2 array. Or, if you prefer, a one-dimensional array of 4 elements. But "tables" are easier to visualise as a grid. Every time a value is inserted, location = hash_function(key, table_size); hash_table[location] = value; happens. The hash_function() is structured in such a way that it will produce a deterministic result; the same key will always result in the same hash. It also is structured to never return a hash value that is greater than the size of the table, as that would result in an array overflow. The size is the size of the set of all possible values hash_function() can produce. How the hash function works exactly depends on the data and there are many strategies. Good hash functions achieve as much of an "optimal" distribution as possible; with size=4, the aim is to have about 25% of the stored values go in hash_table[0], 25% in hash_table[1], 25% in [2], and 25% in [3]. How exactly to achieve this best is a question I leave to the mathematicians; there are many hash algorithms one can use. Of course, whether the result is optimal or not also depends on the relationship of the hash algorithm to the variation of the data. A very basic and common one is used for introductory teaching is to sum up the ASCII values of the key string and divide them by the size of the table and use the remainder as the hash value, e.g. char key[] = "catalina"; int sum = 0; for(int i = 0; i < sizeof(key); i ++) sum += (int) i; return (sum % HASH_TABLE_SIZE); Of course, this is a rather naive hash function and more sophisticated ones are available. Anyway, the point is that if you have a table with a size of 4, the most optimal, best-case scenario is that you will have the first 4 insertions map to a unique value among those 4. Anything inserted AFTER that will *necessarily* result in a collision - AKA there is another element in that bucket, and it is necessary to chain the elements and/or use some sort of linear approach. This increases the computational complexity of the search and removes the speed advantage which is the point of using a hash table as a data structure in the first place: struct value_data *hash_lookup(table_t **tbl, char *key) { int idx = hash_lookup(tbl->size, key); struct bucket_node *scan = NULL; if(tbl->buckets[idx] == NULL) return NULL; for(scan = tbl->buckets; scan; scan = scan->next) { if(!strcmp(scan->key, key)) return scan->value; } return NULL; } With a larger table, you get the advantage of having more mathematically possible unique buckets for the data to go into, thus reducing or eliminating the need for a linear search. If you try to stuff 200 values into 4 buckets, you're going to get a best-case performance of about O(N/4), or O(50). With a table size > 200, you'll get a best-case performance of O(1), which is the point of a hash table. All associative arrays and "maps" in various high-level languages, e.g. Perl my %hash = ( 'key' => 'value' ); and PHP: my $arr = array( 'key' => 'value' ); and Java: HashMap<String, String> m = new HashMap<String, String>(); m.put("Catalina", "Oancea"); ... work on this principle, but dynamically resize themselves in the background in accordance with the runtime population of the structure. The difference is that in the Kamailio 'htable' module, you must specify a fixed size at initialisation. -- Alex -- Alex Balashov - Principal Evariste Systems Web : http://www.evaristesys.com/ Tel : (+1) (678) 954-0670 Direct : (+1) (678) 954-0671

Daniel-Constantin Mierla wrote: Thanks, that was a much-needed clarification omitted from my explanation. I have always been told that table sizes that are prime numbers result in better distribution of factors due to the way modulo works, although I am not a mathematician and don't have a ready understanding of why. Is this true? Is there some reason you did not take this approach? Is hash_value & 2(^size - 1) equally fast? -- Alex Balashov - Principal Evariste Systems Web : http://www.evaristesys.com/ Tel : (+1) (678) 954-0670 Direct : (+1) (678) 954-0671

Daniel-Constantin Mierla wrote: I suppose the key is, as always, a hash function that produces radically different results even for very cosmetically similar data, much like MD5 /CRC32/etc. does. -- Alex Balashov - Principal Evariste Systems Web : http://www.evaristesys.com/ Tel : (+1) (678) 954-0670 Direct : (+1) (678) 954-0671

Daniel-Constantin Mierla wrote: While it would be nice to have the table dynamically resize itself at runtime, it is not necessary. All I was suggesting was a wrapper around the process of iterating through a serialised data structure and re-hashing the keys=>values. The table can still be fixed-size. It's really just serialisation/deserialisation that is the essence of the request. Setting the size on the deserialising end in a way appropriate to the required performance characteristics can still be up to the user. Will do. Is the htable code fairly simple? I might contribute. -- Alex Balashov - Principal Evariste Systems Web : http://www.evaristesys.com/ Tel : (+1) (678) 954-0670 Direct : (+1) (678) 954-0671