ハッシュテーブルなり.

hashtbl.hpp

template <class V>
class hashtbl {
  public:
    static constexpr std::size_t hash_size = 800;
    
  public:
    hashtbl() : data_() {}
    
    auto put(const std::string& key, const V& value) -> void {
        auto h = hash(key);
        if (data_[h].empty()) {
            data_[h].push_back(std::make_pair(key, value));
        } else {
            for (auto itr = std::begin(data_[h]); itr != std::end(data_[h]); itr++) {
                if (itr->first == key) {
                    itr->second = value;
                    return;
                }
            }
            data_[h].push_back(std::make_pair(key, value));
        }
    }
    
    auto get(const std::string& key) const -> V {
        auto h = hash(key);
        if (data_[h].empty()) {
            throw std::out_of_range("key is not found");
        } else {
            auto lst = data_[h];
            auto itr = (std::find_if(std::begin(lst), std::end(lst),
                                  [&key](const std::pair<std::string, V>& p) { return p.first == key; }));
            if (itr != std::end(lst)) {
                return itr->second;
            }
            throw std::out_of_range("key is not found");
        }
    }

    auto hash(const std::string& key) const -> int {
        auto len = key.size();
        auto tmp = static_cast<int>(key[0] + key[len -1] + key[(len - 1) / 2]);
        return tmp % data_.size();
    }
    
  private:
    std::array<std::list<std::pair<std::string, V>>, hash_size> data_;
};