频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
算法系列15天速成——第五天 五大经典查找【中】
2011-11-26 12:50:53      个评论      
收藏   我要投稿

 

大家可否知道,其实查找中有一种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=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 = 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             { www.2cto.com

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)

  

 

 


作者 huangxincheng520

点击复制链接 与好友分享!回本站首页
相关TAG标签 五天 算法 经典
上一篇:算法系列15天速成——第四天 五大经典查找【上】
下一篇:RSA算法从数学基础到实例全面解析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站