Walter Prins wrote: > Thomas, > > Not wanting to be a pedant, but you're mixing up Hashing (hash tables) > and B-trees. B-Trees have O(log n) lookup time as you say, but > hashing/hash tables/hash maps don't use B-Trees and in fact has O(1) > lookup time. It takes just as long (in general case) to look up an item > from 100 as it does from 100 000 000. See for example the entry on > wikipedia for "Hash table".
An associative hash (a.k.a. associative array) implements either a hash table or a B-tree - usually the latter in C++ because stl hash_map specifically implements a hash table. Since you like wikipedia: http://en.wikipedia.org/wiki/Associative_array So I'm using correct terminology. Your suggestion to load the entire database into memory is not a good one. According to the OP, it is roughly 100MB...when you take into consideration data structures and data alignment, loading the whole thing would probably consume at least 300MB RAM. You should get yourself a copy of my book on Safe C++ Design Principles. Your assumptions that accessing a hash table is always O(1) are false. When a hash collision occurs, most hash tables switch to a O(n) search algorithm (linked list). Also, as stated in the book, O(1) algorithms usually come with a side-effect of consuming other resources...CPU, memory, etc. In this particular case, calculating a good hash key typically takes many CPU cycles. -- Thomas Hruska CubicleSoft President Ph: 517-803-4197 Safe C++ Design Principles (First Edition) Learn how to write memory leak-free, secure, portable, and user-friendly software. Learn more and view a sample chapter: http://www.CubicleSoft.com/SafeCPPDesign/ ----------------------------------------------------- Home page: http://groups.yahoo.com/group/delphi-en/ To unsubscribe: [EMAIL PROTECTED] Yahoo! Groups Links <*> To visit your group on the web, go to: http://groups.yahoo.com/group/delphi-en/ <*> To unsubscribe from this group, send an email to: [EMAIL PROTECTED] <*> Your use of Yahoo! Groups is subject to: http://docs.yahoo.com/info/terms/
