template <class Value>
struct __hashtable_node {
	__hashtable_node* next;
    Value val;
};

template <class K, class V>
class HashTable {
	struct Elem {
		pair<K, V> _kv;
		State _state = EMPTY;
	};
public:
	Elem* Find(const K& key);
	bool Insert(const pair<K, V>& kv);
	bool Erase(const K& key);
private:
	vector<Elem> _table;
	size_t _n = 0;
};

/// @brief 標(biāo)記每個位置狀態(tài)
enum State {
    EMPTY,    // 空
    EXIST,    // 有數(shù)據(jù)
    DELETE    // 有數(shù)據(jù)，但已被刪除
};

/// @brief 哈希表的節(jié)點(diǎn)
struct Elem {
    pair<K, V> _kv;    // 存儲數(shù)據(jù)
    State _state;    // 存儲狀態(tài)    
};

/// @brief 查找指定 key
/// @param key 待查找節(jié)點(diǎn)的 key 值
/// @return 找到返回節(jié)點(diǎn)的指針，沒找到返回空指針
Elem* Find(const K& key) {
    if (_table.empty()) {
        return nullptr;
    }

    // 使用除留余數(shù)法的簡化版本，并沒有尋找質(zhì)數(shù)
    // 同時，該版本只能用于正整數(shù)，對于字符串等需使用其他散列函數(shù)
    size_t start = key % _table.size();	
    size_t index = start;
    size_t i = 1;

    // 直到找到空位置停止
    while (_table[index]._state != EMPTY) {
        if (_table[index]._state == EXIST && _table[index]._kv.first == key) {
            return &_table[index];
        }

        index = start + i;
        index %= _table.size();
        ++i;
        // 判斷是否重復(fù)查找
        if (index == start) {
			return nullptr;
        }
    }
    return nullptr;
}

/// @brief 插入節(jié)點(diǎn)
/// @param kv 待插入的節(jié)點(diǎn)
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
    // 檢查是否已經(jīng)存在
    Elem* res = Find(kv.first);
    if (res != nullptr) {
        return false;
    }

    // 看是否需要擴(kuò)容
    if (_table.empty()) {
        _table.resize(10);
    } else if (_n > 0.7 * _table.size()) {	// 變化一下負(fù)載因子計(jì)算，可以避免使用除法
        HashTable backUp;
        backUp._table.resize(2 * _table.size());
        for (auto& [k, s] : _table) {
            // C++ 17 的結(jié)構(gòu)化綁定
            // k 綁定 _kv，s 綁定 _state
            if (s == EXIST) {
                backUp.Insert(k);
            }
        }
        // 交換這兩個哈希表，現(xiàn)代寫法
        _table.swap(backUp._table);
    }

    // 將數(shù)據(jù)插入
    size_t start = kv.first % _table.size();
    size_t index = start;
    size_t i = 1;

    // 找一個可以插入的位置
    while (_table[index]._state == EXIST) {
        index = start + i;
        index %= _table.size();
        ++i;
    }
    _table[index]._kv = kv;
    _table[index]._state = EXIST;
    ++_n;
    return true;
}

/// @brief 刪除指定 key 值
/// @param key 待刪除節(jié)點(diǎn)的 key
/// @return 刪除成功返回 true，失敗返回 false
bool Erase(const K& key) {
    Elem* res = Find(key);
    if (res != nullptr) {
        res->_state = DELETE;
        --_n;
        return true;
    }
    return false;
}

template <class K, class V>
class HashTable {
	struct Elem {
		Elem(const pair<K, V>& kv) 
			: _kv(kv)
			, _next(nullptr)
		{}

		pair<K, V> _kv;
		Elem* _next;
	};
public:
	Elem* Find(const K& key);
	bool Insert(const pair<K, V>& kv);
	bool Erase(const K& key);
private:
	vector<Elem*> _table;
	size_t _n = 0;
};

/// @brief 哈希表的節(jié)點(diǎn)
struct Elem {
    Elem(const pair<K, V>& kv) 
        : _kv(kv)
            , _next(nullptr)
        {}

???????    pair<K, V> _kv;    // 存儲數(shù)據(jù)
    Elem* _next;    // 存在下一節(jié)點(diǎn)地址
};

/// @brief 查找指定 key
/// @param key 待查找節(jié)點(diǎn)的 key 值
/// @return 找到返回節(jié)點(diǎn)的指針，沒找到返回空指針
Elem* Find(const K& key) {
    if (_table.empty()) {
        return nullptr;
    }

    size_t index = key % _table.size();
    Elem* cur = _table[index];
    // 遍歷該位置鏈表
    while (cur != nullptr) {
        if (cur->_kv.first == key) {
            return cur;
        }
        cur = cur->_next;
    }
    return nullptr;
}

/// @brief 插入節(jié)點(diǎn)
/// @param kv 待插入的節(jié)點(diǎn)
/// @return 插入成功返回 true，失敗返回 false
bool Insert(const pair<K, V>& kv) {
    // 檢查是否已經(jīng)存在
    Elem* res = Find(kv.first);
    if (res != nullptr) {
        return false;
    }

    // 檢查是否需要擴(kuò)容
    if (_table.size() == _n) {
        vector<Elem*> backUp;
        size_t newSize = _table.size() == 0 ? 10 : 2 * _table.size();
        backUp.resize(newSize);

        // 遍歷原哈希表，將所有節(jié)點(diǎn)插入新表
        for (int i = 0; i < _table.size(); ++i) {
            Elem* cur = _table[i];
            while (cur != nullptr) {
                // 取原哈希表的節(jié)點(diǎn)放在新表上，不用重新申請節(jié)點(diǎn)
                Elem* tmp = cur->_next;
                size_t index = cur->_kv.first % backUp.size();
                cur->_next = backUp[index];
                backUp[index] = cur;
                cur = tmp;
            }
            _table[i] = nullptr;
        }
        _table.swap(backUp);
    }

    // 將新節(jié)點(diǎn)以頭插的方式插入
    size_t index = kv.first % _table.size();
    Elem* newElem = new Elem(kv);
    newElem->_next = _table[index];
    _table[index] = newElem;
    ++_n;
    return true;
}

/// @brief 刪除指定 key 值
/// @param key 待刪除節(jié)點(diǎn)的 key
/// @return 刪除成功返回 true，失敗返回 false
bool Erase(const K& key) {
    size_t index = key % _table.size();
    Elem* prev = nullptr;
    Elem* cur = _table[index];
    while (cur != nullptr) {
        if (cur->_kv.first == key) {
            if (prev == nullptr) {
                // 是該位置第一個節(jié)點(diǎn)
                _table[index] = cur->_next;
            } else {
                prev->_next = cur->_next;
            }
            delete cur;	// 釋放該節(jié)點(diǎn)
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}