hash_table.inl

采用迭代器模式实现hash算法

/******************************************
 * HASH 表迭代器实现
 *****************************************/

/**********************************
 * 赋值操作符
 *********************************/
template<typename KEY, typename ITEM>
HashIterator<KEY, ITEM>&
HashIterator<KEY, ITEM>::operator = (const Self& obj)
{
	if (this != &obj) {
		this->hash_table_ = obj.hash_table_;
		this->cur_node_   = obj.cur_node_;
	}
	return *this;
}
/**********************************
 * 比较操作符,等式
 *********************************/
template<typename KEY, typename ITEM>
bool
HashIterator<KEY, ITEM>::operator == (const Self& obj) const
{
	return (this->cur_node_ == obj.cur_node_);
}
/**********************************
 * 比较操作符,不等式
 *********************************/
template<typename KEY, typename ITEM>
bool
HashIterator<KEY, ITEM>::operator != (const Self& obj) const
{
	return (this->cur_node_ != obj.cur_node_);
}
/**********************************
 * 递增操作符类似++x
 * 如果下一个节点为空则找下一个桶
 *********************************/
template<typename KEY, typename ITEM>
HashIterator<KEY, ITEM>&
HashIterator<KEY, ITEM>::operator ++ (void)
{
	if (this->cur_node_->next_ == this->hash_table_->end_node () ){
		size_type pos  = this->hash_table_->get_key_num (this->cur_node_->item_.key_);
		pos %= this->hash_table_->bucket_size_;
		this->cur_node_ = this->hash_table_->end_node();
		for (++pos; pos < this->hash_table_->bucket_size_; pos++) {
			this->cur_node_ = this->hash_table_->buckets_[pos];
			if (this->hash_table_->buckets_[pos] != this->hash_table_->end_node() )
				break;
		}
	} else {
		this->cur_node_ = this->cur_node_->next_;
	}
	return *this;
}
/**********************************
 * 递增操作符,类似x++
 *********************************/
template<typename KEY, typename ITEM>
HashIterator<KEY, ITEM>
HashIterator<KEY, ITEM>::operator ++ (int)
{
	Self tmp = *this;
	operator ++ ();
	return tmp;
}
/**********************************
 * 指针操作符
 *********************************/
template<typename KEY, typename ITEM>
typename HashIterator<KEY, ITEM>::ItemPtr
HashIterator<KEY, ITEM>::operator -> (void) const
{
	return &(this->cur_node_->item_);
}
/**********************************
 * *操作符
 *********************************/
template<typename KEY, typename ITEM>
typename HashIterator<KEY, ITEM>::ItemRef
HashIterator<KEY, ITEM>::operator * (void)
{
	return (this->cur_node_->item_);
}





/******************************************
 * HASH 表实现
 *****************************************/

/**********************************
 * 缺省构造函数
 *********************************/
template<typename KEY, typename ITEM>
HashTable<KEY, ITEM>::HashTable(size_type buckets)
: bucket_size_(buckets), elements_(0)
{
	init_buckets();
}
/**********************************
 * 拷贝构造函数
 *********************************/
template<typename KEY, typename ITEM>
HashTable<KEY, ITEM>::HashTable(const Self& obj)
: bucket_size_(obj.bucket_size_), elements_(0)
{
	init_buckets();
	/*向桶内添加传递对象的元素*/
	insert (obj.begin (), obj.end() );
}
/**********************************
 * 析构函数
 *********************************/
template<typename KEY, typename ITEM>
HashTable<KEY, ITEM>::~HashTable()
{
	unini_buckets();
}
/**********************************
 * 赋值操作符
 *********************************/
