算法系列第5天15天快速搜索五经【中】

哈希搜索：是的，它是一个哈希搜索。说到散列，每个人都必须提到散列函数。呵呵，这个东西已经在我们的脑海中形成了一种固有的思维。每个人都必须知道“hash”中的对应关系。比如“5”是一个要保存的数字，然后我把它扔给hash函数，hash函数给我返回一个“2”。那么此时的“5”和“2”就会建立对应关系，这就叫做“哈希关系”，在实际应用中，“2”是关键，“5”是价值。然后一些朋友会问怎么做哈希。首先要遵守两个原则：尽量分散：个键，也就是我给你扔一个“6”和一个“5”，你返回一个“2”，所以这个哈希函数并不完美。:哈希函数尽量简单，也就是说如果你抛出一个“6”，需要你一个小时才能给我，这样不好。实际上，常用的哈希方法有“五种”:第一种是“直接地址法”。很容易理解，键=值C；这个“c”是一个常数。值C实际上是一个简单的散列函数。第二种：“除法求余数的方法”。很容易理解，key=值% C；如上解释。第三类：“数字分析”。这个挺有意思的，比如有一组value1=112233，value2=112633，value3=119033。对于这样的数字，我们分析，数字中间的两个数字波动，而其他数字保持不变。那么我们可以把键值取为key1=22，key2=26，key3=90。第四种：“方取中法”。忽略这里，看到名字就知道意思。第五种：“折法”。这很有意思，比如value=135790，要求key是2位数的哈希值。然后，我们将该值更改为13 57 90=160，然后删除高阶“1”。这时，key=60，哈哈，这是他们的哈希关系。这样做的目的是让密钥与每一位值相关联，从而达到“哈希地址”尽可能分散的目的。我经常在河边散步，所以没有湿鞋。散列也是如此。如果你的hash函数设计得好，很可能会击中建筑物一次，然后抛给我们的问题就是要不要解决“hash地址”的冲突。实际上，解决冲突有两种常见的方法：第一种是“开放地址法”。所谓的“开放地址”实际上是数组中未使用的地址。也就是说，在冲突的地方，后面来的元素(:线性检测和函数检测可以采用两种方式)寻找数组后的“开放地址”，然后将自己插入其中。第二：“链接法”。暂时不懂这个也没关系。我先介绍一下原理，就是在每个元素上放一个“指针字段”。在冲突的地方，后面的元素将自己的数据字段抛出到冲突的元素，此时，冲突的地方形成一个链表。上面有这么多赘言，就是希望大家在“设计hash”和“解决冲突”两个方面给出一些参考和手段。然后，代码写在下面，设计功能采用“除法余数法”。冲突采用：“开放地址线性检测法”。

复制代码代码如下：使用系统；使用系统。集合。通用；使用系统Linq .使用系统。文字；命名空间有一个搜索{类程序{//}除法取余法" static int hashLength=13//原数据静态Listint list=new Listint() { 13，29，27，28，26，30，38 }；//哈希表长度static int[]hash=new int[hashLength]；静态void Main(字符串[]参数){ //创建哈希(int I=0；我列举。计数；i ) { InsertHash(hash，hashLength，list[I])；}控制台。写线('哈希数据：'字符串Join('，'，hash))；while (true) { Console .WriteLine('\n请输入要查找数字：');（同Internationalorganizations）国际组织结果=int .解析（控制台. ReadLine())；var index=SearchHash(hash，hashLength，result)；if (index！=-1)控制台WriteLine(“”数字"结果"在索引的位置是： '索引);否则控制台WriteLine(“”呜呜，'结果'在混杂中没有找到!');} } ///summary///Hash表检索数据////summary////param name=' DIC '/param///param name=' hashLength '/param///param name=' key '/param///returns/returns static int search hash(int[]hash，int hashLength，int key) { //哈希函数int hashAddress=key % hashLength//指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决while (hash[hashAddress]！=0 hash[hashAddress]！=key){ hashAddress=(hashAddress)% hashLength；} //查找到了开放单元，表示查找失败if (hash[hashAddress]==0)返回-1;返回hashAddress}///摘要///数据插入混杂表////summary///param name='dic '哈希表/param///param name=' hashLength '/param///param name=' data '/param static void InsertHash(int[]hash，int hashLength，int data) { //哈希函数int hashAddress=数据% 13;//如果键存在，则说明已经被别人占用，此时必须解决冲突while (hash[hashAddress]！=0) { //用开放寻址法找到hashAddress=(hashAddress)% hashLength；} //将数据存入字典中哈希[哈希地址]=数据；} }}结果

索引搜索：说到“索引”，估计大家的第一反应就是“数据库索引”。是的，事实上，通过主键建立“索引”便于我们在海量数据中进行搜索。关于“指数”的知识，估计大家都比我懂，我就简单介绍一下。我们自己编写算法来实现索引搜索中经常用到的三个术语：第一，主表，非常简单，就是要搜索的对象。第二：索引项。一般我们会用函数把一个主表分成几个子表，每个子表都会建立一个索引。这个索引称为索引项。第三，索引表，它是索引项的集合。一般来说，“索引条目”包含三个内容：索引、开始、长度第一：索引，是索引指向主表的关键词。第二：start，这是索引在主表中的位置。第三，长度是子表的区间长度。复制代码如下：使用系统；使用系统。集合。通用；使用系统。Linq使用系统。文字；namespaceindexsearch程序{ class program {///summary///index item entity////summary class index {//对应于主表public int index的值；//主表记录区间的起始位置为public int start//主表记录间隔的长度为public int length} static void main(string[]args){ console . write line('原始数据为：' string。加入('，'，学生))；int值=205；控制台。write line(' \ n插入数据'值)；//在集合中插入205，超索引var index=insert(值)；//如果插入成功，则获取if (index==1)位置{console。write line(' \ n插入后的数据：' string。加入('，'，学生))；控制台。WriteLine('\n数组中的数据元素：205是' indexSearch(205)'位')；}控制台。ReadLine()；}///summary////student主表////summary static int[]students={ 101，102，103，104，105，0，0，0，0，0，201，202，203，204，0，0。///summary////学生索引表////summary静态索引[] index={new index () {index=1，start=0，length=5}，new index () {index=2，start=10，length=4}，new IndexItem(){ index=3，start=20，length=3}，}；///summary///find data/////summary//param name=' key '/param////returns/returns public static int index search(int key){ indexitem item=null；//创建索引规则var index=key/100；//转到要查找的索引(int I=0；i indexItem。count()；i ) { if (indexItem[i])。index==index){ item=new index item(){ start=index item[I]。开始，长度=indexItem[i]。长度}；打破；} }//如果该项为空，则如果(item==null)返回-1，则索引中的搜索失败；for(int I=item . start；I项.起始项.长度；i ) { if(学生[i]==键){ return I；} } return-1；}///summary////insert data////summary///param name=' key '/param////returns/returns public static int insert(int key){ indexitem item=null；//创建索引规则var index=key/100；int I=0；for(I=0；i indexItem。count()；I) {//得到了index if (index [I]。index==index){ item=new index(){ start=index[I]。开始，长度=索引[I]。长度}；打破；} } if (item==null)返回-1；//更新学生主表[item . startitem . length]=key；//更新索引表索引[I]。长度；返回1；}}}结果：

Ps:哈希搜索时间复杂度O(1)。搜索时间复杂度：以上面的Demo为例，等于O(n/3) O(长度)。