计算机入门必备数据结构——散列表

Hi!各位宝宝朋友们，好久不见了~国庆节中秋节过的快乐吗？我的双节在出差路上度过，你们有什么快乐的事情可以分享给我哦~让我也开心一下嘿嘿

由于工作比较忙，学习也落下不少了。趁着今天有点空，我们开始继续学习，学习是一个循序渐进的过程，切忌囫囵吞枣，只要数量，不看质量。从今天开始哪怕只学习一节甚至一个知识点，我也希望能把它学会并能给大家讲出来，我觉得只有这样今天的学习才是有效的，好了，闲言少叙，我们直接进入正题。

今天我们学习的数据结构叫做散列表，起初我看这个名字还感觉挺陌生的，以为是一个新的数据结构，原来它就是我们所学的哈希表。散列表也称哈希表是最有用的基本数据结构之一，我们将要学习他的内部机制：实现，冲突和散列函数。

先举一个例子引出哈希表的概念：假设你在一家超市上班，有顾客来买东西时，肯定会询问你某种东西的价格，每种东西都有自己不同的价格，细心的人可以发现，我们买的那些需要称重的东西，称旁边贴了一张纸，上面写着各种商品的价格，刚来上班的阿姨肯定会在这张纸上查找价格代码，如果纸上的内容不是排序好的，阿姨有可能为查找一个苹果的价格看遍整张纸，这需要花费很长时间。如果是按字母顺序排序好的，阿姨可以利用我们之前学习过的二分查找法来找出苹果的价格，时间复杂度就会大大减少。但这样每次就查找，不仅是阿姨烦对于顾客等待的时间就会变得更长，对于顾客的体验就不是很好，下次就可能不回来这个超市。

这时就需要一个老手阿姨，把每一种物品的价格都记得很清楚，随便问她就能立马说出价格。不管商品有多少，这位老阿姨都能快速报出任何商品的价格，时间复杂度为O（1），速度比二分查找都快。如果你想在程序中实现这么快的查找速度，这是散列函数的用武之地。

1、 散列函数

散列函数是这样的函数，即无论给它什么数据，它都还你一个数字。

散列函数

用专业术语来讲，散列函数是"将输入映射到数字"。散列函数不是没有原则的输出，它其实还是必须要满足一些要求的。

· 它必须是一致的。例如，假设你输入apple时输出的是4，那么每次输入apple时，得到的都必须为4。如果不是这样，散列表将毫无用处。

· 它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，它就不是好的散列函数，最理想的情况是，将不同的输入映射到不同的数字。

我们首先来创建一个空数组，我们将在这个数组上存储商品的价格，将苹果作为输入交给散列函数，散列函数的输出为2，因此我们将苹果的价格存储到数组的索引2处，依次类推，数组中保存好了牛奶、橘子、苹果、梨子的价格之后，如果我们想知道苹果的价格，无需在数组中查找，只需交给散列函数，将apple作为输入输出2，于是可以在数组的索引2处找到苹果的价格。

散列函数之所以可以这样，具体原因如下：

· 散列函数总是将同样的输入映射到相同的索引。

· 散列函数将不同的输入映射到不同的索引。

· 散列函数知道数组有多大，只返回有效索引

使用散列函数和数组我们就可以创建了一种被称为"散列表"的数据结构。散列表是目前学习的第一种包含额外逻辑的数据结构，数组和链表都被直接映射到内存，但散列表更复杂，它需使用散列函数来确定元素的存储位置。

散列表在编程语言中几乎不用自身去实现，比如java学到map或者hashmap，C#学到的dictionary等等。

比如用C#的一段代码：

static void Main(string[] args)
{ //定义键值对 Dictionary dic = new Dictionary();


//添加数据

dic.Add("牛奶", "￥2");

dic.Add("橘子", "￥3");
dic.Add("苹果", "￥4");
dic.Add("梨子", "￥5");


//循环接收

while (true)

{

Console.Write("请输入需要查询的商品价格：");

//接收用户输入

string input = Console.ReadLine();

Console.WriteLine("您查询的" + input + "的价格为：{0}", dic[input]);


//Console.ReadKey();

}

}

我们再来看看运行结果：

运行结果

你学会了吗，但如果我们要查询的东西不在字典，我们看一下它会出现什么异常：

运行异常

当然对于这种情况我们可以使用try Catch来进行优化解决。由此我们学到了散列表是由键和值组成，散列表将键映射到值。好了，今天的学习就到这块，明天我们来学习散列表的使用示例，不要走开，敬请期待~