Skip to content

Instantly share code, notes, and snippets.

@higuoxing
Created March 26, 2021 03:22
Show Gist options
  • Save higuoxing/56a0ab9c71afd9dd21147e697d578c77 to your computer and use it in GitHub Desktop.
Save higuoxing/56a0ab9c71afd9dd21147e697d578c77 to your computer and use it in GitHub Desktop.
Naive HashTable
#include <iostream>
#include <list>
#include <vector>
template <typename K, typename V> struct HashEntry {
K _key;
V _value;
};
template <typename K, typename V> struct Bucket {
std::list<HashEntry<K, V>> _list;
};
template <typename K, typename V> class HashTable {
static constexpr size_t _buckets_size = 200;
std::vector<Bucket<K, V>> _buckets;
size_t _size = 0;
public:
HashTable() { _buckets.resize(_buckets_size); }
size_t size() const;
void put(K &&key, V &&value);
bool contains(K &&key);
V *get(K &&key);
bool del(K &&key);
};
template <typename K, typename V> size_t HashTable<K, V>::size() const {
return _size;
}
template <typename T> static size_t hash(T &&k) { return std::hash<T>{}(k); }
template <typename K, typename V>
void HashTable<K, V>::put(K &&key, V &&value) {
size_t b_index = hash(std::forward<K>(key)) % _buckets_size;
HashEntry<K, V> he{key, value};
_buckets[b_index]._list.push_front(he);
++_size;
}
template <typename K, typename V> V *HashTable<K, V>::get(K &&key) {
size_t b_index = hash(std::forward<K>(key)) % _buckets_size;
if (!_buckets[b_index]._list.size())
return nullptr;
for (auto It = _buckets[b_index]._list.begin();
It != _buckets[b_index]._list.end(); ++It) {
if (It->_key == key)
return &It->_value;
}
return nullptr;
}
template <typename K, typename V> bool HashTable<K, V>::del(K &&key) {
size_t b_index = hash(std::forward<K>(key)) % _buckets_size;
if (!_buckets[b_index]._list.size())
return false;
auto B = _buckets[b_index]._list.begin();
auto E = _buckets[b_index]._list.end();
for (auto It = B; It != E; ++It) {
if (It->_key == key) {
_buckets[b_index]._list.erase(It);
--_size;
return true;
}
}
return false;
}
template <typename K, typename V> bool HashTable<K, V>::contains(K &&key) {
size_t b_index = hash(std::forward<K>(key)) % _buckets_size;
if (!_buckets[b_index]._list.size())
return false;
for (auto It = _buckets[b_index]._list.begin();
It != _buckets[b_index]._list.end(); ++It) {
if (It->_key == key)
return true;
}
return false;
}
int main() {
HashTable<std::string, std::string> ht;
ht.put("hello", "world");
std::cout << ht.size() << std::endl;
if (auto v = ht.get("hello")) {
std::cout << "hello: " << *v << std::endl;
} else {
std::cout << "hello: null" << std::endl;
}
if (ht.del("hello")) {
std::cout << "del: hello" << std::endl;
}
if (auto v = ht.get("hello")) {
std::cout << "hello: " << *v << std::endl;
} else {
std::cout << "hello: null" << std::endl;
}
std::cout << "size: " << ht.size() << std::endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment