3.2 基本的哈希表实现

哈希表是一种数据结构，通过哈希函数快速定位存储值。

第二章：经典哈希函数——一座算法的博物馆

哈希算法的发展历程中，涌现出许多经典的哈希函数，每一种都为不同的场景提供了解决方案：

1. 简单哈希函数：
   最简单的哈希函数基于数学取模（Modulo）的方式，例如：
   h(x)=x mod m
   它适用于简单场景，例如将数据均匀分布到固定数量的桶中。

   3.1 哈希函数的基本实现

   哈希函数的核心目标是将任意输入映射为固定长度的输出值。一个简单的哈希函数示例如下：

   #include<iostream>#include<string>usingnamespacestd;// 简单的哈希函数：字符求和并取模intsimpleHash(string key,inttableSize){inthashValue =0;for(charc :key){hashValue +=c;// 累加ASCII值}returnhashValue %tableSize;// 取模以映射到哈希表大小}intmain(){string key ="hash";inttableSize =10;cout <<"Hash value of ""<<key <<"": "<<simpleHash(key,tableSize)<<endl;return0;}

   输出：

   Hash value of “hash”: 9

   代码解释：

   • simpleHash 是一个简单的哈希函数，它将字符串中的每个字符的 ASCII 值累加起来。
   • 删除（Delete）：查找到索引后删除对应的值。
   • 链地址法：当两个键映射到同一个索引时，将它们存储在该桶（Bucket）中的链表中，解决哈希冲突。
   • 开放地址法：通过线性探测或二次探测寻找空闲位置。

     第一章：哈希的本质——化繁为简的魔法

     哈希算法的核心思想是将任意长度的数据映射到固定长度的值，称之为哈希值（Hash Value）或散列值。以下是一个简单实现：

     #include<iostream>#include<unordered_map>#include<list>usingnamespacestd;// LRU缓存类classLRUCache{private:intcapacity;// 缓存容量list<int>keys;// 存储键的顺序unordered_map<int,pair<int,list<int>::iterator>>cache;// 哈希表存储键值对及其迭代器public:LRUCache(intcap):capacity(cap){}intget(intkey){if(cache.find(key)==cache.end())return-1;// 缓存未命中// 缓存命中：将键移到列表前keys.erase(cache[key].second);keys.push_front(key);cache[key].second =keys.begin();returncache[key].first;}voidput(intkey,intvalue){if(cache.find(key)!=cache.end()){// 键已存在，更新值并移动到前keys.erase(cache[key].second);}elseif(keys.size()==capacity){// 缓存已满，移除最近最少使用的键intoldKey =keys.back();keys.pop_back();cache.erase(oldKey);}keys.push_front(key);cache[key]={value,keys.begin()};}voiddisplay(){for(intkey :keys){cout <<key <<" ";}cout <<endl;}};intmain(){LRUCache cache(3);cache.put(1,10);cache.put(2,20);cache.put(3,30);cache.display();// 输出：3 2 1cache.get(1);cache.display();// 输出：1 3 2cache.put(4,40);cache.display();// 输出：4 1 3 （2 被移除）return0;}

     输出：

     3 2 1
     1 3 2
     4 1 3

     代码解释：

     • 哈希表与链表结合：哈希表提供 O(1) 的查找，链表维护键的使用顺序。

     3.3 哈希算法的实际应用

     哈希表结合链表可以高效实现最近最少使用（LRU）缓存。

   • 查找（Search）：根据键计算索引，直接定位到存储值的位置。

     哈希函数（Hash Function）是实现这一魔法的核心，其关键特性包括：

     • 确定性：相同的输入总能生成相同的输出。加密安全还是网络协议，哈希算法无处不在。然而，对于复杂的数据，这种方法可能导致大量冲突。

       哈希表的操作：

       • 插入（Insert）：通过哈希函数计算键的索引，将值存入数组。
       • 缓存命中：如果键存在，将其移动到链表头部。这是一个将键（Key）与值（Value）关联的数据结构，它通过哈希函数将键映射到数组的索引，实现快速的数据存取。本文将带你走入哈希算法的奇妙国度，探究它的原理、数字签名和区块链技术。
       • 插入操作：通过哈希函数计算键的索引，将键插入到对应桶中。

第三章：哈希表的奇迹——从无序到有序的转变

哈希算法最典型的应用场景是哈希表（Hash Table）。

#include<iostream>#include<vector>#include<list>#include<string>usingnamespacestd;// 哈希表的定义classHashTable{private:vector<list<string>>table;// 使用链地址法解决冲突inttableSize;// 哈希函数inthashFunction(string key){inthashValue =0;for(charc :key){hashValue +=c;}returnhashValue %tableSize;}public:// 构造函数HashTable(intsize):tableSize(size){table.resize(tableSize);}// 插入操作voidinsert(string key){intindex =hashFunction(key);table[index].push_back(key);}// 查找操作boolsearch(string key){intindex =hashFunction(key);for(string item :table[index]){if(item ==key)returntrue;}returnfalse;}// 打印哈希表voiddisplay(){for(inti =0;i <tableSize;i++){cout <<"Bucket "<<i <<": ";for(string key :table[i]){cout <<key <<" ";}cout <<endl;}}};intmain(){HashTable hashTable(5);hashTable.insert("hello");hashTable.insert("world");hashTable.insert("hash");hashTable.insert("table");hashTable.display();cout <<"Search for 'world': "<<(hashTable.search("world")?"Found":"Not Found")<<endl;cout <<"Search for 'data': "<<(hashTable.search("data")?"Found":"Not Found")<<endl;return0;}