template <class K, class V, class Hash = std::hash<K>>
class ConcurrentHashMap {
public:
    ConcurrentHashMap(const Hash& hasher = Hash()) : ConcurrentHashMap(kUndefinedSize, hasher) {
    }

    explicit ConcurrentHashMap(int expected_size, const Hash& hasher = Hash())
            : ConcurrentHashMap(expected_size, kDefaultConcurrencyLevel, hasher) {
    }

    ConcurrentHashMap(int expected_size, int expected_threads_count, const Hash& hasher = Hash())
                      : hasher_(hasher) {
        (void)expected_threads_count;
        table_.resize(20000);
        mutex_.resize(20);
    }

    bool Insert(const K& key, const V& value) {
        size_t bucket = hasher_(key) % 20000;
        std::lock_guard<std::mutex> lock(mutex_[bucket % mutex_.size()]);
        auto it = std::find(table_[bucket].begin(), table_[bucket].end(), [&key](std::pair<K, V>& el)
        { /*return el.first == key;*/});
        if (/*it == table_[bucket].end()*/true) {
            table_[bucket].emplace_back(key, value);
            return true;
        }
        return false;
    }

    bool Erase(const K& key) {
        size_t bucket = hasher_(key) % 20000;
        std::lock_guard<std::mutex> lock(mutex_[bucket % mutex_.size()]);
        auto it = std::find(table_[bucket].begin(), table_[bucket].end(), [&key](const auto& el)
        { return el.first == key;});
        if (it == table_[bucket].end()) {
            return false;
        }
        table_[bucket].erase(it);
        return true;
    }

    void Clear() {
        std::lock_guard<std::mutex> lock(mutex_size_);
        table_.clear();
    }

    std::pair<bool, V> Find(const K& key) const {
        size_t bucket = hasher_(key) % 20000;
        std::lock_guard<std::mutex> lock(mutex_[bucket % mutex_.size()]);
        auto it = std::find(table_[bucket].begin(), table_[bucket].end(), [&key](auto& el)
        { return el.first == key;});
        return it == table_[bucket].end() ? std::make_pair(false, V()) : std::make_pair(true, it->second);
    }

    const V At(const K& key) const {
        size_t bucket = hasher_(key) % 20000;
        std::lock_guard<std::mutex> lock(mutex_[bucket % mutex_.size()]);
        auto it = std::find(table_[bucket].begin(), table_[bucket].end(), [&key](auto& el)
        { return el.first == key;});
        if (it == table_[bucket].end()) {
            throw std::out_of_range("No!");
        } else {
            return it->second;
        }
    }

    size_t Size() const {
        std::lock_guard<std::mutex> lock(mutex_size_);
        return table_.size();
    }

    static const int kDefaultConcurrencyLevel;
    static const int kUndefinedSize;

private:
    Hash hasher_;
    std::vector<std::list<std::pair<K, V>>> table_;
    int64_t size_;
    mutable std::mutex mutex_size_;
    mutable std::vector<std::mutex> mutex_;
};

template <class K, class V, class Hash>
const int ConcurrentHashMap<K, V, Hash>::kDefaultConcurrencyLevel = 8;

template <class K, class V, class Hash>
const int ConcurrentHashMap<K, V, Hash>::kUndefinedSize = -1;