网站建设调研报告的前言,百度一下百度搜索百度一下,中国十大服务外包企业,兰州官网优化技术厂家在普通的查询中#xff0c;通过关键码的比较进行查找#xff0c;而哈希是根据关键码直接定位到数据项
哈希冲突#xff1a;同一个关键码经过哈希函数后指向同一个记录集 链式哈希
using namespace std;
#define M 13
typedef int KeyType;
//typedef struct
//{
// KeyTyp…在普通的查询中通过关键码的比较进行查找而哈希是根据关键码直接定位到数据项
哈希冲突同一个关键码经过哈希函数后指向同一个记录集 链式哈希
using namespace std;
#define M 13
typedef int KeyType;
//typedef struct
//{
// KeyType key;
// Record recptr;
//}Elemtype;
typedef struct HashNode
{HashNode* next;KeyType key;
} HashNode;
typedef struct
{HashNode* data[M];int cursize;
}HashTable;
HashNode* BuyNode()
{HashNode* s (HashNode*)calloc(1, sizeof(HashNode));if (s nullptr)exit(1);return s;
}
void FreeNode(HashNode*p)
{free(p);
}
void InitHashTable(HashTable* pht)
{assert(pht ! nullptr);pht-cursize 0;for (int i 0; i M; i){pht-data[i] 0;}
}
int Hash(KeyType kx)
{return kx % M;
}
bool Insert(HashTable* pht, KeyType kx)
{assert(pht ! nullptr);int pos Hash(kx);HashNode* p pht-data[pos];while (p ! nullptr p-key ! kx){p p-next;}if (p ! nullptr) return false;HashNode* s BuyNode();s-key kx;s-next pht-data[pos];pht-data[pos] s;pht-cursize 1;return true;
}
void PrintHashTable(HashTable* pht)
{assert(pht ! nullptr);for (int i 0; i M; i){cout 桶编号 i - ;HashNode* p pht-data[i];while (p ! nullptr){cout p-key ;p p-next;}cout endl;}
}
int main()
{KeyType ar[] { 19,14,23,1,68,20,84,27,55,11,10,79};int n sizeof(ar) / sizeof(ar[0]);HashTable ht;InitHashTable(ht);for (int i 0; i n; i){Insert(ht, ar[i]);}PrintHashTable(ht);
}
结果 删除
bool Remove(HashTable* pht, const KeyType kx)
{if (pht nullptr) { return false; }int pos Hash(kx);HashNode* p pht-data[pos];HashNode* ptr nullptr;while (p ! nullptr p-key ! kx){ptr p;p p-next;}if (p nullptr) { return false; }if (ptr nullptr){pht-data[pos] p-next;free(p);p nullptr;}else{ptr-next p-next;free(p);p nullptr;}pht-cursize - 1;return true;
} 一致性哈希 采用虚拟节点的方式解决了添加和删除物理节点时资源分配会不均匀的问题。 倒排表
到排表是搜索引擎的核心架构
假设我们爬取了4个文档里面的内容如下 基于4个文档写出我们的词库 [我们今天运动昨天上课什么] 统计词库中的每个单词出现在哪些文档中显然 我们 出现在[doc1,doc2] 中
这样我们就可以把文档以到排表的方式存储了这样做有什么优点呢 假如用户输入我们 上课 如果没有到排表则只能一篇一篇的去搜索文档中 是否既包含我们又包含上课这样复杂度太高了 有了到排表我们知道 我们[Doc1, Doc2], 上 [ Doc3,Doc4], 课[Doc3,Doc4], 如果有交集我们可以直接返回交集如果没有交集那么直接返回 并集[ Doc1,Doc2, Doc3,Doc4] 倒排的优缺点和正排的优缺点整好相反。 所有正排的【优点】易维护【缺点】搜索的耗时太长。 倒排【缺点】在构建索引的时候较为耗时且维护成本较高【优点】搜索耗时短在处理复杂的多关键字查询时可在倒排表中先完成查询的交、并等逻辑运算得到结果后再对记录进行存取。这样不必对每个记录随机存取把对记录的查询转换为地址集合的运算从而提高查找速度。
templateclass TKey std::string
class InvIndex : public mapTKey, listint
{
public:vectorvectorTKey docs;
public:void add(vectorTKey doc){docs.push_back(doc);int curDocID docs.size();for (int i 0; i doc.size(); i){typename mapTKey, listint ::iterator it;it this-find(doc[i]);if (it this-end()){listint newlist;(*this)[doc[i]] newlist;it this-find(doc[i]);}it-second.push_back(curDocID);}}
};
int main()
{string d1_tmp[] { 杨和平,按泽鹏,殷培文,谢家桥,释小龙 };int n sizeof(d1_tmp) / sizeof(d1_tmp[0]);vectorstringd1(d1_tmp, d1_tmp n);string d2_tmp[] { 杨和平,里加长,房价想,谢家桥,冬温慧 };n sizeof(d2_tmp) / sizeof(d2_tmp[0]);vectorstringd2(d2_tmp, d2_tmp n);string d3_tmp[] { 释小龙,按泽鹏,殷培文,里加长,样变变 };n sizeof(d3_tmp) / sizeof(d3_tmp[0]);vectorstringd3(d1_tmp, d1_tmp n);string d4_tmp[] { 杨和平,房价想,殷培文,谢家桥,作结 };n sizeof(d4_tmp) / sizeof(d4_tmp[0]);vectorstringd4(d4_tmp, d4_tmp n);std::shared_ptrInvIndexstringinv(new InvIndexstring());inv-add(d1);inv-add(d2);inv-add(d3);inv-add(d4);return 0;
}
