| |||||||||||||
Throwing one awayThrowing one awayPosted Sep 21, 2012 19:27 UTC (Fri) by Cyberax (✭ supporter ✭, #52523)In reply to: Throwing one away by knobunc Parent article: Throwing one away
You don't need a lexical order, just some stable ordering.
(Log in to post comments)
Throwing one away Posted Sep 21, 2012 20:15 UTC (Fri) by knobunc (subscriber, #4678) [Link]
Agreed... but given that you need an ordering to allow you to locate where a missing arbitrary string needs to go, it must rely on an ordering property present in any arbitrary string. Which leaves you with little other than a lexical ordering.
Throwing one away Posted Sep 21, 2012 20:49 UTC (Fri) by neilbrown (subscriber, #359) [Link]
Yes - ordering doesn't need to be strictly lexical, does need to be stable.
Why would you have an ordering that isn't stable? The obvious answer is that a hash table with chaining is commonly used and does not reliably provide a stable order (as collisions tend to be ordered based on creation order).
My preferred mechanism for directory indexing is a hash table with internal chaining. It easily provides a reliable fixed size telldir cookie, and performance should be quite good until the number of directory entries gets to about half the cookie space.
|
|||||||||||||