On Tue, Aug 30, 2011 at 02:29:34PM +0200, Laurent wrote: > On Tue, Aug 30, 2011 at 12:52, Jos Koot <jos.k...@telefonica.net> wrote: > > > ** > > You are stating: hash with bounded memory > > Does that mean you will have a limit on the number of entries? > > > > Not necessarily. It might grow, although I might limit it to logarithmic > growth. > Or the bound may be very large but unknown, and little memory should be used > most of the time. > > > > In that case a vector plus a current index might do, I think. > > Gives you O(1) access to every element. > > If the required number of elements may vary very much, a vector probably is > > not a good idea, unless using resizable vectors, but that makes some > > operations O(n). > > > > A hash+vector would nearly do it, but in the end it might not get any > simpler than a doubly linked list. > I also need to move items at the end of the list too. > > I should add that this is not for production purpose, but for more > "theoretical" properties, so I don't care much about a potential constant > overhead per operation, but I care about how it would behave with an > increasing number of items. > > Laurent
Would you lso want entries to be garbage-collected? If there are no longer any references to a hash entry's key except as a key in the hash table, would you want the garbage colelctor to be able to remove it? -- hendrik _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
