散列表： 本章介绍了散列表的各种问题。
散列函数：除法散列，乘法散列，全域散列。 其中除法散列是简单的mod. 乘法散列为h(k) = m(kA mod 1). 即关键字k乘常数A， 然后取小数部分， 乘以m. 全域散列是一组散列函数，这些函数都可以将关键字域U映射到相同的集合中， 同时对k, l 属于U. 满足h(k) = h(l)的散列函数的个数最多是: 散列函数的数目/集合的大小. 散列表的2种解决冲突的办法： 链接法和开放寻址法。链接法比较简单， 开发寻址法解决冲突的探查函数有几种： 线形探察， 二次探察， 双重散列。 其中双重探察的探察序列最多，所以相应散列效果更好。最后介绍了完全散列， 这节难度较大， 没有看太明白， 主要是对于全域散列的证明很头疼阿。我自己的链接法的实现： 因为很少用到散列， 所以只是做了少量的测试。 而且散列函数的返回值一定是int_type. 对于散列的应用了解少了点，所以模板参数的定义可能不是很合理。template <class Key, class Value, class Hash = HashDivide<Key> >class LinkHash{public: typedef Key key_type; typedef Value data_type; typedef std::pair<Key, Value> value_type; typedef value_type& value_reference; typedef const value_type& value_const_reference; typedef key_type& key_reference; typedef const key_type& key_const_reference; typedef value_type* value_pointer; typedef const value_type* value_const_pointer;
typedef LinkNode<value_type>* node_type;
LinkHash(int size) { m_container.assign(size, 0); m_size = 0; } ~LinkHash() { for (std::vector< node_type >::iterator it = m_container.begin(); it != m_container.end(); ++it) { node_type node = *it; while (node) { *it = node->next(); delete node; node = *it; } } }
size_t size() const {return m_size;}
data_type get(const key_type& key) { node_type node = find(key); if (node) { return node->value().second; } else { throw std::out_of_range("no key"); } }
bool insert(const key_type& key, const data_type& value) { return insert(value_type(key, value)); } bool insert(value_const_reference data) { node_type node = find(data.first); if (node) { node->value().second = data.second; return false; } else { node_type node = new LinkNode<value_type>(); node->m_data = data; node->m_next = m_container[hash(data.first)]; m_container[hash(data.first)] = node; ++m_size; return true; } }
bool has_key(const key_type& key) { node_type node = find(key); if (node) return true; else return false; }
bool erase(const key_type& key) { assert(hash(key)); int index = hash(key); if (index >= m_container.size()) { throw bucketNotEnough("bucket not enough"); } LinkNode<value_type> nodeImp; node_type node = &nodeImp; node->m_next = m_container[index]; while(node->next()) { if (node->next()->value().first == key) { node_type eraseNode = node->next(); node->m_next = node->next()->next(); delete eraseNode; --m_size; m_container[index] = node->m_next; return true; } node = node->next(); } return false; }
private:
node_type find(const key_type& key) { int index = hash(key); if (index >= m_container.size()) { throw bucketNotEnough("bucket not enough"); } node_type node = m_container[index]; while(node) { if (node->value().first == key) { return node; } node = node->next(); } return 0; }
int hash(const key_type& key) { return m_function(key) % m_container.size(); }
private: LinkHash(const LinkHash&); LinkHash& operator=(const LinkHash&); std::vector< node_type > m_container; Hash m_function; size_t m_size;};
