哈希表 - 图1

哈希

百度百科：“Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。”

定义

  • 哈希是一类算法（一种思想），不是固定的某种算法；
  • 这类算法可以把任意长度的的消息转换成固定长度的字符串（通常用16进制的字符串表示）；

在线hash加密：https://tool.oschina.net/encrypt?type=2
image.png
抽象成函数：

  1. char* hash_1(char* intput)
  2. {
  3.     char* output = (char*)malloc(32);
  4.     .....
  5.     return  output;
  6. }
  8. char* hash_2(char* intput)
  9. {
  10.     char* output = (char*)malloc(128);
  11.     .....
  12.     return  output;
  13. }
  15. char* hash_3(char* intput)
  16. {
  17.     char* output = (char*)malloc(256);
  18.     .....
  19.     return  output;
  20. }

特点

  • 单向不可逆；
  • 无论输入的消息有多长，计算出来的消息摘要的长度总是固定的，计算出的结果越长，一般认为该摘要算法越安全；

  • 输入的消息不同，产生的消息摘要必不同，输入的消息相同，产生的消息摘要一定是相同的；

    应用

  • 文件校验：比如在网络传输过程中，为防串改，需要校验文件的完整性；

  • 数字签名；
  • 鉴权：后台不可能直接存储用户的密码，一般都是存储摘要，当用户登陆的时候校验用户所输入密码的摘要，作比较就饿判断是否通过；


常用的加密算法

语雀内容

拓展

MD5破解，撞库，王小云
https://www.sohu.com/a/197288583_684445
王小云教授曾经成功制造出MD5的碰撞，即md5(a) = md5(b)。这样的碰撞只能随机生成，并不能根据一个已知的a求出b（即并没有破坏MD5的无冲突特性），但这已经让她 声名大噪了。

哈希表

百度百科：“散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表”

引子

假设要建立一张全班40个学生的情况统计表，每一个学生为一个记录，记录的各项数据为：
哈希表 - 图3

  • 很明显我们可以利用一个一维数组S[40]来存放它，当我们要查询某一个学生的信息的时候，我们可以以学生的学号来作为关键字查询，因为数组的下标和学号没有确定的关系，因此我们需要遍历整个数组才能找到想要的学号，如下图：

哈希表 - 图4

  • 很明显遍历的做法很耗时，因此我们想通过建立学号和下标的映射关系，来提高我们的查询效率，也就是说通过学号可以确定下标，如下图：

哈希表 - 图5
上面的学号和下标的映射关系可以这样表示：下标 = 学号 - 20155040，这样我们查找学号为2015550403的学生信息，就可以直接找到它的存储位置，它对应的下标为3，上面的映射关系可以抽象为函数：Hash(key)=key-201555040

  1. int hash_table(int* stu_num)
  2. {
  3.     return  stu_num - 2015550400;
  4. }

在上面的例子中，学号和下标建立映射关系的函数，就称为哈希函数，通过通过映射得到的下标值称为哈希地址，通过映射关系存储学生信息的数组就称为哈希表！

哈希冲突

当然在实际生活中我们查询一个班级的学生情况的时候，往往更倾向于用名字作为关键字来查找记录，比如老师更倾向于询问”刘耀的电话是多少啊？”而不是”2015550403 的电话是多少啊？”。假设学生姓名以汉语的小写拼音的字符表示，取关键字的第一个字母的ASCII码，再对10取余所得的余数便是记录在数组中的下标值。如关键字陈葳蕤（陈葳蕤）第一字母为c ASCII码为99,99对10取余为9，则陈葳蕤的记录在哈希表的中的下标为9.
如图给出部分学生的哈希地址：
哈希表 - 图6
这个时候你就会发现一个bug：陈葳蕤和蔡布思hash地址相同，都为9这个，这个时候就会造成哈希冲突，怎么解决呢？
如图可以把哈希地址相同的元素放在同一个链表中，这时数组中对应的下标存储的不再是具体的元素，而是元素所对应的链表地址！

哈希表 - 图7
从这个例子中得知：

  • 哈希表的构建很灵活，关键字有很多选择，hash函数也可以有很多的设计方法
  • 对于不同的关键字，若得到同一个哈希地址，这种关键字我们称之为同义词，结果就是哈希冲突
  • 一般情况下，同义词的冲突只能尽可能地减少并不能完全避免

冲突解决方法有很多，如上面的解决办法，被称为拉链法，还有开放地址发等，这里不做过多讨论

定义

利用关键字通过一个函数确定记录在数组中的下标。
（通过一个哈希函数Hash(key)和处理冲突方法将一个关键字映射到一个连续的地址集上，并以关键字在地址集上的像作为记录在表中的存储位置。这种表或者结构称为哈希表）

注意：哈希表的本质是一个数组和链表的组合，但是与数组的区别在于：

  • 普通数组存储的元素和下标没有对应关系
  • 哈希表中存储的元素和下标存在某种映射关系


时间复杂度

理想情况下(没有同义词)，通过关键字访问哈希表某一个记录的时间复杂度是O(1)，但是由于冲突的产生，使得关键字仍然需要和别的同义词做比较。

打个比方:
这就像我们去利用字典查找汉字，我们虽然能够利用汉字的首字母或者汉字的笔画去确定该汉字在字典中的页码，但是该页码中还存在其他的汉字，我们需要将查找的汉字和该页码中的汉字进行比较，直到找到我们要查找的汉字。在利用字典查找汉字的过程中，我们虽然仍然要去比较汉字，但相比与在所有页码中去一个个比较查询，这种先确定页码再去比较的方案已经能极大地提高我们查找的效率了。
也就是说哈希表尽可能地减少我们要比较的次数，当然通过设计优秀的哈希函数可减少哈希冲突，但同时会提高空间复杂度。时间换空间，亦或空间换时间，这远远是计算机界的永恒定律。