数据结构基本知识与常见的数据结构二：哈希表、树

哈希

在学习哈希表之前要先了解一下什么叫哈希

hash，一般翻译为散列，是把任意长度的输入，通过哈希算法变成固定长度的输出，输出的值就叫做散列

通过md5算法来了解一下哈希

1
2
3
4
5
6
7
8

import md5 from 'md5-node';

const a = '123456';
const b = 'lalalalalala';
const c = '测试测试宝贝';
console.log(md5(a));
console.log(md5(b));
console.log(md5(c));

在浏览器的控制台查看结果：

e10adc3949ba59abbe56e057f20f883e

3f9b6dcc758a64770bb28ae8c4e5b3ea

a66ae9c7ac9801c50cc5fcdda02e6e10

从console的结果可看出来，一开始的三个变量长度并不一样，最后经过md5算法都输出成一样长度的，输出的这一串就是散列值

这个过程通过md5算法转换的过程叫做哈希转换，这种转换是一种压缩映射，映射表达的是一一对应的关系

哈希的特性

• 哈希算法不能从结果推算输入，哈希算法是不可逆的

• 计算非常快

哈希的用途

1. 密码存储、校验

   通常情况下，我们在各种系统里面提交的登陆密码在数据库里面都是经过哈希算法转换过之后的哈希值去存储的，

   那么哈希算法转换之后的结果是不可逆的，所以通过数据库的管理员并不知道我们的明文密码是什么，

   然后每次登陆的时候，提交密码，都要先经过同样的哈希算法转换一下，和数据库存储的密码的哈希值进行比较，就可以得出两个密码是不是一样的

2. 文件完整校验

   当文件的内容修改过之后，经过哈希转换之后的哈希值也是会变化的，通过比较这两个哈希值，可以检测文件有没有改变

哈希表

我们知道数组在查询数据的时候是比较快速的，但是这个快速是基于我们能够确定我们需要查询的数据的索引值，简单的通过array[index]索引就可以查询

如果我们不知道我们要查询的数据的索引，而是基于内容是查找，就需要遍历整个数组，然后比较，才能拿到想要的数据

思考：如果我们能够将我们查询的内容的值作为索引，是不是知道了内容就能够查询到相关的数据呢？

这个实现就是哈希表，哈希表是基于数组实现的，但是它在插入和删除的操作比数组要快

哈希表的结构就是数组，与数组不相同的是，它的索引是经过哈希转换的

树