【数据结构】散列表

? ? ??散列表是典型的以空间换取时间的数据结构；它在插入、删除、查找操作上也具有常数平均时间的表现，但是这种表现是以统计为基础的；

基本知识

（1）负载系数，指元素的个数除以表格大小，除非采用开链法（拉链法），否则负载系数应该在0~1之间；

（2）对应像字符串类型、float这样的类型，如何映射到表上，这时候使用散列函数hash function；hash function带来的问题是可能有不同的元素被映射到相同的位置，这是无法避免的，因为元素的个数有可能会大于表的大小，这就是碰撞问题；如nginx中有这样一个散列函数：

#define ngx_hash(key,c)   ((ngx_uint_t) key * 31 + c)

//求槽的位置
ngx_uint_t
ngx_hash_key(u_char *data,size_t len)
{
    ngx_uint_t  i,key;

    key = 0;

    for (i = 0; i < len; i++) {
        key = ngx_hash(key,data[i]);	//key的循环利用
    }

    return key;
}

（3）解决碰撞的问题，线性探测（线性探测是逐个往下找，遇到惰性删除记号或空元素即可；因此要求表格足够大，但是该假设比较不符合实际，会带来一次群集问题）；二次探测（H为计算的槽位置，二次探测是使用H＋1^2,?H-1^2,?H＋2^2,?H-2^2,......H+i^2,?.H-i^2；但是也会带来二次群集的问题）；

（4）在nginx中散列表的建立会预先采用探测的方法来计算合适的表大小，因为nginx中的散列表不支持删除，只能够一次性创建，能够利用探测的方法计算出合适的空间大小；详情请见nginx专题中的hash的介绍；

（5）采用开链法，对每一个槽对于冲突的元素建立一个链表，只要链表足够短，速度还是够快的；在stl中，对于元素个数过多时，会动态调整表的大小，使得冲突的链表元素尽可能小；采用开链法，表格的负载系数将会大于1；

代码分析

（本节选取stl中hashtable的相关代码进行分析）

表格的质数表

static const int __stl_num_primes = 28;
//先将28个质数计算好
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,97,193,389,769,1543,3079,6151,12289,24593,49157,98317,196613,393241,786433,1572869,3145739,6291469,12582917,25165843,50331653,100663319,201326611,402653189,805306457,1610612741,3221225473ul,4294967291ul
};

说明几点

（1）在stl中，表格的大小选取为一个最靠近某个数，并大于等于某个数的质数；通过上述表格来获取，总共有28个质数；

获得合适的表格大小

inline unsigned long __stl_next_prime(unsigned long n)
{
  const unsigned long* first = __stl_prime_list;
  const unsigned long* last = __stl_prime_list + __stl_num_primes;
  const unsigned long* pos = lower_bound(first,last,n);   //找到的是第一个小于等于n的某个质数，若n不存在，返回一个不小于n的元素
  return pos == last ? *(last - 1) : *pos;		//先判别pos是否与last相等，相等则返回最后一个质数，否则返回相应位置的质数
}

桶节点

//这个是hashtable的桶所维护的节点
template <class Value>
struct __hashtable_node
{
  __hashtable_node* next;   //连接下一个桶
  Value val;                //元素值
};  

  //创建节点
  node* new_node(const value_type& obj)			//节点空间配置
  {
    node* n = node_allocator::allocate();		//申请一块内存
    n->next = 0;
    __STL_TRY {
      construct(&n->val,obj);		//构造
      return n;
    }
    __STL_UNWIND(node_allocator::deallocate(n));
  }
  
  //删除节点
  void delete_node(node* n)			//节点空间释放
  {
    destroy(&n->val);
    node_allocator::deallocate(n);
  }

hastable中的表结构

  typedef __hashtable_node<Value> node;

  vector<node*,Alloc> buckets;		//buckets是以vector来做桶的

构造散列表

  //hashtable的构造函数
  hashtable(size_type n,const HashFcn&    hf,const EqualKey&   eql)
    : hash(hf),equals(eql),get_key(ExtractKey()),num_elements(0)
  {
    initialize_buckets(n);
  }

  size_type next_size(size_type n) const { return __stl_next_prime(n); }    //获得表的大小

  void initialize_buckets(size_type n)
  {
    const size_type n_buckets = next_size(n);		//知道合适的表大小
    buckets.reserve(n_buckets);			            //创建表
    buckets.insert(buckets.end(),n_buckets,(node*) 0);  //每一个表插入节点，为空指针
    num_elements = 0;                            //元素的个数为0
  }

说明几点

（1）buckets中插入的元素为NULL指针；

判断元素的插入位置

  size_type bkt_num_key(const key_type& key) const
  {
    return bkt_num_key(key,buckets.size());
  }

  //只接受实值
  size_type bkt_num(const value_type& obj) const
  {
    return bkt_num_key(get_key(obj));
  }

  size_type bkt_num_key(const key_type& key,size_t n) const
  {
    return hash(key) % n;		//SGI所有内建的hash()
  }

  //接受实值和buckets个数
  size_type bkt_num(const value_type& obj,size_t n) const
  {
    return bkt_num_key(get_key(obj),n);
  }

散列函数

//对于字符串类型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);
  } 

删除元素

//删除所有与节点键值相同的元素
template <class V,A>::size_type 
hashtable<V,A>::erase(const key_type& key)
{
  const size_type n = bkt_num_key(key);     //找到插入位置
  node* first = buckets[n];     //第一个元素的指针
  size_type erased = 0;

  if (first) {
    node* cur = first;    //当前指针，首指针先跳过
    node* next = cur->next; //下一个指针
    while (next) {  //下一个元素和key来比
      if (equals(get_key(next->val),key)) {    //节点的键值相同
        cur->next = next->next;   //先改变当前指针的指向
        delete_node(next);        //删除
        next = cur->next;         //next
        ++erased;
        --num_elements;
      }
      else {
        cur = next;         
        next = cur->next;  
      }
    }
    if (equals(get_key(first->val),key)) { //若首指针也相同，也要删除
      buckets[n] = first->next;     //buckets指向下一个
      delete_node(first);           //删除
      ++erased;
      --num_elements;
    }
  }
  return erased;
}