哈希桶

基本结构

template<class T>
struct HashNode
{T _data;HashNode<T>* _next;
};
template<class K,class T,class KeyOfT>
class HashTable
{typedef HashNode<T> Node;
public:private:vector<Node*> _tables;size_t _num;
};

insert

bool Insert(const T& data)
{KeyOfT koft;size_t index = koft(data) % _tables.size();//1.看值在不在表中Node* cur = _tables[index];while (cur){if (koft(cur->_data) = koft(data)){return false;}else{cur = cur->_next;}}//2.头插到挂的链表中Node* newnode = new Node(data);newnode->_next = _tables[index];_tables[index] = newnode;++_num;return true;
}

增容

if (_tables.size() == _num)
{vector<Node*> newtables;size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;newtables.resize(newsize);for (size_t i = 0; i < _tables.size(); ++i){//1.开空间//2.重新计算数据位置//3.释放旧表Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t index = koft(cur->_data) % newtables.size();cur->_next = newtables[index];newtables[index] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);
}

增容只是空间大小发生了变化，_size并没有发生变化。

头插

find

Node* find(const K& key)
{KeyOfT koft;size_t index = key % _tables.size();Node* cur = _tables[index];while (cur){if (koft(cur->_data) == key){return cur;}elsecur = cur->_next;}return nullptr;
}

erase

bool Erase(const K& key)
{KeyOfT koft;size_t index = key % _tables.size();Node* prev = nullptr;Node* cur = _tables[index];while (cur){if (koft(cur->_data) == key){if (prev == nullptr){//删除的值在第一个节点_tables[index] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;
}