Member Avatar for yongj

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!!

  • 5 Contributors
  • 6 Replies
  • 187 Views
  • 22 Hours Discussion Span
  • Latest Post Latest Post by yongj

Dani AI

Generated

Short, practical guide to learning and using hash tables—focused on what the thread already touched on and on things that matter when applying them in C++.

Hash tables map keys to buckets via a hash function; collisions are unavoidable, so the two common families of collision resolution are chaining (overflow buckets or lists) and open addressing (probing). ’s “overflow buckets” is chaining: simple to implement and easy to delete from, but uses extra memory for pointers. Open addressing keeps everything in the array (better cache locality) but needs a lower load factor, careful deletion (tombstones) and attention to clustering. Trade-offs drive the choice depending on expected load, memory constraints and deletion patterns.

Practical C++ advice (real-world focus, as hinted): prefer the standard containers for everyday work. A short example shows how to supply a custom key type and control rehashing:

#include <unordered_map>
#include <string>

struct Point { int x, y; };
struct PointHash {
    size_t operator()(Point const& p) const noexcept {
        return std::hash<int>()(p.x) * 31u + std::hash<int>()(p.y);
    }
};
struct PointEq { bool operator()(Point const& a, Point const& b) const noexcept {
    return a.x==b.x && a.y==b.y;
}};
std::unordered_map<Point, std::string, PointHash, PointEq> m;
m.reserve(1024);
m.max_load_factor(0.7f);

Recommended practical exercises: implement both chaining and open addressing, add resize/rehash, then benchmark with different key distributions and load factors. Watch for common pitfalls: weak hash functions (clustering), inconsistent hash vs equality, mutable keys, floating-point keys and adversarial inputs. Remember complexity notes: expected O(1) average lookup, but O(n) worst-case; rehashing causes occasional heavier cost but is amortized.

Combine small implementations, micro-benchmarks and inspection of std::unordered_map behavior to form a solid, practice-driven understanding before attempting production custom implementations.

Recommended Answers

All 6 Replies

Member Avatar for rubberman

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.

Member Avatar for yongj

Thank you all for the replies. Do you guys have any online references? I'm mainly trying to find online resources.

Member Avatar for mrnutty

Thank you all for the replies. Do you guys have any online references? I'm mainly trying to find online resources.

Wiki is usually a good place to start!

Member Avatar for mitrmkar

You'll probably find useful.

Member Avatar for yongj

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.