I'm trying to learn hash tables as I am hearing that it'll be utilized a lot in the future (advanced programming). My book, however, does not include any lessons on Hash Tables. Any good references for someone trying to learn Hash Tables? Thank you!!
yongj 1 Junior Poster in Training
rubberman 1,355 Nearly a Posting Virtuoso Featured Poster
Hash tables are simply 2-dimension arrays sorted by the key (hash value). The hash value is a mathematical representation of the data stored. There are a number of hashing algorithms that are used these days. The "key" is to select one that will minimize the number of collisions - situations where different data values will result in the same hash value. Hash tables have the ability to deal with this, by having overflow buckets. IE, each hash value can have any number of associated data values, each in a slot in the overflow array. Obviously, if this is a frequent situation, then performance in finding specific items can be seriously impacted, hence the desire to have non-colliding hash algorithms. Generating a good hash can be expensive in terms of CPU time, but cheap in terms of lookup times, especially if the table is stored on disc.
A very good source to study this subject is Knuth, The Art of Computer Programming - Volume 3, Sorting and Searching, published by Addison/Wesley. One of the later chapters deals with hashing in some detail. FWIW, the Berkeley DB libraries for C/C++ are hash-table implementations.
jbennet 1,618 Most Valuable Poster Team Colleague Featured Poster
Look at "C++ Data Structures and algorithms" by glenn rowe. He used to be one of my lecturers, and it was our course text.
Its not very mathematical, being more concerned with real-world uses from a programmers point of view.
yongj 1 Junior Poster in Training
Thank you all for the replies. Do you guys have any online references? I'm mainly trying to find online resources.
mitrmkar 1,056 Posting Virtuoso
yongj 1 Junior Poster in Training
I've been through the Wiki and have been reading the confuzzled page. Both excellent resources! If anyone has additional resources, please feel free to raise them up!
Thanks, forum :D
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.