Re^2: Advanced Data Structure Question

traveler,
Given an ordered list, a binary search is the fastest way to find an element. I didn't realize there was a way to use a hashing function and preserve order as well. I thought, apparently incorrectly, that those two things were in conflict with one another. I guess I will look into hashing functions further if you feel they could do the job.

Cheers - L~R

Comment on Re^2: Advanced Data Structure Question

Replies are listed 'Best First'.
Re^3: Advanced Data Structure Question by dragonchild (Archbishop) on Apr 19, 2006 at 15:41 UTC
Given any list, a hashed search is the fastest way to find an element because it's generally O(1) (unlike O(logn) for binary searches), particularly if you have a limit on the number of elements as you do. You can use 1001 as your modulus and (with a little finagling) guarantee uniqueness in your buckets. If you need to maintain order, do so by another data structure. In almost all cases, you can trade RAM for CPU. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re^4: Advanced Data Structure Question by tilly (Archbishop) on Apr 20, 2006 at 00:59 UTC
Given any list if memory access speed is constant, a hashed search averages fastest. Real computers do not have constant memory access time. A tree structure that preserves locality of reference can therefore be faster if the application has "hotspots".	[reply]
Re^3: Advanced Data Structure Question by traveler (Parson) on Apr 19, 2006 at 18:15 UTC
There are ordered hash tables. Knuth did some work with them. You can also have a parallel array with the order information.	[reply]