http://blogs.msdn.com/dcook/archive/2007/09/09/hashes-and-tables-and-primes-oh-my.aspxIf you have to write a hash function for something important (i.e. a .NET GetHashCode method or a C++ hash traits class), don't design your own. Steal one that has been well-tested. One of my favorites for speed, simplicity, and quality is the "Jenkinsen-USCommunityServer 2.1 SP1 (Build: 61025.2)http://blogs.msdn.com/dcook/archive/2007/09/09/hashes-and-tables-and-primes-oh-my.aspx#5611251Tue, 23 Oct 2007 01:55:14 GMT91d46819-8472-40ad-a661-2c78acb4018c:5611251John<p>You say: &quot;One good solution is to make a list of items sorted by the associated key. The list can then be searched using a binary search. This works quite well for a large class of problems, and assuming that the list allows for linear-time lookup of item a (where a is a number refering to the a'th item), ..&quot;</p> <p>It's only paragraph 4 and I'm confused already. &nbsp;I'm interpreting this to mean we use a binary search to lookup the key, a, and then once we have the key we can directly get the value ... so wouldn't that be constant-time lookup, not linear-time lookup?</p> http://blogs.msdn.com/dcook/archive/2007/09/09/hashes-and-tables-and-primes-oh-my.aspx#5757275Mon, 29 Oct 2007 10:23:27 GMT91d46819-8472-40ad-a661-2c78acb4018c:5757275dcook<p>John:</p> <p>Finding the index of the key in the table is O(log N). Going from key to value is constant. So the overall operation of finding the value from the key is O(log N).</p>