#include <cstdint>
#include <type_traits>

namespace detail
{
    std::uint32_t const FNV_PRIME_32        = 16777619u;
    std::uint64_t const FNV_PRIME_64        = 1099511628211ull;

    std::uint32_t const FNV_OFFSETBASIS_32  = 2166136261u;
    std::uint64_t const FNV_OFFSETBASIS_64  = 14695981039346656037ull;

    template<unsigned Bits>
    struct FnvDefaultParams
    { };

    template<>
    struct FnvDefaultParams<32>
    {
        constexpr static std::uint32_t prime()
        {
            return FNV_PRIME_32;
        }

        constexpr static std::uint32_t offsetbasis()
        {
            return FNV_OFFSETBASIS_32;
        }
    };

    template<>
    struct FnvDefaultParams<64>
    {
        constexpr static std::uint64_t prime()
        {
            return FNV_PRIME_64;
        }

        constexpr static std::uint64_t offsetbasis()
        {
            return FNV_OFFSETBASIS_64;
        }
    };

    template<   typename UIntT,
                UIntT OffsetBasis = detail::FnvDefaultParams<sizeof(UIntT) * 8>::offsetbasis(),
                UIntT FnvPrime = detail::FnvDefaultParams<sizeof(UIntT) * 8>::prime()>
    UIntT fnv1a(std::uint8_t const* begin, std::uint8_t const* end)
    {
        static_assert(std::is_unsigned<UIntT>::value, "Hash must be an unsigned integer");

        UIntT hash = OffsetBasis;
        for(; begin != end; ++begin)
        {
            hash ^= *begin;
            hash *= FnvPrime;
        }
        return hash;
    }

    template<   typename UIntT,
                UIntT OffsetBasis = detail::FnvDefaultParams<sizeof(UIntT) * 8>::offsetbasis(),
                UIntT FnvPrime = detail::FnvDefaultParams<sizeof(UIntT) * 8>::prime()>
    UIntT fnv1a_zero(char const* begin)
    {
        static_assert(std::is_unsigned<UIntT>::value, "Hash must be an unsigned integer");

        UIntT hash = OffsetBasis;
        for(; *begin; ++begin)
        {
            hash ^= *begin;
            hash *= FnvPrime;
        }
        return hash;
    }

    std::uint32_t const HASHTABLE_PRIMES[] =
    {
        13, 29, 59, 121, 251, 503, 1009, 2027, 4057, 8117, 16249, 32503,
        65011, 130027, 260081, 520193, 1040387, 2080777, 4161557, 8323151,
        16646317, 33292687, 66585377, 133170769, 266341583, 532683227,
        1065366479, 2130732959, 4261465919
    };

    float const HASHTABLE_MAX_LOADFACTOR = 0.5;
}

#include <cstring>
#include <cmath>
#include <vector>
#include <cstddef>
#include <limits>
#include <memory>

template<typename CharT, typename ValueT>
class StringHashtable
{
private:
    struct Entry
    {
        size_t keyLength;
        Entry* next;
        ValueT value;
        CharT key[1];
    };

    unsigned _primeIndex;
    std::unique_ptr<Entry*[]> _buckets;
    size_t _size;

    template<typename Value2T>
    static Entry* makeEntry(CharT const* key, size_t keyLength, Value2T&& value)
    {
        auto const MAXA = std::numeric_limits<size_t>::max();
        if(MAXA / sizeof(CharT) < keyLength)
            throw std::bad_alloc();

        auto const keySize = keyLength * sizeof(CharT);
        auto const keyOffset = offsetof(Entry, key);
        if(MAXA - keyOffset < keySize)
            throw std::bad_alloc();

        Entry* data = (Entry*)std::malloc(keyOffset + keySize);
        if(!data)
            throw std::bad_alloc();
        data->keyLength = keyLength;
        data->next = nullptr;
        new(&data->value) ValueT(std::move(value));
        std::memcpy(data->key, key, keySize);
        return data;
    }

    static void destroyEntry(Entry* entry)
    {
        entry->value.~ValueT();
        std::free(entry);
    }

    static Entry* destroyEntryList(Entry* first)
    {
        Entry* cur = first;
        while(cur)
        {
            Entry* next = cur->next;
            destroyEntry(cur);
            cur = next;
        };
    }

    size_t bucketFor(CharT const* key, size_t keyLength) const
    {
        auto const data = (std::uint8_t const*)key;
        return detail::fnv1a<size_t>(data, data + keyLength * sizeof(CharT)) % bucketCount();
    }

