【数据结构】散列表

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

基本知识

（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);
  }

散列函数

（编辑：ASP站长网）