快速制作简单的网站,网站建设理由和目的,网络课程设计报告,合肥动画制作公司示例代码参考代码随想录
1、啥是哈希表 哈希表#xff0c;简单说吧#xff0c;复杂的现在还没有弄明白怎么描述 1、就是按照一定的规则#xff0c;将数据存入到数据结构中。而C语言中现在我们常见的就是数组#xff0c;以及使用数组和链表的结合。还有C#xff0c;一般使…示例代码参考代码随想录
1、啥是哈希表 哈希表简单说吧复杂的现在还没有弄明白怎么描述 1、就是按照一定的规则将数据存入到数据结构中。而C语言中现在我们常见的就是数组以及使用数组和链表的结合。还有C一般使用的都是unordered_set,unordered_map。 突出的就是一个存储位置和值的对应关系书上写的是关键字实际上就是值看书上的强迫症都犯了 比如计算存储位置索引的方法之一 Hashvalue value %p这个被称为除留取余法。不过这个方法这样的表现形式是使用数字做取余运算的方式。如果存储其他类型数据可能需要看情况转化成可使用数字做索引的方式了。突然发现这个索引的计算有点像是计算某个范围内随机值的感觉 2、还有一点这个hash表更多的是突出一个散列的存储 根据下面例子我们就可以发现只是使用字符的ascii码差值做索引来记录相同字符的个数这字符的字符数据之间没有直接的关联关系什么的。 这个例子就有点像点到原点的距离。这些字符串中的字符有多少到原点a的距离是相同的比如n - a 20就相当于我们设定好了n的位置就存放在数组的位置 record [20]处而我们需要计算的是有多少点的位置在里。直接给record[20] . 2、代码题示例
#include iostream
#include stdio.h
#include stringusing namespace std;
bool isAnagram(string s, string t);
int main()
{string s(anagram);string t(nagaram);isAnagram(t,s);
}bool isAnagram(string s, string t){ // s anagram t nagaramint record[26] {0};if(s.size()! t.size()){return false;}for(int i 0; i s.size(); i) {record[s[i] - a]; //一开始接触这个也是没反应过来实际上就是 用字母去减字母这种情况下都是使用askii码进行相加减} //这个操作就相当于记录一个标志值因为26个英文字母在ascii中是连续的所以其他字母和a的差值不会超过25/26//至于我为啥用25/26呢因为确实记不清a是多少了 不过作为数组record的下标不会超过26//上面的这个可以发现如果相同的字母减a那么那个下标的值就会1.//当两个字符串的字母一样时如果用同样的数组记录结果应该就是一样的字符串t//比如 t有三个a 结果遍历字符的时候a-a 的ascii值是一样的有三个所以record[a - a] 3;//这个时候如果我们做个相反的计算 record[]-1 是不是遍历结束后record[0]的位置就是0 .其他的字符也一样for(int i 0; i t.size(); i){record[t[i]-a]--;}//上面两步操作完数组里如果都是0就表示两个字符串的字符一样。顺序不同 。这有点那个信号量控制共享资源的感觉for(int i 0; i 26; i){if(record[i]!0){return false;}}cout t 和s 是互为字母异位词 endl;return true;
}
3、哈希表的链地址法 基本上就是使用一个数组去存储链表的头指针。然后将数据根据我们设定的索引规则存储在特定的索引地址下。
这个我们也可以用来做索引数据结构啥的在标准模板库STL中的无需关联式容器使用的就是链地址法。用来解决hash冲突
这个网上挺多的就是需要注意一个装填因子的问题 装填因子/装载因子 元素个数/表长0.5~0.75 这个值在这个范围之间就比较合适。再多了可能需要更换数据结构。、
比如C有序关联式容器中使用红黑树去存储数据目前还没扣明白等搞明白了写上。
使用epoll 的时候这个底层实现也是使用红黑树去实现的。因为select 底层就是一个位图可以当成个数组大概能监听1024个文件描述符。而epoll好像在10万以上 //哈希表的用途可以用来做缓存比如服务器使用哈希表做缓存机制缓存用户的id作为keyvalue 用来存储用户详细信息等查询起来方便就不用每次都向服务器发送请求了
