HashTable(哈希表分离链接法)

2024-08-25 08:18
文章标签 分离 哈希 链接 hashtable

本文主要是介绍HashTable(哈希表分离链接法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

哈希表的分离链接法其实就是个vector<type>容器 + 链表来实现的,其本质就是如果数值(mod)相等的话就插入到vector<type>的同一格,将相等的两个值依次存放在链表中,如果空间很小的话建议不要采用此方法,因为此方法的链表为双向链表,下面为分离链接法的代码:
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
using namespace std;
template<typename HashedObj>
class HashTable
{
public:explicit HashTable(int size = 101){theLists.resize(size);currentSize = size;}bool contains(const HashedObj & x) const;void makeEmpty();bool insert(const HashedObj & x);bool remove(const HashedObj & x);
private:vector<list<HashedObj> > theLists; // the array of Listsint currentSize;void rehash();int myHash(const HashedObj &x) const;
};
class Employee
{
public:const string &getName() const{return name;}bool operator== (const Employee &rhs) const{return getName() == rhs.getName();}bool operator!= (const Employee &rhs) const{return !(*this == rhs);}
private:string name;double salary;int senioity;
};
int hash(const string & key)
{int hashVal = 0;for(int i=0;i<key.length();i++){hashVal = hashVal * 37 + key[i];}return hashVal;
}
int hash(int key)
{return key;
}
int hash(const Employee & item)
{return hash(item.getName());
}
bool Prime(int res)         //散列表最好为素数
{for(int i=2;i<res/2;i++){if(res % i == 0){return true;break;}}return false;
}
int nextPrime(int num)
{while(1){if(Prime(num) == false){return num;break;}else{num++;}}
}
template<typename HashedObj>
int HashTable<HashedObj>::myHash(const HashedObj & x) const
{int hashVal = hash(x);hashVal %= theLists.size();  //theLists.size()为总容量if(hashVal < 0){hashVal += theLists.size();}return hashVal;
}
template<typename HashedObj>
void HashTable<HashedObj>::rehash()
{vector<list<HashedObj> > oldLists = theLists;theLists.resize(nextPrime(2 * theLists.size()));for(int j=0;j<theLists.size();j++){theLists[j].clear();}cout<<theLists.size()<<endl;currentSize = 0;for(int i=0;i<oldLists.size();i++)  //vector<>从上到下{typename list<HashedObj>::iterator itr = oldLists[i].begin(); //链表头到尾覆盖while(itr != oldLists[i].end())insert(*itr++);}
}
template<typename HashedObj>
void HashTable<HashedObj>::makeEmpty()
{for(int i=0;i<theLists.size();i++){theLists[i].clear();}
}
template<typename HashedObj>
bool HashTable<HashedObj>::contains(const HashedObj & x) const
{const list<HashedObj> &whichList = theLists[myHash(x)];return find(whichList.begin(),whichList.end(),x) != whichList.end();
}
template<typename HashedObj>
bool HashTable<HashedObj>::remove(const HashedObj &x)
{list<HashedObj> & whichList = theLists[myHash(x)];typename list<HashedObj>::iterator itr = find(whichList.begin(),whichList.end(),x);if(itr == whichList.end()){return false;}whichList.erase(itr);--currentSize;return true;
}
template<typename HashedObj>
bool HashTable<HashedObj>::insert(const HashedObj &x)
{list<HashedObj> & whichList = theLists[myHash(x)];if(find(whichList.begin(),whichList.end(),x) != whichList.end()){return false; // 如果已经存在}whichList.push_back(x);if(++currentSize >theLists.size())rehash();return true;
}
int main()
{HashTable<int> b;b.insert(1);b.insert(10);b.insert(100);b.insert(9);b.insert(69);b.insert(57);if(b.contains(100) && b.contains(57)){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}if(b.insert(57)){cout<<"insert succeed!"<<endl;}else{cout<<"repeat!"<<endl;}if(b.remove(69)){cout<<"remove succeed!"<<endl;}else{cout<<"The element not exist in HashTable";}b.makeEmpty();if(b.contains(1) || b.contains(10) || b.contains(100)){cout<<"The HashTable is not empty!"<<endl;}else{cout<<"It is empty!"<<endl;}return 0;
}



这篇关于HashTable(哈希表分离链接法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1105027

相关文章

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import

springboot将lib和jar分离的操作方法

《springboot将lib和jar分离的操作方法》本文介绍了如何通过优化pom.xml配置来减小SpringBoot项目的jar包大小,主要通过使用spring-boot-maven-plugin... 遇到一个问题,就是每次maven package或者maven install后target中的ja

配置springboot项目动静分离打包分离lib方式

《配置springboot项目动静分离打包分离lib方式》本文介绍了如何将SpringBoot工程中的静态资源和配置文件分离出来,以减少jar包大小,方便修改配置文件,通过在jar包同级目录创建co... 目录前言1、分离配置文件原理2、pom文件配置3、使用package命令打包4、总结前言默认情况下,

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

安卓链接正常显示,ios#符被转义%23导致链接访问404

原因分析: url中含有特殊字符 中文未编码 都有可能导致URL转换失败,所以需要对url编码处理  如下: guard let allowUrl = webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时,会被误伤转义为%23,导致链接无法访问

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表(Hash Table)是一种数据结构,它通过将键(Key)映射到值(Value)的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希

每日一练7:简写单词(含链接)

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1(错误经验) #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=