参考散列表
在前面介绍的查找算法中，如果是无序表，那就是得用顺序查找，从前往后依次遍历。如果是有序表，那可以用二分查找。那么能不能有一种方法可以直接查找出来呢，而不用遍历的思想。
想一想在教室里学生坐在座位上，如果上课的时候想看谁，那就直接向那个方位位置看就行，那么为什么没有从前向后遍历所有的座位呢？ 因为内心里记着一张座次表，知道谁坐在哪里，所以当你想看向谁的时候，大脑里就直接给你那个位置，而这张座次表就是哈希表，这种查找算法就是哈希查找。
或者说下课的时候，看向心里的那个“她”，如果她的座位上没有她，你会怎么做呢？是不是环顾四周，环顾整个教室？？？ 这就是需要遍历了。因为我们对下课时的教室这个环境不熟悉，或者说是没有这张表，本质上说，这其实就是顺序查找了。
再来一个例子，你家的房间，客厅，厨房，主卧，次卧，卫生间。想去主卧，然后就直接去了，为什么不是遍历呢，一个一个的房间看看是不是，不是再退出来。还是因为你大脑中有一张表，对这几个房间的位置有了一种映射关系。把它们想象成5个元素的数组，[0,1,2,3,4]。你想去主卧，那大脑直接返给你下标2，想去卫生间，大脑直接返给你下标4.。
简单的说，哈希表是一种数据结构，它有一个映射函数（哈希函数），可以根据要存储的值直接计算出存储的位置。这样就可以存储。要访问的时候，再一次输入相同的值，根据存储位置直接访问。类似于字典的键值对，可以想象字典dict的key和value，存储的时候直接“dict[key]”，访问的时候直接“dict.get(key)”。
其实哈希表关键之处在于映射函数（散列函数，哈希函数）。比如需要存储17,3,6,19,24五个数，存储在长度为10的列表中，那么该如何存储呢？可以构建一个映射函数，最常用的就是采用取余法，每个数值对10取余，17%10=7，那么就存在下标为7的位置上，3%10=3，存储在下标为3的位置上。以此类推，这样这五个数分别存储在下标为“7,3，6,9，4”的位置上。当我们查找的时候，还是用求余法，计算出其下标位置，直接访问看看有没有这个数值即可。
当然，求余法是不完美的，假如又来了一个数，比如27，那么利用求余法计算出的下标为7，而下标7的位置已经存储17了，这就是所谓的冲突现象。那这该怎么办呢？这就需要解决冲突了。
解决冲突的方法主要有两种，一种是再散列，就是产生冲突后，向后寻找一个空的位置存储，向后寻找的话，那么又分为多种，下标加1，加2，加n等等。当然查找的时候如果首次没有找到，就需要额外的根据再散列规则进一步遍历查找了。
另一种方法就是在每个下标处增加一个表，也就是二次嵌套。当产生冲突后，将元素存储在这个嵌套表里面，这样在嵌套表里面遍历就行，这其实是顺序查找和哈希查找的一种折衷。同样也可以存储的时候排序一下，查找的时候用二分查找也行。
理想情况下的散列函数是完美的，即不会造成冲突，且容易计算。流行的有MD5，SHA系列函数。虽然有论文已经发现有些数值会造成冲突，但在实际使用过程中，并没有发生过。
散列函数除了用于存储数据，其他用途也有很多，比如说文件校验，密码校验等等，常说的MD5校验码就是用MD5函数计算出散列值。文件校验就是用来检验文件内容是否相同，在检验文件的时候，我们不可能一个字节一个字节的去比较，而是将文件内容作为散列函数的输入，计算出散列值，然后比较散列值是否相同即可。还有密码校验，随着网络安全的发展，逐渐不再传递明文密码，而是根据明文密码生成其散列值，用于对比是否密码正确。类似的还有区块链技术，也是用散列函数计算散列值用于链接分布式数据库各个区块。还有比特币等等。
