Hash Table

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
int main() {
5
    ios::sync_with_stdio(false);
6
    cin.tie(nullptr);
7
8
    // Example: frequency counting with unordered_map
9
    unordered_map<string, int> freq;
10
11
    // Tuning: reserve enough buckets to avoid many rehashes
12
    // Suppose we expect up to 100000 distinct words
13
    freq.reserve(100000);
14
    freq.max_load_factor(0.7f); // keep chains short
15
16
    vector<string> words = {"apple","banana","apple","pear","banana","apple"};
17
    for (const auto &w : words) {
18
        // operator[] inserts if missing, then increments
19
        ++freq[w];
20
    }
21
22
    // Query: check membership without inserting using find/contains
23
#if __cplusplus >= 202002L
24
    bool has_orange = freq.contains("orange");
25
#else
26
    bool has_orange = (freq.find("orange") != freq.end());
27
#endif
28
29
    cout << "has_orange? " << (has_orange ? "yes" : "no") << "\n";
30
31
    // Iterate and print frequencies
32
    for (auto &kv : freq) {
33
        cout << kv.first << ": " << kv.second << "\n";
34
    }
35
36
    // unordered_set example: membership only
37
    unordered_set<long long> seen;
38
    seen.reserve(1000);
39
    seen.insert(10);
40
    seen.insert(20);
41
    cout << (seen.count(10) ? "present" : "absent") << "\n";
42
43
    // Introspection: bucket_count and load_factor
44
    cout << "bucket_count: " << freq.bucket_count() << " load_factor: " << freq.load_factor() << "\n";
45
46
    return 0;
47
}
48

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// A strong 64-bit mixer: splitmix64
5
static uint64_t splitmix64(uint64_t x) {
6
    x += 0x9e3779b97f4a7c15ULL;
7
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
8
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
9
    return x ^ (x >> 31);
10
}
11
12
struct custom_hash {
13
    // Random seed to defeat adversarial inputs
14
    const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
15
16
    // Hash for 64-bit integers
17
    size_t operator()(uint64_t x) const noexcept {
18
        return (size_t)splitmix64(x + FIXED_RANDOM);
19
    }
20
21
    // Overload for signed long long
22
    size_t operator()(long long x) const noexcept {
23
        return (*this)((uint64_t)x);
24
    }
25
26
    // Hash combine helper
27
    size_t combine(size_t a, size_t b) const noexcept {
28
        // Similar to boost::hash_combine but with extra mixing
29
        uint64_t res = a;
30
        res ^= b + 0x9e3779b97f4a7c15ULL + (res << 6) + (res >> 2);
31
        return (size_t)splitmix64(res + FIXED_RANDOM);
32
    }
33
34
    // Hash for pair<T,U>
35
    template<class T, class U>
36
    size_t operator()(const pair<T,U>& p) const noexcept {
37
        size_t h1 = (*this)((uint64_t)std::hash<T>{}(p.first));
38
        size_t h2 = (*this)((uint64_t)std::hash<U>{}(p.second));
39
        return combine(h1, h2);
40
    }
41
42
    // Hash for vector<int> (illustrative; for other types, generalize)
43
    size_t operator()(const vector<int>& v) const noexcept {
44
        size_t h = 0;
45
        for (int x : v) {
46
            size_t hx = (*this)((uint64_t)(uint32_t)x);
47
            h = combine(h, hx);
48
        }
49
        return h;
50
    }
51
};
52
53
int main() {
54
    ios::sync_with_stdio(false);
55
    cin.tie(nullptr);
56
57
    // Using pair<int,int> as a key
58
    unordered_map<pair<int,int>, int, custom_hash> grid_cost;
59
    grid_cost.reserve(1 << 16);
60
61
    grid_cost[{1,2}] = 5;
62
    grid_cost[{2,3}] = 7;
63
    cout << grid_cost[{1,2}] << "\n"; // 5
64
65
    // Using vector<int> as a key
66
    unordered_map<vector<int>, string, custom_hash> pattern_name;
67
    pattern_name.reserve(1024);
68
    pattern_name[{1,2,3}] = "seq123";
69
    pattern_name[{2,3,5,7}] = "primes";
70
    cout << pattern_name[{2,3,5,7}] << "\n";
71
72
    // Anti-hash: show that many equal hashes won't easily occur with random seed
73
    unordered_set<long long, custom_hash> us;
74
    us.reserve(100000);
75
    for (long long i = 0; i < 100000; ++i) us.insert(i * 1000003LL);
76
    cout << "size: " << us.size() << "\n"; // Should be 100000
77
78
    return 0;
79
}
80

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
class LinearProbingHash {
5
    // States for each slot
6
    enum State : uint8_t { EMPTY = 0, FILLED = 1, DELETED = 2 };
7
8
    struct Slot {
9
        long long key = 0;
10
        State state = EMPTY;
11
    };
12
13
    vector<Slot> table;
14
    size_t n = 0;              // number of FILLED keys
15
    double max_alpha = 0.7;    // rehash threshold
16
17
    static inline uint64_t splitmix64(uint64_t x) {
18
        x += 0x9e3779b97f4a7c15ULL;
19
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
20
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
21
        return x ^ (x >> 31);
22
    }
23
24
    size_t H(long long x) const {
25
        // Simple 64-bit mixing, then map into table size
26
        return (size_t)(splitmix64((uint64_t)x)) & (table.size() - 1);
27
    }
28
29
    void rehash(size_t new_m) {
30
        // new_m must be a power of two for &-masking to work
31
        vector<Slot> old = move(table);
32
        table.assign(new_m, {});
33
        n = 0;
34
        for (const auto &s : old) if (s.state == FILLED) insert(s.key);
35
    }
36
37
    void maybe_grow() {
38
        if ((double)n / (double)table.size() > max_alpha) {
39
            rehash(table.size() * 2);
40
        }
41
    }
42
43
public:
44
    explicit LinearProbingHash(size_t m = 8) {
45
        // Round up m to power of two
46
        size_t pw = 1;
47
        while (pw < m) pw <<= 1;
48
        table.assign(pw, {});
49
    }
50
51
    bool insert(long long key) {
52
        maybe_grow();
53
        size_t m = table.size();
54
        size_t i = H(key);
55
        size_t first_deleted = SIZE_MAX;
56
        while (true) {
57
            if (table[i].state == EMPTY) {
58
                size_t pos = (first_deleted != SIZE_MAX ? first_deleted : i);
59
                table[pos].key = key;
60
                table[pos].state = FILLED;
61
                ++n;
62
                return true; // inserted new
63
            } else if (table[i].state == DELETED) {
64
                if (first_deleted == SIZE_MAX) first_deleted = i; // remember first tombstone
65
            } else if (table[i].state == FILLED && table[i].key == key) {
66
                return false; // already present
67
            }
68
            i = (i + 1) & (m - 1); // linear probing with wrap-around
69
        }
70
    }
71
72
    bool contains(long long key) const {
73
        size_t m = table.size();
74
        size_t i = H(key);
75
        while (true) {
76
            if (table[i].state == EMPTY) return false; // stop at empty slot
77
            if (table[i].state == FILLED && table[i].key == key) return true;
78
            i = (i + 1) & (m - 1);
79
        }
80
    }
81
82
    bool erase(long long key) {
83
        size_t m = table.size();
84
        size_t i = H(key);
85
        while (true) {
86
            if (table[i].state == EMPTY) return false;
87
            if (table[i].state == FILLED && table[i].key == key) {
88
                table[i].state = DELETED; // tombstone to preserve probe chains
89
                --n;
90
                return true;
91
            }
92
            i = (i + 1) & (m - 1);
93
        }
94
    }
95
96
    size_t size() const { return n; }
97
    size_t capacity() const { return table.size(); }
98
};
99
100
int main() {
101
    ios::sync_with_stdio(false);
102
    cin.tie(nullptr);
103
104
    LinearProbingHash hs;
105
    for (int i = 0; i < 10; ++i) hs.insert(i * 3);
106
107
    cout << "contains 9? " << (hs.contains(9) ? "yes" : "no") << "\n";
108
    cout << "contains 12? " << (hs.contains(12) ? "yes" : "no") << "\n";
109
    cout << "size: " << hs.size() << " capacity: " << hs.capacity() << "\n";
110
111
    hs.erase(9);
112
    cout << "contains 9 after erase? " << (hs.contains(9) ? "yes" : "no") << "\n";
113
114
    return 0;
115
}
116

