首先哈希算法主要是用来查找元素，效率非常快 原理： 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。（摘自百度） 快的原因：是因为通过key转换，代入函数，获得关键字的记录。实际还是看代码，代码比较好懂。 哈希表查找时间复杂度O（1），空间复杂度O（n）：牺牲空间复杂度，来实现查找的快速（还挺押韵） 示例代码（主要使用散列表的折叠法，其实只要懂原理，其实都好办这种）： 头文件部分
include "stdafx.h"
//哈希结果 enum HASH_RESULT_TYPE { FAIL, SUCCESS };
//构建类似Map的结构体：不使用std自带的方法 struct _Map{ int key; std::string value; _Map(){ //类似类的构造函数 key = 0; value = ""; } };
class Batch { public: Batch(){ m_index = -1; } int m_index;//当前位置 _Map m_map[100];//设置默认大小 };
class HashTable{ public: HashTable(); ~HashTable(); int hash(int _key);//进行哈希：获取key _Map searchValue(int _key); //查询 bool addElement(_Map _element);//添加元素到Hash表当中 private: Batch * m_batch[4]; };
实现部分：
// HashTable.cpp : 定义控制台应用程序的入口点。 // 哈希表算法实现
include "stdafx.h"
include "HashTable.h"
using namespace std;
HashTable::HashTable() { for (int i = 0; i < 5; i ) { m_batch[i] = new Batch(); } }
HashTable::~HashTable() { for(int j = 0; j < 4; j ) { delete m_batch[j]; } }
//每5个组合一下：加快查找效率 int HashTable::hash(int _key) { int key = _key % 4; return key; }
bool HashTable::addElement(_Map _element) { //获取位置 int key = hash(_element.key); int cur_pos = (m_batch[key]->m_index) 1; m_batch[key]->m_index = cur_pos; //添加相应元素 m_batch[key]->m_map[cur_pos].key = _element.key; m_batch[key]->m_map[cur_pos].value = _element.value; return true; }
//根据key 查找指定元素 _Map HashTable::searchValue(int _key) { int key = hash(_key); for (int i = 0; i < 100; i ) { if (m_batch[key]->m_map[i].key == _key) { return m_batch[key]->m_map[i]; } } _Map not_found_map; //没找到返回空值 return not_found_map; }
