class Solution {
public:
    int firstUniqChar(string s) {
        //桶思想
        vector<int> cnt(26,0);
        //統(tǒng)計次數(shù)
        for(auto i:s) cnt[i-'a']++;
        for(size_t i=0;i<s.size();i++) if(cnt[s[i]-'a']==1) return i;
        return -1;
    }
};

enum State{
    EXIST,EMPTY,DELETE
};
template<class K,class V>
struct HashData{
    pair<K,V> _kv;
    State _state=EMPTY;
};
 template<class K,class V>
 class HashTable{
 private:
    vector<HashData<K,V>> _tables;
    int _n;
 };

inline unsigned long __stl_next_prime(unsigned long n){
    //Note:assumes long is at least 32 bits
    static const int __stl_num_primes=28;
    static const unsigned long __stl_prime_list[__stl_num_primes]={
        53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
    };
    const unsigned long* first=__stl_prime_list;
    const unsigned long* last=__stl_prime_list+__stl_num_primes;
    const unsigned long* pos=lower_bound(first,last,n);
    return pos==last?*(last-1):*pos;
}

template<class K>
struct HashFunc{
    size_t operator()(const K& key){
        return (size_t)key;
    }
};
template<>
struct HashFunc<string>{
    size_t operator()(const string& s){
        //BKDR
        size_t hash=0;
        for(auto ch:s){
            hash+=ch;
            hash*=131;
        }
        return hash;
    }
};
template<class K,class V,class Hash=HashFunc<K>>
class HashTable{
private:
    vector<HashData<K,V>> _tables;
    int _n;
};

namespace open_address{
    template<class K,class V,class Hash=HashFunc<K>>
    class HashTable{
    public:
        HashTable()
            :_tables(__stl_next_prime(0))
            ,_n(0)
        {}
        bool Insert(const pair<K,V>& kv){
            if(Find(kv.first)){
                return false;
            }
            //負(fù)載因子>=0.7,擴容
            if(_n*10/_tables.size()>=0.7){
                //舊法，等于說把Insert接口的邏輯又實現(xiàn)了一遍
                // vector<HashData<K,V> nextables(_tables.size()*2);
                // for(auto& data:_tables){
                //     //舊表的數(shù)據(jù)映射到新表
                //     if(data._state==EXIST){
                //         size_t hash0=data._kv.first%newtables.size();
                //         //……
                //     }
                // }
                //現(xiàn)代寫法
                HashTable<K,V> newht;
                //newht._tables.resize(_tables.size()*2);
                newht._tables.resize(__stl_next_prime(_tables.size()+1));
                for(auto& data:_tables){
                    //舊表映射到新表
                    if(data._state==EXIST)
                        newht.Insert(data._kv);
                }
                _tables.swap(newht._tables);
            }
            size_t hash0=kv.first%_tables.size();
            size_t hash1=hash0;
            int i=1;
            int flag=1;
            while(_tables[hash1]._state==EXIST){
                //線性探測
                hash1=(hash0+i)%_tables.size();
                ++i;
                //二次探測
                /*hash1=(hash0+(i*i*flag))%_tables.size();
                if(hash1<_tables.size()){
                    hash1+=_tables.size();
                }
                if(flag==1)
                    flag=-1;
                else{
                    ++i;
                    flag=-1;
                }*/
            }
            _tables[hash1]._kv=kv;
            _tables[hash1]._state=EXIST;
            _n++;
            return false;
        }
        HashData<K,V>* Find(const K& key){
            size_t hash0=key%_tables.size();
            size_t hash1=hash0;
            int i=1;
            while(_tables[hash1]._state!=EMPTY){
                if(_tables[hash1]._kv.first==key&&_tables[hash1]._state==EXIST)
                    return &_tables[hash1];
                hash1=(hash0+i)%_tables.size();
                ++i;
            }
            return nullptr;
        }
        bool Erase(const K& key){
            HashData<K,V>* ret=Find(key);
            if(ret){
                ret->_state=DELETE;
                --_n;
                return true;
            }
            else return false;
        }
    private:
        vector<HashData<K,V>> _tables;
        int _n;
    };
}

namespace hash_bukect{
    template<class K,class V>
    struct HashNode{
        pair<K,V> _kv;
        HashNode<K,V>* _next;
        HashNode(const pair<K,V>& kv)
            :_kv(kv)
            ,_next(nullptr)
        {}
    };
    template<class K,class V,class Hash=HashFunc<K>>
    class HashTable{
        typedef HashNode<K,V> Node;
    public:
        HashTable()
            :_tables(11)
            ,_n(0)
        {}
        inline unsigned long __stl_next_prime(unsigned long n){
            //Note:assumes long is at least 32 bits
            static const int __stl_num_primes=28;
            static const unsigned long __stl_prime_list[__stl_num_primes]={
                53, 97, 193, 389, 769,
		        1543, 3079, 6151, 12289, 24593,
		        49157, 98317, 196613, 393241, 786433,
		        1572869, 3145739, 6291469, 12582917, 25165843,
		        50331653, 100663319, 201326611, 402653189, 805306457,
		        1610612741, 3221225473, 4294967291
            };
            const unsigned long* first=__stl_prime_list;
            const unsigned long* last=__stl_prime_list+__stl_num_primes;
            const unsigned long* pos=lower_bound(first,last,n);
            return pos==last?*(last-1):*pos;
        }
        bool Insert(const pair<K,V>& kv){
            //當(dāng)負(fù)載因子為1時，擴容
            if(_n==_tables.size()){
                //直接復(fù)用Insert，不好
                /*HashTable<K,V> newht;
                newht._tables.resize(_tables.size()*2);
                for(int i=0;i<_tables.size();i++){
                    Node* cur=_tables[i];
                    while(cur){
                        newht.Insert(cur);
                        cur=cur->_next;
                    }
                }
                _tables.swap(newht);*/
                HashTable<K,V> newht;
                newht._tables.resize(_tables.size()*2);
                //newht._tables.resize(__stl_next_prime(_tables.size()+1));
                for(int i=0;i<_tables.size();i++){
                    Node* cur=_tables[i];
                    while(cur){
                        Node* next=cur->_next;
                        size_t hash1=cur->_kv.first%newht._tables.size();
                        //頭插
                        cur->_next=newht[hash1];
                        newht[hash1]=cur;
                        cur=next;
                    }
                    _tables[i]=nullptr;
                }
                _tables.swap(newht);
            }
            //頭插
            size_t hash1=kv.first%_tables.size();
            Node* newNode=new Node(kv);
            newNode->next=_tables[hash1];
            _tables[hash1]=newNode;
            ++_n;
            return true;
        }
        Node* Find(const K& key){
            size_t hash0=key%_tables.size();
            Node* cur=_tables[hash0];
            while(cur){
                if(cur->_kv.first==key)
                    return cur;
                cur=cur->_next;
            }
            return nullptr;
        }
        bool Erase(const K& key){
            //沒有這個值
            if(!Find(key)) return false;
            size_t hash0=key%_tables.size();
            Node* cur=_tables[hash0];
            Node* prev=nullptr;
            while(cur){
                if(cur->_kv==key){
                    //刪除的節(jié)點是鏈表的頭
                    if(!prev){
                        _tables[hash0]=cur->_next;
                    }
                    else{
                        prev->_next=cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                prev=cur;
                cur=cur->_next;
            }
            return false;
        }
    private:
        vector<HashNode<K,V>*> _tables;
        size_t _n;
    };
}