【数据结构】散列表

//对于字符串类型char*的函数的转换函数
inline size_t __stl_hash_string(const char* s)
{
  unsigned long h = 0; 
  for ( ; *s; ++s)
    h = 5*h + *s;
  
  return size_t(h);
}

__STL_TEMPLATE_NULL struct hash<char*>
{
  size_t operator()(const char* s) const { return __stl_hash_string(s); }
};

__STL_TEMPLATE_NULL struct hash<const char*>
{
  size_t operator()(const char* s) const { return __stl_hash_string(s); }
};

__STL_TEMPLATE_NULL struct hash<char> {
  size_t operator()(char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned char> {
  size_t operator()(unsigned char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<signed char> {
  size_t operator()(unsigned char x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
  size_t operator()(short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
  size_t operator()(unsigned short x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
  size_t operator()(int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
  size_t operator()(unsigned int x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
  size_t operator()(long x) const { return x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
  size_t operator()(unsigned long x) const { return x; }
};

散列表插入元素（元素值不允许重复）

  //插入元素，元素值不允许重复
  pair<iterator,bool> insert_unique(const value_type& obj)
  {
    resize(num_elements + 1);   //判断是否需要重建表格
    return insert_unique_noresize(obj);   //插入元素，键值不允许重复
  }

//判断是否需要重建表格
template <class V,class K,class HF,class Ex,class Eq,class A>
void hashtable<V,K,HF,Ex,Eq,A>::resize(size_type num_elements_hint)
{
  const size_type old_n = buckets.size();		//buckets中的表格大小
  if (num_elements_hint > old_n) {		//现有的元素个数大于以前的表格大小时
    const size_type n = next_size(num_elements_hint);		//找到下一个新的质数
    if (n > old_n) {
      vector<node*,A> tmp(n,(node*) 0);       //创建新的bucket
      __STL_TRY {
        for (size_type bucket = 0; bucket < old_n; ++bucket) {  //旧的
          node* first = buckets[bucket];		//节点的本身
          while (first) {
            size_type new_bucket = bkt_num(first->val,n);		//计算新的插入位置，因为n改变了
            buckets[bucket] = first->next;			//旧的散列表先指向下一个元素
            first->next = tmp[new_bucket];			//first指向新的散列表中元素指针
            tmp[new_bucket] = first;				    //新的散列表指向first
            first = buckets[bucket];				    //再次指向旧的散列表的指针
          }
        }
        buckets.swap(tmp);      //交换
      }
  }
}

//在不需要重建表格的情况下，元素值是不允许重复的
template <class V,class A>
pair<typename hashtable<V,A>::iterator,bool> 
hashtable<V,A>::insert_unique_noresize(const value_type& obj)
{
  const size_type n = bkt_num(obj);   //计算插入的位置
  node* first = buckets[n];       

  for (node* cur = first; cur; cur = cur->next) 
    if (equals(get_key(cur->val),get_key(obj)))	//元素值是不允许相同的
      return pair<iterator,bool>(iterator(cur,this),false);

  node* tmp = new_node(obj);	//产生新的节点
  tmp->next = first;			//指向头元素
  buckets[n] = tmp;				//表中指针指向tmp
  ++num_elements;			  	//更新节点的个数
  return pair<iterator,bool>(iterator(tmp,true);
}

散列表插入元素（元素值允许重复）

  iterator insert_equal(const value_type& obj)
  {
    resize(num_elements + 1);   //是否重建表格
    return insert_equal_noresize(obj);  //插入元素，元素值可以重复
  }

//允许元素值重复
template <class V,class A>
typename hashtable<V,A>::iterator 
hashtable<V,A>::insert_equal_noresize(const value_type& obj)
{
  const size_type n = bkt_num(obj);   //找到插入位置
  node* first = buckets[n];

  for (node* cur = first; cur; cur = cur->next) 
    if (equals(get_key(cur->val),get_key(obj))) {  //相等时
      
	   //马上插入，并返回
	    node* tmp = new_node(obj);
      tmp->next = cur->next;    //指向相等元素的下一个指向
      cur->next = tmp;          //相等元素指向新的插入
      ++num_elements;
      return iterator(tmp,this);
    }

  //插入新的元素，元素值并没有重复
  node* tmp = new_node(obj);
  tmp->next = first;
  buckets[n] = tmp;
  ++num_elements;
  return iterator(tmp,this);
}

查找元素

  //找到某个键值
  iterator find(const key_type& key) 
  {
    size_type n = bkt_num_key(key);   //找到插入位置
    node* first;
    for ( first = buckets[n];         //从首指针开始查找判断
          first && !equals(get_key(first->val),key);	//判断键值相同的
          first = first->next)
      {}
    return iterator(first,this);
  } 

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!