C++哈希查找算法简单实现

文章正文

发布时间：2024-12-11 14:01

首先哈希算法主要是用来查找元素，效率非常快

原理：
散列表（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;
}

测试运行程序：

int _tmain(int argc, _TCHAR* argv[])
{
//HashTable *_Hash_ = new HashTable();
HashTable _Hash_;
_Map map_;
map_.key = 2;
map_.value = "demo";
_Map map_1;
map_1.key = 3;
map_1.value = "demsso";
_Map map_2;
map_2.key = 4;
map_2.value = "dss";
_Map map_3;
map_3.key = 5;
map_3.value = "cide";
_Hash_.addElement(map_);
_Hash_.addElement(map_2);
_Hash_.addElement(map_3);
_Hash_.addElement(map_1);
_Map demo = _Hash_.searchValue(5);
std::cout << demo.key << endl;
std::cout << demo.value << endl;
//delete _Hash_;
system("pause");
return 0;
}

运行结果：

C++哈希查找算法简单实现

标签