哈希算法（Hash）又称摘要算法（Digest），它的作用是：对任意一组输入数据进行计算，得到一个固定长度的输出摘要。

哈希算法最重要的特点就是：相同的输入一定得到相同的输出；不同的输入大概率得到不同的输出。

哈希算法的目的就是为了验证原始数据是否被篡改。

// Java字符串的hashCode()就是一个哈希算法，它的输入是任意字符串，输出是固定的4字节int整数：
"hello".hashCode(); // 0x5e918d2
"hello, java".hashCode(); // 0x7a9d88e8
"hello, bob".hashCode(); // 0xa0dbae2f

哈希碰撞是指，两个不同的输入得到了相同的输出。一个安全的哈希算法必须满足：碰撞概率低，不能猜测输出。

"AaAaAa".hashCode(); // 0x7460e8c0
"BBAaBB".hashCode(); // 0x7460e8c0

1. 常用的哈希算法

根据碰撞概率，哈希算法的输出长度越长，就越难产生碰撞，也就越安全。

散列表（Hash Table），也叫“哈希表”或者“Hash表”。是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。

通常，我们把这个关键字称为 Key，把对应的记录称为 Value，所以也可以说是通过 Key 访问一个映射表来得到 Value 的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫作散列表。

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。

Hash，一般翻译做“散列”/“哈希”，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。 (这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，这种现象叫作碰撞（Collision）。) 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

对散列表中的键(key)进行Hash的函数就是散列函数（Hash(key)）。函数的计算结果就是散列值,就是Hash(key)的值。

1. 几种常见哈希函数：

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址；如Hash(key)=key或者Hash(key)=a*key+b，a和b都为常数。
• 数字分析法：如果关键字由多位字符或者数字组成，就可以考虑抽取其中的2位或者多位作为该关键字对应的散列地址，在取法上尽量选择变化较多的位，避免冲突发生。
• 平方取中法：对关键字做平方操作，取平方值的中间几位作为散列地址。此方法也是比较常用的构造哈希函数的方法。计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留余数法：若已知整个哈希表的最大长度m，可以取一个不大于m的数p，然后对该关键字key做取余运算，即：Hash(key)=key%p。
• 随机数法：取关键字的一个随机函数值作为它的哈希地址，即：Hash(key)=random(key)，此方法适用于关键字长度不等的情况。

构建哈希函数，需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面：

跳表（Skip List）是一个动态数据结构（链表加多级索引），可以支持快速地插入、删除、查找操作的有序链表。 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

1. 跳表的演化

跳表的原始链表是一个有序单链表，如果要想在其中查找某个数据，只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。

栈（Stack）和队列（Queue），严格意义上来说，也属于线性表，是一种操作受限的线性表数据结构。 使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈； 使用队列存储数据，讲究“先进先出”，即最先进队列的数据，也最先出队列。

1. 栈

栈（Stack）是一种只能从一端存取数据且遵循“先进后出”原则（First In Last Out，简称FILO）的线性存储结构。 通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。 栈只支持两个基本操作：入栈push()和出栈pop()。

线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。比如数组，链表、队列、栈等也是线性表结构。 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

1. 数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

数据结构与算法解决的是：如何让计算机更快时间、更省空间的解决问题。 因此需要从执行时间和占用空间两个维度来评估数据结构和算法的性能，二者统称为复杂度。 复杂度描述的是算法执行时间或占用系统空间与数据规模的增长关系。

和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

1. 时间复杂度与空间复杂度

大O表示法：所有代码的执行时间T(n)与每行代码的执行次数f(n)成正比，用T(n) = O(f(n))表示，其中n表示数据规模的大小