散列表
i. 散列函数
i. 冲突解决
ii. 分离链表法
ii. 开放地址法
iii. 线性探测法
iii. 平方探测法
iii. 双散列
ii. 再散列
ii. 可扩散列
i. 装填因子：元素个数 / 散列表大小
C++实现
1. 冲突解决：分离链表法
散列函数：key % tableSize
/*
散列函数： key % tableSize
冲突解决： 分离链表法
*/
#include <iostream>
#include <vector>
#include <list> using namespace std; typedef int value; class HashTable
{
public:
HashTable(unsigned size) : _size(size)
{
_table = new vector<list<value>* >(size); for (size_t i = ; i < _size; i++)
{
(*_table)[i] = new list<value>;
}
} void insert(value val)
{
(*_table)[ val % _size ]->push_back(val);
} value find(value val)
{
list<value>::const_iterator it = (*_table)[val % _size]->cbegin(); while (it != (*_table)[val % _size]->cend())
{
if (*it == val)
return *it; it++;
} return NULL;
} ~HashTable()
{
for (size_t i = ; i < _size; i++)
{
delete (*_table)[i];
} delete _table;
} private:
vector<list<value>* >* _table;
unsigned _size;
}; int main()
{
HashTable h(); h.insert();
h.insert( + ); cout << h.find( + ); return ;
}
2. 冲突解决：开放地址法 之 线性探测
散列函数：(key + collisionNum) % TableSize
装填因子：散列大小 > 元素个数 × 2
/*
冲突解决：开放地址法 之 线性探测
散列函数：(key + collisionNum) % TableSize
装填因子：散列大小 > 元素个数 × 2
*/ #include <iostream>
#include <vector> using namespace std; class HashTable
{
friend void dump(const HashTable&); public:
HashTable(size_t size = ) : _size(size)
{
_table = new vector<int>(_size); for (size_t i = ; i < _size; i++)
{
_table->operator[](i) = NULL;
}
} void insert(int val)
{
for (unsigned i = ; i < _size; i++)
{
if (_table->operator[](_hash(val, i)) == NULL)
{
_table->operator[](_hash(val, i)) = val; return;
}
}
} int find(int val) const
{
for (unsigned i = ; i < _size; i++)
{
if (_table->operator[](_hash(val, i)) == val)
{
return _table->operator[](_hash(val, i));
}
} return NULL;
} ~HashTable()
{
delete _table;
} private:
size_t _hash(size_t val, unsigned collision) const
{
return (val + collision) % _size; //散列函数 线性探测
} vector<int>* _table;
size_t _size;
}; void dump(const HashTable& h)
{
vector<int>::const_iterator it = h._table->cbegin(); while (it != h._table->cend())
{
cout << it - h._table->cbegin() << " " << *it++ << endl;
}
} int main()
{
HashTable h(); h.insert();
h.insert();
h.insert();
h.insert();
h.insert(); dump(h); cout << h.find() << endl;
cout << h.find() << endl; return ;
}
3. 冲突解决：开放地址法 之 平方探测
散列函数：(key + collisionNum ^ 2) % TableSize
装填因子：散列大小 > 元素个数 × 2
/*
冲突解决：开放地址法 之 平方探测
散列函数：(key + collisionNum ^ 2) % TableSize
装填因子：散列大小 > 元素个数 × 2
*/ #include <iostream>
#include <vector> using namespace std; class HashTable
{
friend void dump(const HashTable&); public:
HashTable(size_t size = ) : _size(size)
{
_table = new vector<int>(_size); for (size_t i = ; i < _size; i++)
{
_table->operator[](i) = NULL;
}
} void insert(int val)
{
for (unsigned i = ; i < _size; i++)
{
if (_table->operator[]( _hash(val, i)) == NULL)
{
_table->operator[]( _hash(val, i)) = val; return;
}
}
} int find(int val) const
{
for (unsigned i = ; i < _size; i++)
{
if (_table->operator[](_hash(val, i)) == val)
{
return _table->operator[](_hash(val, i));
}
} return NULL;
} ~HashTable()
{
delete _table;
} private:
size_t _hash(size_t val, unsigned collision) const
{
return (val + collision * collision) % _size; //散列函数，平方探测
} vector<int>* _table;
size_t _size;
}; void dump(const HashTable& h)
{
vector<int>::const_iterator it = h._table->cbegin(); while (it != h._table->cend())
{
cout << it - h._table->cbegin() << " " << *it++ << endl;
}
} int main()
{
HashTable h(); h.insert();
h.insert();
h.insert();
h.insert();
h.insert(); dump(h); cout << h.find() << endl;
cout << h.find() << endl; return ;
}