    Entry* findEntry(CharT const* key, size_t keyLength, size_t bucketIndex)
    {
        if(!_buckets[bucketIndex])
            return nullptr;

        Entry* cur = _buckets[bucketIndex];
        do
        {
            if(keyLength == cur->keyLength)
            {
                auto const cmpResult = std::memcmp(key, cur->key, keyLength * sizeof(CharT));
                if(cmpResult == 0)
                    return cur;
            }
        } while(cur = cur->next);
        return nullptr;
    }

    template<typename Value2T>
    Entry* insertOrReturn(CharT const* key, size_t keyLength, Value2T&& value, bool* existed = nullptr)
    {
        size_t const bucketIndex = bucketFor(key, keyLength, bucketCount());
        Entry* entry = findEntry(key, keyLength, bucketIndex);
        if(entry)
        {
            if(existed)
                existed = true;
            return entry;
        }

        if(existed)
            existed = false;
        entry = makeEntry(key, keyLength, std::forward<Value2T>(value));
        insertEntry(entry, bucketIndex);
        return entry;
    }

    template<bool Rehash = true>
    void insertEntry(Entry* entry, size_t bucketIndex)
    {
        if(Rehash && float(_size) / bucketCount() > detail::HASHTABLE_MAX_LOADFACTOR)
            rehash();

        if(!_buckets[bucketIndex])
        {
            _buckets[bucketIndex] = entry;
            _buckets[bucketIndex]->next = nullptr;
        }
        else
        {
            Entry* old = _buckets[bucketIndex];
            _buckets[bucketIndex] = entry;
            _buckets[bucketIndex]->next = old;
        }
        ++_size;
    }

    void rehash()
    {
        StringHashtable newTable( (_primeIndex + 1) );
        for(size_t i = 0, count = bucketCount(); i != count; ++i)
        {
            Entry* curEntry = _buckets[i];
            while(curEntry)
            {
                Entry* next = curEntry->next;
                size_t const bucketIndex = newTable.bucketFor(curEntry->key, curEntry->keyLength);
                newTable.insertEntry<false>(curEntry, bucketIndex);
                curEntry = next;
            }
            _buckets[i] = nullptr;
        }
        swap(newTable);
    }

    size_t bucketCount() const
    {
        return detail::HASHTABLE_PRIMES[_primeIndex];
    }

public:
    StringHashtable(unsigned primeIndex = 0)
        : _primeIndex(primeIndex), _buckets(new Entry*[bucketCount()]), _size(0)
    {
        std::memset(_buckets.get(), 0, bucketCount() * sizeof(Entry*));
    }

    ~StringHashtable()
    {
        for(size_t i = 0, count = bucketCount(); i != count; ++i)
            destroyEntryList(_buckets[i]);
    }

    void swap(StringHashtable& other)
    {
        std::swap(_primeIndex, other._primeIndex);
        std::swap(_buckets, other._buckets);
        std::swap(_size, other._size);
    }

    ValueT& operator[](std::basic_string<CharT> const& key)
    {
        auto const bucket = bucketFor(key.data(), key.length());
        Entry* entry = findEntry(key.data(), key.length(), bucket);
        if(entry)
            return entry->value;
        entry = makeEntry(key.data(), key.length(), ValueT());
        insertEntry(entry, bucket);
        return entry->value;
    }

    bool contains(std::basic_string<CharT> const& key) const
    {
        auto const bucket = bucketFor(key.data(), key.length());
        return const_cast<StringHashtable*>(this)->findEntry(
            key.data(), key.length(), bucket) != nullptr;
    }

    size_t size() const
    {
        return _size;
    }
};

#include <fstream>
#include <iostream>

int main()
{
    std::vector<std::string> words;
    std::ifstream in("wordsEn.txt");
    std::string curWord;
    while(in >> curWord)
        words.push_back(curWord);
    std::cout << words.size() << " words read\n";

    {
        StringHashtable<char, int> ht(0);
        for(std::string const& word : words)
            ht[word] = 1;

        std::cout << ht.size() << " pushed into StringHashtable\n";

        for(std::string const& word : words)
            if(!ht.contains(word))
                std::cout << word << " not in StringHashtable!\n";

        for(std::string const& word : words)
            if(ht[word] != 1)
                std::cout << word << " fail! (" << ht[word] << ") ";
        std::cout << std::endl;

        ht["octavo"] = 1;
        std::cout << "octavo in StringHashtable: " << (ht.contains("octavo") ? "yes" : "no") << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
    }
}