哈希表hash table

哈希表也叫做散列表，采用直接寻址技术，用于在表中快速检索信息，所期望的复杂度为O(1)，散列表所要做的就是利用散列函数将关键字集合映射到表上，最好能建立键与下标的一一对应的关系，同时因为压缩了待处理的下标范围，因此可以有效降低空间开销。

选择哈希函数的标准是简单快速计算，而且在下标范围内最好能够出现键的平均分布。

1.哈希表的几种构造方法分别可以用截取，即忽略键的一部分，而用剩余部分直接作为下标，缺点是不能够在表中均匀的分布所要加入的键；

2.折叠法，将键划分为几个部分并采用一种方便的方式进行组合以得到下标，这样做的好处是键中的所有信息都能够影响函数的值，可以比截取法获得更好的下标分布；

3.模运算，取余数作为结果，很大程度上依赖于模的选择，模通常是质数，以保持均匀的分布键。

对于哈希表中开放地址的冲突解决方案，最简单的是线性探测，也就是从冲突地址开始，在表中顺序查找期望的空位置；还有一种是链式的冲突解决方案，将哈希表本身作为一个链表数组。用链接的方式解决冲突的好处是节省空间，并且简单有效的解决了冲突的问题，而且不会出现溢出的问题。

根据网上的代码自己写了一遍哈希表的代码，如下：

hashtable.h

#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_

typedef int KeyType;
const int NULLKEY = 0;

typedef struct {
	KeyType key;
	int order;
}NodeType;

class hashtable{
	public:
		int init_hashtable();
		void destory_hashtable();
		unsigned hash(KeyType k);
		void collision(int &p, int d);
		bool search_hash(KeyType k, int &p);
		int insert_hash(NodeType e);
		void traverse_hash();

	private:	
		NodeType *elem;
		int count;
		int size;
};

#endif

#include"hashtable.h"
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int hashtable::init_hashtable() { count = 0; elem = new NodeType[19]; if(!elem) { cout<<"哈希表创建失败！"<