首页 > 代码库 > 算法系列15天速成——第五天 五大经典查找【中】
算法系列15天速成——第五天 五大经典查找【中】
大家可否知道，其实查找中有一种O(1)的查找，即所谓的秒杀。
哈希查找：
对的，他就是哈希查找，说到哈希，大家肯定要提到哈希函数，呵呵，这东西已经在我们脑子里面形成
固有思维了。大家一定要知道“哈希“中的对应关系。
比如说： ”5“是一个要保存的数，然后我丢给哈希函数，哈希函数给我返回一个”2"，那么此时的”5“
和“2”就建立一种对应关系，这种关系就是所谓的“哈希关系”，在实际应用中也就形成了”2“是key，”5“是value。
那么有的朋友就会问如何做哈希，首先做哈希必须要遵守两点原则：
①: key尽可能的分散，也就是我丢一个“6”和“5”给你，你都返回一个“2”，那么这样的哈希函数不尽完美。
②： 哈希函数尽可能的简单，也就是说丢一个“6”给你，你哈希函数要搞1小时才能给我，这样也是不好的。
其实常用的做哈希的手法有“五种”：
第一种：”直接定址法“。
很容易理解，key=Value+C； 这个“C"是常量。Value+C其实就是一个简单的哈希函数。
第二种：“除法取余法”。
很容易理解， key=value%C;解释同上。
第三种：“数字分析法”。
这种蛮有意思，比如有一组value1=112233，value2=112633，value3=119033，
针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是
key1=22,key2=26,key3=90。
第四种：“平方取中法”。此处忽略，见名识意。
第五种：“折叠法”。
这种蛮有意思,比如value=http://www.mamicode.com/135790，要求key是2位数的散列值。那么我们将value变为13+57+90=160，
然后去掉高位“1”,此时key=60，哈哈，这就是他们的哈希关系，这样做的目的就是key与每一位value都相
关，来做到“散列地址”尽可能分散的目地。
正所谓常在河边走，哪有不湿鞋。哈希也一样，你哈希函数设计的再好，搞不好哪一次就撞楼了，那么抛给我们的问题
就是如果来解决“散列地址“的冲突。
其实解决冲突常用的手法也就2种：
第一种： “开放地址法“。
所谓”开放地址“，其实就是数组中未使用的地址。也就是说，在发生冲突的地方，后到的那个元素（可采用两种方式
:①线性探测，②函数探测）向数组后寻找"开放地址“然后把自己插进入。
第二种：”链接法“。
这个大家暂时不懂也没关系，我就先介绍一下原理，就是在每个元素上放一个”指针域“，在发生冲突的地方，后到的那
个元素将自己的数据域抛给冲突中的元素，此时冲突的地方就形成了一个链表。
上面啰嗦了那么多，也就是想让大家在”设计哈希“和”解决冲突“这两个方面提一点参考和手段。
那么下面就上代码了，
设计函数采用：”除法取余法“。
冲突方面采用:”开放地址线性探测法"。
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace HashSearch
7 {
8 class Program
9 {
10 //“除法取余法”
11 static int hashLength = 13;
12
13 //原数据
14 static List<int> list = new List<int>() { 13, 29, 27, 28, 26, 30, 38 };
15
16 //哈希表长度
17 static int[] hash = new int[hashLength];
18
19 static void Main(string[] args)
20 {
21 //创建hash
22 for (int i = 0; i < list.Count; i++)
23 {
24 InsertHash(hash, hashLength, list[i]);
25 }
26
27 Console.WriteLine("Hash数据：" + string.Join(",", hash));
28
29 while (true)
30 {
31 Console.WriteLine("\n请输入要查找数字：");
32 int result = int.Parse(Console.ReadLine());
33 var index = SearchHash(hash, hashLength, result);
34
35 if (index != -1)
36 Console.WriteLine("数字" + result + "在索引的位置是:" + index);
37 else
38 Console.WriteLine("呜呜，" + result + " 在hash中没有找到！");
39
40 }
41 }
42
43 ///<summary>
44 /// Hash表检索数据
45 ///</summary>
46 ///<param name="dic"></param>
47 ///<param name="hashLength"></param>
48 ///<param name="key"></param>
49 ///<returns></returns>
50 static int SearchHash(int[] hash, int hashLength, int key)
51 {
52 //哈希函数
53 int hashAddress = key % hashLength;
54
55 //指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决
56 while (hash[hashAddress] != 0 && hash[hashAddress] != key)
57 {
58 hashAddress = (++hashAddress) % hashLength;
59 }
60
61 //查找到了开放单元，表示查找失败
62 if (hash[hashAddress] == 0)
63 return -1;
64 return hashAddress;
65
66 }
67
68 ///<summary>
69 ///数据插入Hash表
70 ///</summary>
71 ///<param name="dic">哈希表</param>
72 ///<param name="hashLength"></param>
73 ///<param name="data"></param>
74 static void InsertHash(int[] hash, int hashLength, int data)
75 {
76 //哈希函数
77 int hashAddress = data % 13;
78
79 //如果key存在，则说明已经被别人占用，此时必须解决冲突
80 while (hash[hashAddress] != 0)
81 {
82 //用开放寻址法找到
83 hashAddress = (++hashAddress) % hashLength;
84 }
85
86 //将data存入字典中
87 hash[hashAddress] = data;
88 }
89 }
90 }
结果：
索引查找：
一提到“索引”，估计大家第一反应就是“数据库索引”，对的，其实主键建立“索引”，就是方便我们在海量数据中查找。
关于“索引”的知识，估计大家都比我清楚，我就简单介绍下。
我们自己写算法来实现索引查找时常使用的三个术语：
第一：主表， 这个很简单，要查找的对象。
第二：索引项， 一般我们会用函数将一个主表划分成几个子表，每个子表建立一个索引，这个索引叫做索引项。
第三：索引表, 索引项的集合也就是索引表。
一般“索引项”包含三种内容：index，start，length
第一： index，也就是索引指向主表的关键字。
第二：start， 也就是index在主表中的位置。
第三：length, 也就是子表的区间长度。
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5
6 namespace IndexSearchProgram
7 {
8 class Program
9 {
10 ///<summary>
11 /// 索引项实体
12 ///</summary>
13 class IndexItem
14 {
15 //对应主表的值
16 public int index;
17 //主表记录区间段的开始位置
18 public int start;
19 //主表记录区间段的长度
20 public int length;
21 }
22
23 static void Main(string[] args)
24 {
25 Console.WriteLine("原数据为：" + string.Join(",", students));
26
27
28 int value = http://www.mamicode.com/205;
29
30 Console.WriteLine("\n插入数据" + value);
31
32 //将205插入集合中，过索引
33 var index = insert(value);
34
35 //如果插入成功，获取205元素所在的位置
36 if (index == 1)
37 {
38 Console.WriteLine("\n插入后数据：" + string.Join(",", students));
39 Console.WriteLine("\n数据元素：205在数组中的位置为 " + indexSearch(205) + "位");
40 }
41
42 Console.ReadLine();
43 }
44
45 ///<summary>
46 /// 学生主表
47 ///</summary>
48 static int[] students = {
49 101,102,103,104,105,0,0,0,0,0,
50 201,202,203,204,0,0,0,0,0,0,
51 301,302,303,0,0,0,0,0,0,0
52 };
53 ///<summary>
54 ///学生索引表
55 ///</summary>
56 static IndexItem[] indexItem = {
57 new IndexItem(){ index=1, start=0, length=5},
58 new IndexItem(){ index=2, start=10, length=4},
59 new IndexItem(){ index=3, start=20, length=3},
60 };
61
62 ///<summary>
63 /// 查找数据
64 ///</summary>
65 ///<param name="key"></param>
66 ///<returns></returns>
67 public static int indexSearch(int key)
68 {
69 IndexItem item = null;
70
71 // 建立索引规则
72 var index = key / 100;
73
74 //首先去索引找
75 for (int i = 0; i < indexItem.Count(); i++)
76 {
77 if (indexItem[i].index == index)
78 {
79 item = new IndexItem() { start = indexItem[i].start, length = indexItem[i].length };
80 break;
81 }
82 }
83
84 //如果item为null，则说明在索引中查找失败
85 if (item == null)
86 return -1;
87
88 for (int i = item.start; i < item.start + item.length; i++)
89 {
90 if (students[i] == key)
91 {
92 return i;
93 }
94 }
95 return -1;
96 }
97
98 ///<summary>
99 /// 插入数据
100 ///</summary>
101 ///<param name="key"></param>
102 ///<returns></returns>
103 public static int insert(int key)
104 {
105 IndexItem item = null;
106 //建立索引规则
107 var index = key / 100;
108 int i = 0;
109 for (i = 0; i < indexItem.Count(); i++)
110 {
111 //获取到了索引
112 if (indexItem[i].index == index)
113 {
114 item = new IndexItem()
115 {
116 start = indexItem[i].start,
117 length = indexItem[i].length
118 };
119 break;
120 }
121 }
122 if (item == null)
123 return -1;
124 //更新主表
125 students[item.start + item.length] = key;
126 //更新索引表
127 indexItem[i].length++;
128 return 1;
129 }
130 }
131 }
结果：
ps： 哈希查找时间复杂度O(1)。
索引查找时间复杂度：就拿上面的Demo来说是等于O(n/3)+O(length)
算法系列15天速成——第五天 五大经典查找【中】