C++

Forum

 
Initialization of hash table

chuuuing (20)
I'm trying to implement a hash table with vectors. Using separate chaining to solve the collision. Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
#include <cassert>
#include <iostream>
#include <list>
#include <optional>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>
#include <cmath>

using namespace std;

template <typename V> class myHashTable {

    // https://burtleburtle.net/bob/hash/integer.html
    /**
     * Simple 32 bit hash function
     * @param key
     * @return
     */
    static constexpr uint32_t hash(uint32_t key) {
        key = (key ^ 61) ^ (key >> 16);
        key = key + (key << 3);
        key = key ^ (key >> 4);
        key = key * 0x27d4eb2d;
        key = key ^ (key >> 15);
        return key;
    }

    // static const uint32_t hashBucket = pow(2.0, 4.0);
    static const uint32_t hashBucket = 16;

    struct Elem {
        uint32_t key;
        V value;
        Elem *next;
    };

    static std::vector<std::vector<Elem>> table;

public:
    /**
     * Constructor
     */
    myHashTable() {
        table.resize(hashBucket);
        cout << "The size of the table is " << sizeof(table) << "." << endl;
    }

    /**
     * Destructor
     */
    ~myHashTable() { clear(); }

    /**
     * insert value to HT if not exists
     *
     * used for non-overwriting inserts
     *
     * @param key
     * @param value
     */
    void insert(uint32_t key, V value) {
        if (!count(key)) {
            operator[](key) = value;
        }
    }

    /**
     * remove element from HT
     *
     * used for remove
     *
     * @param key
     */
    void erase(uint32_t key) {
        // ## INSERT CODE HERE
        uint32_t hashValue = myHashTable::hash(key);
        int position = 0;

        if (get(key).has_value()) {
            Elem *elem = &table[hashValue].front();
            while (elem->next != 0) {
                if (elem->key == key) {
                    table[hashValue].erase(table.at(hashValue).begin() + position);
                    return;
                };
                elem = elem->next;
                position++;
            }
        }
    }

    /**
     * get element from HT wrapped in optional
     *
     * used for const lookup
     *
     * @param key
     * @return optional containing the element or nothing if not exists
     */
    std::optional<V> get(uint32_t key) const {
        // ## INSERT CODE HERE
        uint32_t hashValue = myHashTable::hash(key);
        if (!count(key)) {  // if bucket is not empty
            Elem *elem = &table[hashValue].front();
            while (elem->next != 0) {
                if (elem->key == key) {
                    return elem->value;
                }
                elem = elem->next;
            }
        }
        // otherwise
        return std::nullopt;
    }

    /**
     * get reference to existing HT element or insert new at key
     *
     * used for lookups, inserts, and editing the HT elements
     *
     * @param key
     * @return reference to HT element
     */
    V &operator[](uint32_t key) {
        // ## INSERT CODE HERE
        uint32_t hashValue = myHashTable::hash(key);
        // if bucket is not empty
        if (!count(key)) {
            Elem *elem = &table[hashValue].front();
            while (elem->next != 0) {
                if (elem->key == key) {
                    return elem->value;
                }
                elem = elem->next;
            }
        }
        // if bucket is empty || the element doesnt exist in bucket
        table[hashValue].push_back({key, NULL});
        Elem last = table[hashValue].back();
        return last.value;
    }

    /**
     * get count of contained elements in one bucket[key]
     *
     * used for containment check
     *
     * @param key
     * @return 0 if not contained, 1 if contained??
     */
    uint64_t count(uint32_t key) const {
        // ## INSERT CODE HERE
        uint32_t hashValue = myHashTable::hash(key);
        int bucketSize = table[hashValue].size();
        return bucketSize;
    }

    /**
     * get number of stored element
     *
     * @return HT size
     */
    std::size_t size() const {
        // ## INSERT CODE HERE
        size_t htSize = 0;
        for (int i = 0; i < table.size(); ++i) {
                htSize += table[i].size();
        }
        return htSize;
    }

    /**
     * is HT empty
     *
     * @return true if HT empty
     */
    bool empty() const {
        // ## INSERT CODE HERE
        for (int i = 0; i < table.size(); i++) {
            if (table[i].size() != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * empty the HT
     */
    void clear() {
        // ## INSERT CODE HERE
        if (!empty()) {
            for (int i = 0; i < table.size(); i++) {
                // table.at(i).clear();
                table[i].clear();
            }
        }
    }
};


I got following error & warning info when running in CLion:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
 c++ -std=c++17 main.cpp 
main.cpp:57:9: warning: instantiation of variable 'myHashTable<unsigned int>::table' required here, but no definition is available [-Wundefined-var-template]
        table.resize(hashBucket);
        ^
main.cpp:246:5: note: in instantiation of member function 'myHashTable<unsigned int>::myHashTable' requested here
    HashTableTester() {
    ^
main.cpp:48:43: note: forward declaration of template entity is here
    static std::vector<std::vector<Elem>> table;
                                          ^
main.cpp:57:9: note: add an explicit instantiation declaration to suppress this warning if 'myHashTable<unsigned int>::table' is explicitly instantiated in another
      translation unit
        table.resize(hashBucket);
        ^
main.cpp:159:42: warning: implicit conversion of NULL constant to 'unsigned int' [-Wnull-conversion]
        table[hashValue].push_back({key, NULL});
                                   ~     ^~~~
                                         0
main.cpp:260:14: note: in instantiation of member function 'myHashTable<unsigned int>::operator[]' requested here
        myMap[key] = value;
             ^
main.cpp:161:16: warning: reference to stack memory associated with local variable 'last' returned [-Wreturn-stack-address]
        return last.value;
               ^~~~
3 warnings generated.
Undefined symbols for architecture x86_64:
  "myHashTable<unsigned int>::table", referenced from:
      myHashTable<unsigned int>::myHashTable() in main-72cd79.o
      myHashTable<unsigned int>::clear() in main-72cd79.o
      myHashTable<unsigned int>::empty() const in main-72cd79.o
      myHashTable<unsigned int>::operator[](unsigned int) in main-72cd79.o
      myHashTable<unsigned int>::count(unsigned int) const in main-72cd79.o
      myHashTable<unsigned int>::size() const in main-72cd79.o
      myHashTable<unsigned int>::get(unsigned int) const in main-72cd79.o
      ...
ld: symbol(s) not found for architecture x86_64
clang: error: linker command failed with exit code 1 (use -v to see invocation)
seeplus (6597)
 
 
 static std::vector<std::vector<Elem>> table;


That is a declaration, not a definition. table needs to be defined outside of the class but before the class is used (usually before main() ).
chuuuing (20)
hi seeplus,

thanks for your reply. The table should be empty in the beginning. How should I define it in this case?

Best,
Chuying
chuuuing (20)
If I use
static std::vector<std::vector<Elem>> table(hashBucket);
instead of
static std::vector<std::vector<Elem>> table;
I get a error of "Unknown type name 'hashBucket'" I dont know why...
seeplus (6597)
If you compile as C++17, the easiest way is to inline the static definitions as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 
#include <cassert>
#include <iostream>
#include <list>
#include <optional>
#include <random>
#include <string>
#include <unordered_map>
#include <vector>
#include <cmath>

using namespace std;

template <typename V> class myHashTable {

	// https://burtleburtle.net/bob/hash/integer.html
	/**
	 * Simple 32 bit hash function
	 * @param key
	 * @return
	 */
	static constexpr uint32_t hash(uint32_t key) {
		key = (key ^ 61) ^ (key >> 16);
		key = key + (key << 3);
		key = key ^ (key >> 4);
		key = key * 0x27d4eb2d;
		key = key ^ (key >> 15);
		return key;
	}

	// static const uint32_t hashBucket = pow(2.0, 4.0);
	inline static const uint32_t hashBucket = 16;

	struct Elem {
		uint32_t key;
		V value;
		Elem* next;
	};

	inline static std::vector<std::vector<Elem>> table;

public:
	/**
	 * Constructor
	 */
	myHashTable() {
		table.resize(hashBucket);
		cout << "The size of the table is " << sizeof(table) << "." << endl;
	}

	/**
	 * Destructor
	 */
	~myHashTable() { clear(); }

	/**
	 * insert value to HT if not exists
	 *
	 * used for non-overwriting inserts
	 *
	 * @param key
	 * @param value
	 */
	void insert(uint32_t key, V value) {
		if (!count(key)) {
			operator[](key) = value;
		}
	}

	/**
	 * remove element from HT
	 *
	 * used for remove
	 *
	 * @param key
	 */
	void erase(uint32_t key) {
		// ## INSERT CODE HERE
		uint32_t hashValue = myHashTable::hash(key);
		int position = 0;

		if (get(key).has_value()) {
			Elem* elem = &table[hashValue].front();
			while (elem->next != 0) {
				if (elem->key == key) {
					table[hashValue].erase(table.at(hashValue).begin() + position);
					return;
				};
				elem = elem->next;
				position++;
			}
		}
	}

	/**
	 * get element from HT wrapped in optional
	 *
	 * used for const lookup
	 *
	 * @param key
	 * @return optional containing the element or nothing if not exists
	 */
	std::optional<V> get(uint32_t key) const {
		// ## INSERT CODE HERE
		uint32_t hashValue = myHashTable::hash(key);
		if (!count(key)) {  // if bucket is not empty
			Elem* elem = &table[hashValue].front();
			while (elem->next != 0) {
				if (elem->key == key) {
					return elem->value;
				}
				elem = elem->next;
			}
		}
		// otherwise
		return std::nullopt;
	}

	/**
	 * get reference to existing HT element or insert new at key
	 *
	 * used for lookups, inserts, and editing the HT elements
	 *
	 * @param key
	 * @return reference to HT element
	 */
	V& operator[](uint32_t key) {
		// ## INSERT CODE HERE
		uint32_t hashValue = myHashTable::hash(key);
		// if bucket is not empty
		if (!count(key)) {
			Elem* elem = &table[hashValue].front();
			while (elem->next != 0) {
				if (elem->key == key) {
					return elem->value;
				}
				elem = elem->next;
			}
		}
		// if bucket is empty || the element doesnt exist in bucket
		table[hashValue].push_back({key, NULL});
		Elem last = table[hashValue].back();
		return last.value;
	}

	/**
	 * get count of contained elements in one bucket[key]
	 *
	 * used for containment check
	 *
	 * @param key
	 * @return 0 if not contained, 1 if contained??
	 */
	uint64_t count(uint32_t key) const {
		// ## INSERT CODE HERE
		uint32_t hashValue = myHashTable::hash(key);
		int bucketSize = table[hashValue].size();
		return bucketSize;
	}

	/**
	 * get number of stored element
	 *
	 * @return HT size
	 */
	std::size_t size() const {
		// ## INSERT CODE HERE
		size_t htSize = 0;
		for (int i = 0; i < table.size(); ++i) {
			htSize += table[i].size();
		}
		return htSize;
	}

	/**
	 * is HT empty
	 *
	 * @return true if HT empty
	 */
	bool empty() const {
		// ## INSERT CODE HERE
		for (int i = 0; i < table.size(); i++) {
			if (table[i].size() != 0) {
				return false;
			}
		}
		return true;
	}

	/**
	 * empty the HT
	 */
	void clear() {
		// ## INSERT CODE HERE
		if (!empty()) {
			for (int i = 0; i < table.size(); i++) {
				// table.at(i).clear();
				table[i].clear();
			}
		}
	}
};

int main()
{
	myHashTable<int> mht;
}


This compiles OK with VS2019 as C++17.
Last edited on
Topic archived. No new replies allowed.