template<typename KEY, typename ITEM>
HashTable<KEY, ITEM>&
HashTable<KEY, ITEM>::operator = (const Self& obj)
{
	clear();    //先清空元素
	/*如果桶的总数不相等,则释放原来的桶数组,重新构造新桶数组*/
	if (bucket_size_ != obj.bucket_size_) {
		delete [] buckets_;
		bucket_size_ = obj.bucket_size_;
		init_buckets();
	}
	/*向桶内添加传递对象的元素*/
	insert (obj.begin (), obj.end() );
	return *this;
}
/**********************************
 * 返回开始迭代器
 * 即第一个有元素桶的第一个元素
 * 如果没有任何元素则返回end迭代器
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::Iterator
HashTable<KEY, ITEM>::begin () const
{
	for (size_type n = 0; n < bucket_size_; n++)
		if (buckets_[n])
			return Iterator((Self*)this, buckets_[n]);
	return Iterator((Self*)this, end_node() );
}
/**********************************
 * 返回最后一个迭代器
 * 最后迭代器用NULL表示
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::Iterator
HashTable<KEY, ITEM>::end () const
{
	return Iterator ((Self*)this, end_node() );
}
/**********************************
 * 返回HASH表目前存放的元素总和
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::size () const
{
	return elements_;
}
/**********************************
 * 返回目前已经有内容的桶个数
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::bucket_count() const
{
	size_type sum = 0;
	/*计算有内容的桶*/
	for ( size_type n = 0; n < bucket_size_; n++)
		if (buckets_[n] != end_node() )
			sum++;
	return sum;
}
/**********************************
 * 返回指定桶中元素的个数
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::bucket_elems(size_type bucket) const
{
	size_type  sum  = 0;
	NodePtr node =buckets_[bucket % bucket_size_];
	for (; node != end_node() ; sum++, node = node->next_);
	return sum;
}
/**********************************
 * 返回KEY所处桶的位置
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::bucket_pos(const Key& key) const
{
	return (get_key_num(key) % bucket_size_);
}
/**********************************
 * 根据KEY向对应的桶内添加元素
 * 为了插入的效率,每次都插入到首元素
 * 成功时返回当前元素,否则end_node
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::Iterator
HashTable<KEY, ITEM>::insert (const Key& key, const Value& val)
{
	size_type  pos  = get_key_num(key) % bucket_size_;
	NodePtr node = create_node();
	node->item_.key_  = key;
	node->item_.val_  = val;
	node->next_ = buckets_[pos];
	buckets_[pos] = node;
	++elements_;
	return Iterator((Self*)this, node);
}
/**********************************
 * 向桶数组中连续插入元素
 * 成功时返回总数,否则-1
 *********************************/
template<typename KEY, typename ITEM>
void
HashTable<KEY, ITEM>::insert (const Iterator& first, const Iterator& last)
{
	for (Iterator it = first; it != last; it++)
		insert (it->key_, it->val_);
}
/**********************************
 * 根据KEY值查找桶中的元素
 * 首先根据KEY确定所处的桶
 * 再遍历桶中元素直到找到节点
 * 如果没找到则返回end
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::Iterator
HashTable<KEY, ITEM>::find (const Key& key) const
{
	size_type  pos  = get_key_num(key) % bucket_size_;
	NodePtr node = buckets_[pos];
	for (; node != end_node(); node = node->next_)
		if (node->item_.key_ == key )
			break;
	return Iterator((Self*)this, node);
}
/**********************************
 * 根据KEY从桶中删除一个元素
 * 删除方法和删除链表节点相似
 * 返回剩余的元素个数
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::erase (const Key& key)
{
	size_type  pos  = get_key_num(key) % bucket_size_;
	NodePtr node = buckets_[pos];
	NodePtr node_prev = 0;
	
	/*循环比对KEY值相等的元素*/
	for (; node != end_node(); node_prev = node, node = node->next_)
		if (node->item_.key_ == key ) {       //KEY值是否相等
			if (!node_prev)                  //删除节点
				buckets_[pos] = node->next_;
			else
				node_prev->next_ = node->next_;
			release_node (node);
			break;
		}
	return elements_;
}
/**********************************
 * 根据给定的迭代器删除对应位置的节点
 * 返回剩余的元素个数
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::erase (const Iterator& it)
{
	return erase(it->key_);
}
/**********************************
 * 根据给定迭代器的范围删除节点
 * 返回剩余的元素个数
 *********************************/
template<typename KEY, typename ITEM>
typename HashTable<KEY, ITEM>::size_type
HashTable<KEY, ITEM>::erase (const Iterator& first, const Iterator& last)
{
	for ( Iterator it = first, it2; it != last; ) {
		it2 = it++;
		erase (it2);
	}
	return elements_;
}
/**********************************
 * 清空所有的元素
 *********************************/
template<typename KEY, typename ITEM>
void
HashTable<KEY, ITEM>::clear ()
{
	erase ( begin (), end() );
}
/**********************************
 * 清空给定桶中的元素
 *********************************/
template<typename KEY, typename ITEM>
void
HashTable<KEY, ITEM>::clear_bucket(size_type bucket)
{
	for (NodePtr node = buckets_[bucket];
		buckets_[bucket] != end_node();
		buckets_[bucket] = buckets_[bucket]->next_, node = buckets_[bucket])
			release_node(node);
	return elements_;
}
/**********************************
 * 初始化桶
 * 根据总数构造桶,并初始化它
 *********************************/
template<typename KEY, typename ITEM>
void
HashTable<KEY, ITEM>::init_buckets()
{
	buckets_ = new NodePtr[bucket_size_];
	for (size_type n = 0; n < bucket_size_; buckets_[n] = end_node(), n++);
		
}
/**********************************
 * uninitialize桶
 * 先清空桶中的元素,再释放桶
 *********************************/
template<typename KEY, typename ITEM>
void
HashTable<KEY, ITEM>::unini_buckets()
{
	clear();
	delete [] buckets_;
}