I'm with Branko here... -1
Hash tables are unordered entities. Pure and simple. If you want something else, then introduce something else. But don't mess up hash tables to add a concept which just doesn't belong. Cheers, -g On Thu, Oct 11, 2001 at 07:58:04AM +0200, Mladen Turk wrote: > > -----Original Message----- > > From: Branko Cibej [mailto:[EMAIL PROTECTED] > > Sent: Wednesday, October 10, 2001 10:10 PM > > To: Mladen Turk > > Cc: APR Dev List; Apache Dev > > Subject: Re: [PATCH] apr_hash.c -- Make table ordered > > > > > > Mladen Turk wrote: > > > > >Hi, > > > > > >Here is the patch that makes the apr_hash table ordered in the > > way that the > > >apr_hash_first/apr_hash_next returns the values in order they > > were stored in > > >the table using apr_hash_set. > > >The patch could be IMO very usefull to solve the httpd release > > showstopper > > >Set...Filter Add...Filter, because one can retrive the entries ordered in > > >the way they are entered. > > > > > > > -1. This would add memory (and time) overhead to all hash tables > > everywhere. > > The memory overhead is < 2% in real table (only one extra pointer per slot). > Time overhead happens only when deleting items from table (solvable by using > an extra int), but the walking through table works faster. > > > > > A hash table is an unordered associative container. If you need > > ordering, there are other ways to do this. You could, for instance, put > > your objects into an array and use the hash table as an index over the > > array slots, or join them with a doubly-linked list. > > That would be overhead indeed. > > > But it makes no sense to do this / within/ the hash table implementation. > > It's discussable what makes/makes-no sense :) > The question is where the hash table is used and for what purpose, not for > the sake of the theory itself. > How many entries are in the table itself? It is not used to store couple of > thousand records, not even couple of hundreds. > > I see couple of usages of apr_array (just because they need ordered entries) > that would gain the performance benefit. > > If the hash table implementation _must_ remain as such, then how about > introducing something like apr_shash? > > MT. -- Greg Stein, http://www.lyra.org/
