散列表（也叫哈希表），是根据键而直接访问在内存存储位置的数据结构。在这篇文章中，我们将介绍散列表的基本原理。通过了解散列表的基本原理，有助于我们理解散列表的工作方式。
1. 介绍
散列表是一种通过与其所包含的元素相关联的对象来访问元素的容器，这种与元素相关联的对象在散列表中被称为“键”。也就是说，对散列表中元素的添加、查找、修改、删除等操作必须通过与元素所对应的键才能进行。因此，散列表中的元素所对应的键在同一个散列表对象中是唯一且不可变的，即同一个散列表中不会出现两个相同的键；并且在元素确定的情况下，其对应的键是不可变的。
散列表提供了一种高效的元素使用方式，在理想情况下 [1]，访问元素的时间复杂度能够达到O(1)。
2. 基本原理
散列表中存储的每一个元素都会有唯一一个与之对应的键，形成一一对应的关系 [2]，散列表对某个元素的操作都是通过元素所对应的键进行，元素在散列表结构中存储的位置也是由其对应的键所决定的。
在添加元素时，散列表会先通过一个确定的散列函数 [3]，将需要添加的元素所对应的键转化为一个整数值，这个数值可用于确定散列表结构内的某个位置，一旦存储的位置确定后，散列表将把这个需要添加的元素以及其对应的键以键值对的形式存储在这个位置。
元素添加后，若需要访问这个元素，就必须向散列表提供与需要访问的元素对应键，散列表仍然会通过那个确定的散列函数，将这个指定的键转化为一个整数值，即可根据这个数值找到散列元素所存储的位置。
散列表之所以可这种方式访问元素，就是其散列函数能够保证：对于同一个指定的键，在确定的散列表结构中将总是得到同一个数值。
3. 数据结构
为了能够高效存取，散列表使用了顺序结构与链式结构混合的方式来实现 [4]。散列表的数据结构大致如图 1。其中黑色部分为链式结构，棕色部分为顺序结构。
图 1 中的棕色部分的顺序结构在每一个散列表对象有且仅有一个，它在散列表中被称为“表”。
之所以采用这样的结构是有几个原因，第一，元素的键通过散列函数所转化出的整数，经过计算后直接对应于顺序结构中的某个位置，可实现高效的随机存取；第二，如果不同的键经过散列函数计算后得到了相同的值，则需要使用链式结构来表示这些元素在逻辑上被放置于同一个位置。
一旦明白散列表的数据结构后，也就不难明白散列表访问元素时的流程了：
1. 将指定的键通过散列函数转化为一个整数值 n。
2. 使用这个得到的数值 n 计算出一个表中的合法位置 x ，访问这个 x 的位置。
3. 如果表中的 x 位置没有任何对象，则说明散列表中目前并没有指定键所对应的元素。
4. 如果表中的 x 位置有指针指向某个对象，那么这个对象一定是一个链式结构的起始。依次检查链式结构的每一个节点，如果有某一个节点的键与指定的键一致，则说明找到元素；如果没有找到，则说明散列表中目前并没有指定键所对应的元素。
4. 元素记录
散列表中的每一个元素必须拥有一个与之对应的键，并且在发生散列冲突的时候，这些元素还要能够自发组织为链式结构。为了满足这些要求，散列表的元素以及其对应的键通常被放置于一种结构体中，这种结构体在散列中被称作“记录” [5]，如图 2。
其中，value 为散列表的元素，key 为这个元素对应的键，next 指向下一个发生散列冲突的记录。如果将图 2 与图 1 联系起来看的话，就是图 1 中的每一个黑色矩形，其细节就如图 2 所示。
5. 散列值与索引
现在已经知道了散列表中数据结构的形式，那么接下来思考这么两个问题：1. 散列表如何将指定的键转化为整数；2. 如果将散列表的表视作一个数组，散列表是如果将这个整数转化为其合法的索引下标。
明白了第一个问题，也就明白了什么是散列值。通常，某个对象一旦创建之后，它在内存中的地址将是不变的，如果某些语言的内存模型并不是这样，那么它一定会提供某种标识一个对象的方式。这种标识对象的方式可以将之视为一串二进制值，不论其原本表示的意义是什么，二进制值都可以按照整数的方式去解析它，最终，总是能够得到一个整数值。
明白了第二个问题，也就明白了如何通过散列值得到散列表的表索引 [6]。散列表在设计上巧妙的利用了按位与运算。二进制的按位与运算是在相同的位上如果两个值同为 1，则得到 1，否则得到 0 。例如 1010 & 0011 = 0010、111 & 101 = 101。如果以十进制书写，就是 10 & 3 = 2、7 & 5 = 5，也就是有这样一个特点： A & B 如果将A、B视为无符号整数，其结果一定大于等于 0 且小于等于 A 且小于等于 B。一个在区间 [0, n]的整数，可作为长度为 n+1 的数组的合法索引。推出：一个长度为 n+1 的数组，用其长度减 1 的值（n + 1 - 1 = n）去和任意一个二进制数进行与运算，得到的结果一定是这个数组的合法索引。同时，为了能够最大限度的利用二进制的每一位，最好的方式就是 n 的结果转化为二进制后每一位都是 1 ，这样的 n 就是 1, 3, 7, 15, 31...，那么 n+1 就是 2, 4, 8, 16, 32...。[7]
6. 散列冲突
前面章节中，已经知道了散列表根据元素的键获取散列值的表索引的原理。现在假设有一个散列表的表长为 8，现在需要添加两个元素，散列值分别为 0010 和 1010。使用表长减 1 的值分别与键的散列值进行按位与运算，得到的结果都是二进制的 0010，也就是十进制的 2。此时，对于散列值分别为 0010 和 1010 的两个键来说，就出现了相同的索引，称为“散列冲突”。
一旦发生了散列冲突，也就是散列表尝试将多个元素放置于同一个位置，此时，链式结构就发挥作用了。散列表添加元素具体过程如下：
1. 将指定的键通过散列函数转化为一个整数值 n。
2. 使用这个得到的数值 n 计算出一个表中的合法位置 x ，尝试将元素放置于这个 x 的位置。
3. 如果表中的 x 位置没有任何对象，则根据指定的元素和对应的键创建一个新的记录，然后将表中的 x 位置的指针指向这个新创建的记录。
4. 如果表中的 x 位置有指向某个已有记录的指针，则根据指定的元素和对应的键创建一个新的记录，使这个新记录的 next 指向当前表中 x 位置上已有的指针所指向的记录，然后将表中的 x 位置的指针指向这个新创建的记录。
根据以上过程可以作出假设，如果不停的向散列表中添加散列冲突的键，最终结果就是这个散列表的表中除那个特定的位置有记录外，其他位置都是空，并且所有记录都以链式结构的方式排列在一起。此时散列表访问元素的时间复杂度变为 O(n)，到达最坏情况。[8]
7. 扩容
如果散列表中放置了很多的元素，即使添加的元素的键之间发生最少次数的散列冲突 [9]，也会使得散列表访问元素的时间复杂度增加。此时 [10]，散列表将会扩大表的长度以尝试减少各个链式结构的长度，从而改善访问元素的时间复杂度。扩容前后的结构对比如图 3。
由图 3 可以看出，扩容后的散列表中各个元素所处的链式结构的长度都减少了，这就使得散列表的时间复杂度下级降，趋近于O(1)。
读完这篇文章，你可以继续阅读《JDK 1.7 HashMap 解析》，该文章将在代码的层面上继续深入解释散列表。
[1] 理想情况是指：添加元素时，不出现散列冲突、不出现表扩容；得到元素时，已有的所有元素不存在散列冲突。
[2] 一种特殊的情况是：如果有多个键，它们对应的值都是指针（引用），并且这些指针都指向同一个对象。那么，站在对象的层面上来看，就会出现多个键对应同一个值。
[3] 散列函数是一种用于将一个任意类型的对象（包括 Null），根据代码中定义的某种标识对象的特征，获取一个具体数值的函数，得到的数值被称为这个对象的“散列值”。散列值与对应的对象的之间的关系通常为：如果两个对象相同，对应的散列值一定相同；如果两个对象不相同，对应的散列值不一定不相同；如果两个散列值不同，对应的对象一定不相同；如果两个散列值相同，对应的对象不一定相同。
[4] 散列表的表的数据结构有多种实现方式，在这里我们仅讨论其中一种比较典型的方式。
[5] 散列表的记录的数据结构有多种实现方式，在这里我们仍然仅讨论其中一种比较典型的方式。
[6] 散列表将对象散列值转化为表的索引的方式有多种实现方式，在这里我们还是仅讨论其中一种比较典型的方式。
[7] 这也就是散列表的表长度一定是 2 的 n 次幂的原因。（基于我们上面所讨论的实现方式）
[8] 这种散列表的最坏情况在我们上面所讨论的实现方式中是不可避免的，这种情况是所有键对外透露的特征都是相同的，但他们却彼此不相等。比这种情况稍微好一点的情况是所有键对外透露的特征虽然不同，但是在计算索引的函数中都返回了相同结果，此时可将链式结构由链列转为查找树即可有所改善。
[9] 最少散列冲突是指：当添加的键的散列值足够离散，但由于散列表的表不够长，迫使某些元素的键产生散列冲突。例如，一个表长为 8 的散列表，向其中添加 16 个元素，即使在最好情况下，也就是表中每一个位置都放置了记录，但这些记录所处的链式结构长度都为 2。
[10] 通常，散列表不会在元素被放满才进行扩容，而是会有一个阈值，当散列表添加元素时，散列表中的元素数量大于这个阈值，并且这个新添加的元素的键发生了散列冲突，就会进行扩容，以最大化利用我们上面所讨论的结构。
