Naive HashTable

naive-hashtable.cc

#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;
}