哈希表企业应用-DNA的字符串检测
DNA的字符串检测-引言
若干年后, ikun DNA 检测部成立,专门对 这些ikun的解析检测 突然发现已经完全控制不了 因为学生已经会了 而且是太会了
所以DNA采用 以下视频测试:
ikun必进曲
ikun必经曲
ikun必阶曲
如何感受到了吧!,如果你现在唱跳并且还Rap 还有打篮球 还有铁山靠 那么你就是名副其实的真ikun 为ikun发光发亮,那些假的ikun 只会说:食不食油饼,香精煎鱼.拿什么荔枝 绿尸寒警告,看到这各位想必ikun已经回应那些 黑我们坤坤的人曾经说出食不食油饼,香精煎鱼.拿什么荔枝这些黑粉们你们知道ikun 有多努力? 为了创作 不惜牺牲于自身.emmmm这些你们知道? 他们只不过i kun 而已你们这些小黑子有什么权利说我们ikun ! “闭嘴” DNA检测部门 :他们可是贡献了你们坤坤的"知名度"跟他们比 “你们这些只会喊和叫和骂还有什么” ,“我不信” DNA部门:治不了你 带走 改造DNA 变成名副其实的"黑子DNA部门! " 哈哈哈哈哈, 此时应该插入哦呼w<敢 杀 我 的 马？！>那些魔性的笑声
DNA的字符串检测-原理
所谓的小黑子DNA 检测部门到是有可能00后下一代可能危害巨大必须加以改造 不然老是想着"唱跳并且还Rap 还有打篮球 “危害社会 什么的 当然这也没什么一些家长认为"而且还培养爱运动的习惯…唱功 练习 肺活量练习”
ikun服务部:免费为ikun们 DNA检测 于是乎上3亿人统一归来 大喊为ikun助力 怎么检测有"真ikun"成分?
突然检测组陷入了谜团之中…之前不检测出有种真ilun成分 分别为: “ADDR”,“ABBR”,“BADR”,“BCEE”,“CBEC”,“CRAB”,“DACD”,“DDRC” 这些DNA序列
如何快速匹配真ikun 的DNA?
以下代码 传统方式 测试
#include<iostream>
using namespace std;
// ikun 基因库测试 类型:传统
void iKunGeneSrcLibTradiTest(void) {
// ikun 基因串长度
const int iKunGeneStrLen = 4;
// ikun 基因源库,存储可能的基因串 ("ADDR","ABBR",->唱) ("BADR","BCEE"-> 跳) ("CBEC","CRAB"->Rap) ("DACD","DDRC" ->篮球)
const char* iKunGeneSrcLib[8] = { "ADDR","ABBR","BADR","BCEE","CBEC","CRAB","DACD","DDRC" };
// 要匹配的基因串
const char* TRueIkunGene = "XADDRIKUNYYDS";
// 匹配标志,默认false
bool ikunFlag = false;
// 遍历基因源库
for (size_t i = 0; i < 8; i++){
// 如果源库中的基因串与要匹配的基因串的前4个字符相同
if (strncmp(TRueIkunGene + 1, iKunGeneSrcLib[i], iKunGeneStrLen)==0) {
// 设置匹配标志并结束遍历
ikunFlag = true;
break;
}
}
// 如果匹配成功
if (ikunFlag){
cout << "真ikun 不用质疑了" << endl;
}else{
cout << "小黑子 香精煎鱼?" << endl;
}
}
int main(void) {
// 调用测试函数
iKunGeneSrcLibTradiTest();
return 0;
}
ikun 服务部: 看着挺好用的,但不够高效 (还挺懂啊 ) 上亿人 等着呢 怎么办 突然来了一个原神+崩坏:星穹铁道 玩家说了一句: 让我来看看 (没错就是作者本人
,若干年后,还是一名不知名的程序员 看这挺老的 那可不谁没年轻过呢) emmmm 这段代码?,好像我觉得在CSDN平台看到过,而且好像是我写的,…
一堆废话后,唉我忘了我找找看(此时用的是虚拟键盘 和虚拟电脑 感觉用不习惯)…
找到了…emmm 一顿操作后,如下代码:
#include<iostream>
#include"HashTable.h"
using namespace std;
// ikun 基因库测试 类型:散列
void iKunGeneSrcLibHashiTest(void) {
// 基因串长度
const int iKunGeneStrLen = 4;
// 基因源库
const char* iKunGeneSrcLib[8] = { "ADDR","ABBR","BADR","BCEE","CBEC","CRAB","DACD","DDRC" };
// 要匹配的基因串
const char* TRueIkunGeneSrc = "XCDDRIKUNYYDS";
// 创建哈希表
HashTable iKunGeneSrcIndexLib;
CreateHashTable(iKunGeneSrcIndexLib);
// 将基因源库中的基因串插入哈希表
for (size_t i = 0; i < 8; i++){
HashTableInsert(iKunGeneSrcIndexLib, CreateHashValue(iKunGeneSrcLib[i], iKunGeneSrcLib[i]));
}
// 取要匹配基因串的前4个字符
char TRueIkunGene[5];
strncpy_s(TRueIkunGene, TRueIkunGeneSrc + 1, iKunGeneStrLen);
// 在哈希表中查找
GetFindHashValue findValue = HashTableFind(iKunGeneSrcIndexLib, TRueIkunGene);
// 如果找到,打印找到的基因,否则打印提示信息
if (findValue.isExist){
cout << "真ikun 基因:" << findValue.value->value <<endl;
}else {
cout << "没有找到该基因 :" << TRueIkunGene << " 默认为小黑子基因" << endl;
}
// 销毁哈希表
HashTableDestroy(iKunGeneSrcIndexLib);
}
int main(void) {
iKunGeneSrcLibHashiTest();
return 0;
}
搞定这下大规模数据没有问题了
emmm 给大家介绍所使用的哈希函数算法吧
// SDBM哈希函数
const unsigned int SMBD_Hash(Key key) {
// 0x7FFFFFFF是int类型的最大值,用于取模运算,防止哈希值溢出
const unsigned max = 0x7FFFFFFF;
// 初始化哈希值
unsigned int hash_code = 0;
// 遍历要计算哈希值的字符串
while (*key){
// 更新哈希值
hash_code = (*key++) + (hash_code << 6) + (hash_code << 16) - hash_code;
}
// 对max取模,防止哈希值溢出
return hash_code & max;
}
我只说一个GetFindHashValue
//查找存在的HashValue
struct GetFindHashValue{
//表示哈希值是否存在。
bool isExist;
//哈希值本身
HashValue *value;
};
//哈希表查找算法
GetFindHashValue HashTableFind(const HashTable& HashTable, Key key) {
//获取哈希表的桶空间
HashBucket BucketSpace = HashTable.BucketSpace;
//计算键key的哈希值,得到其在桶空间中的索引
int HashIndex = Hash({ key }, HashTable);
//获取键key所在桶的头节点
HashElement HashElementList = BucketSpace[HashIndex];
//跳过头节点,进入链表
HashElementList = HashElementList->Next;
//遍历链表,查找键key
while (HashElementList && cmp(HashElementList->MyValue.key,key)) {
HashElementList = HashElementList->Next;
}
//如果找到,HashElementList指向找到的节点,否则为nullptr
HashValue* v = HashElementList != nullptr ? &HashElementList->MyValue : nullptr;
GetFindHashValue result{};
//如果找到,设置相关字段,否则isExist为false
if (v) {
result.isExist = true;
result.value = v;
}
return result;
}