1
#include <bits/stdc++.h>
2
#include <ext/pb_ds/assoc_container.hpp>
3
using namespace std;
4
using namespace __gnu_pbds;
5
6
static uint64_t splitmix64_u(uint64_t x) {
7
    x += 0x9e3779b97f4a7c15ULL;
8
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
9
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
10
    return x ^ (x >> 31);
11
}
12
13
struct fast_hash {
14
    const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count();
15
    size_t operator()(uint64_t x) const { return (size_t)splitmix64_u(x + SEED); }
16
    size_t operator()(long long x) const { return operator()((uint64_t)x); }
17
};
18
19
int main() {
20
    ios::sync_with_stdio(false);
21
    cin.tie(nullptr);
22
23
    // gp_hash_table<Key, Mapped, Hash>
24
    gp_hash_table<long long, int, fast_hash> mp;
25
    mp.resize(1 << 16); // pre-allocate buckets
26
27
    // Example: count occurrences
28
    vector<long long> a = {1,2,3,2,1,4,5,2,1};
29
    for (auto x : a) mp[x]++;
30
31
    cout << "count(2) = " << mp[2] << "\n";
32
33
    // Membership-style container: value-less map (mapped type = null_type)
34
    gp_hash_table<long long, null_type, fast_hash> st;
35
    st.resize(1 << 16);
36
    st.insert(10);
37
    st.insert(20);
38
    cout << (st.find(10) != st.end() ? "present" : "absent") << "\n";
39
40
    return 0;
41
}
42