Member Avatar for nitro

Can someone plz give me the C++ code for the following:

(1) linear probing
(2) separate chaining
(3) quadratic probing
(4) double hashing

I know the theory behind it but i dont seem to be able to put it into code!
plz help me

P/S: im not asking you to spoon feed me with code but im really not able to figure out how to write these functions....

  • 3 Contributors
  • 2 Replies
  • 117 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by Ptolemy

Dani AI

Generated

asked for implementations of linear probing, separate chaining, quadratic probing and double hashing. is right to start with an algorithm; is also right that the implementations are short once the design is clear. The following gives concise, practical sketches (one chaining and one open-addressing) plus key pitfalls and tuning points to apply directly when writing full C++ code.

A straight separate-chaining implementation uses a vector of buckets (list or vector) and is the simplest to get correct. Insertion/search/delete only touch one bucket; resizing just re-inserts every pair into a larger table.

template<typename K, typename V>
class HashChain {
    using Bucket = std::list<std::pair<K,V>>;
    std::vector<Bucket> table;
    size_t count = 0;
    std::hash<K> hasher;
public:
    HashChain(size_t m = 101) : table(m) {}
    void insert(const K& k, const V& v) {
        size_t i = hasher(k) % table.size();
        for (auto &p : table[i]) if (p.first == k) { p.second = v; return; }
        table[i].push_front({k, v}); ++count;
    }
    bool find(const K& k, V& out) const {
        size_t i = hasher(k) % table.size();
        for (const auto &p : table[i]) if (p.first == k) { out = p.second; return true; }
        return false;
    }
    bool remove(const K& k) { /* erase from bucket, decrement count */ }
};

Open addressing needs a probe function and a state for each slot (EMPTY, OCCUPIED, TOMBSTONE). The probe index differs by strategy; double hashing needs a nonzero secondary hash that is coprime with the table size.

enum class Probe { LINEAR, QUADRATIC, DOUBLE };
size_t probeIndex(const K& k, size_t i, Probe mode, size_t m) {
    size_t h1 = std::hash<K>{}(k) % m;
    if (mode == Probe::LINEAR) return (h1 + i) % m;
    if (mode == Probe::QUADRATIC) return (h1 + i + i*i) % m;
    size_t h2 = 1 + (std::hash<K>{}(k) % (m - 1)); // non-zero
    return (h1 + i * h2) % m;
}

Notes, pitfalls and tuning: use std::hash and operator== (or specialize std::hash for custom types). For open addressing, handle tombstones on search vs insert, or rebuild to remove tombstones. Keep load factor low: <= 0.5 for open addressing for predictable probes, higher for chaining (up to 1.0+ depending on bucket structure). For double hashing prefer prime table sizes and secondary hash in [1, m-1] so gcd(h2,m)=1. Always rehash on resize (rehash every element). If the objective is practical use rather than learning, prefer std::unordered_map.

Recommended Answers

All 2 Replies

Member Avatar for Belrog

Have a go at the design of an algorithm first - after you know what you want the code to do, the actual code will come easier.

Member Avatar for Ptolemy

>I know the theory behind it but i dont seem to be able to put it into code!
Then you don't really know the theory behind it. ;) Not to be rude or anything, but these are all pretty straightforward concepts and the code ends up being very short compared to other data structures. might help you get a feel for how things work in practice.

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.