Created
March 26, 2021 03:22
-
-
Save higuoxing/56a0ab9c71afd9dd21147e697d578c77 to your computer and use it in GitHub Desktop.
Naive HashTable
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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