On Friday 13 April 2007 17:52:16 Eddie Pettis wrote: > > I thought about maybe to create an expandable hashtable, for fun :). > > i.e. you define the number of items per hashkey and if there is no room > > you rebuild the hashtable with a higher order. You can also add that you > > rebuild if the table is xx% filled (probably 67% is a golden ratio) to > > avoid too many rebuilds. > > I don't know if percentage filled is the proper metric for chained > hash tables such as these. Average search depth is probably a better > metric, possibly maintained through an exponential average with a low > decay factor. However, percentage filled is an excellent metric if > you implement an open addressing table. My main concern and reason for percentage is that what happens if the keys of the entries in the buckets are not differentiated even in the next rebuild or 2 rebuilds. That could prove very wasteful, thus, the percentage is meant as a barrier to prevent too many rebuilds, which could waste space and lower performance. You can still use other metrics on top of it. I.e., you can set it at 50% and use average search depth, etc... -- Regards, Tzahi. -- Tzahi Fadida Blog: http://tzahi.blogsite.org | Home Site: http://tzahi.webhop.info WARNING TO SPAMMERS: see at http://members.lycos.co.uk/my2nis/spamwarning.html -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
