数据的存储结构
内容摘要
本文章讲述了在程序设计中常用的四种数据存储结构，对比阐述了它们的优缺点。重点说明了散列函数、散列表的冲突及其解决方案。
概述
数据的存储结构分为：
- 顺序
- 链式
- 索引
- 散列
数据的存储结构是针对计算机来说的，指的是数据的逻辑结构在计算机中的表示，也就是说这些数据存储在计算机中到底是怎么存储的。
我的一些观点
我个人认为对于数据的存储来说，顺序和链式结构是两种最基本的存储数据的方式。索引是在链式结构基础上的一种拓展，而且对于索引存储中的key来说，可以用链式存储也可以用顺序存储；与之对应的value大部分情况下是链式存储的（毕竟找到了key就找到了value，所以一般来说没有必要必须顺序），但是在数据库中，为了减少碎片，会使用顺序存储。而散列（哈希，这里特指散列存储，而不是加密）在我看来更像是一种存储思想。
为什么有不同的数据结构
人们对于数据的操作无非就5点：增加（append）、删除（drop）、更新（update）、插入（insert）、查找（query），为了更快、更方便地执行这些操作，我们创造出了很多存储数据的方式。这些存储方式都不是完美的，它们只有在不同的应用场景下才能发挥出最好的表现。
所以我们在比较不同数据结构时，大都是围绕着以上5点操作和储存体积展开的。
顺序结构
在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。
特点
- 随机存取表中元素：即在所分配的存储表中，对一个存储需求会随机选择一个存储单元进行存储。
优点
- 比链式结构的数据密度要大；
- 查找的时间复杂度为\(O(1)\)；
缺点
- 对于表来说，一开始大小就固定了，所以插入（插入是从中间插入，和增加不同；增加是加在末尾，增加的复杂度是\(O(1)\)）和删除复杂度较高，通常会达到\(O(n)\)；
链式结构
不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系。
特点
- 每个结点除了数据外还有一个指针（这个指针的指向会根据逻辑结构来定，可以是前置结点，也可以是后继结点）；
优点
- 逻辑上相邻的元素在物理存储中不一定相邻；
- 插入和删除时间复杂度是\(O(1)\)；
缺点
- 比顺序存储的数据密度要小（因为指针域要占一定的空间）；
- 查找数据的开销很大，时间复杂度为\(O(n)\)；
索引（这一部分内容不是很完善，请慎用）
除建立存储结点信息外，还建立附加的索引表来标识结点的地址。索引表由若干索引项组成。
特点
- 索引存储结构是用结点的索引号来确定结点存储地址；
优点
- 检索速度快。
缺点
- 增加了附加的索引表，增加了空间开销。
散列（哈希）
散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
- 它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，查找的期望时间为\(O(1)\)。
若键为k，其值放在f(k)地址处，可以不需要比较就能根据关系f找到值。这个关系f称为散列函数，根据散列函数建立的表叫散列表。
基本思想
由节点的关键码值决定节点的存储地址。用键来直接访问内存位置的数据结构。实现这种思想的关键就是构造一个hash函数，这个函数会实现从键到内存位置的映射。
它不仅可以用于查找，还可以用于存储。这种思想还可以用于加密。
特点
- 不可逆。按道理来说，其实是否可逆与你设计的散列函数有关，但是因为不需要从存储地址映射到键，所以没有必要可逆。
常用的散列函数
- 如果关键字（以下简称键）是字符or字符串，则可以用他们的ASCII码之和作为关键字。
直接定址法
直接将键做为地址，或者是将键的线性变化作为地址。\(hash(x)=ax+b\)，其中\(a,b\)均为常数。
平方取中法
取键平方后的中间几位作为地址。
平方扩大键之间的差别，而中间几位都乘以过乘数，这样散列得比较均衡。
除留余数法
取一个数\(p，p<hashTableSize\)，用键取模\(p\)后的值作为地址。\(hash(x)=x\ MOD\ p\)。
- 在使用除留余数法时，对p的选择很重要。一般情况下可以选p为质数或不包含小于20的质因素的合数。
折叠法
把键为切分为相同的几段（最后一段可以不相同），然后这几段相加去掉进位来作为地址。
随机数法
顾名思义，\(hash(x)=random(x)\)。
相乘取整法
取一个常数\(A,0<A<1\)，\(hash(x)=round(hashTableSize \times decimal(x\times A))\)，decimal是取小数，round是四舍五入。
- 该方法最大的优点是m的选取比除余法要求更低。比如，完全可选择它是2的整数次幂。
- 虽然该方法对任何A的值都适用，但对某些值效果会更好。如黄金比例。
加密算法的散列
一些加密算法也用到了散列的思想，比如MD5。
散列表的冲突（碰撞）
我们设键为\(x\)，散列函数为\(f\)，地址为\(y=f(x)\)。
在离散数学中，函数是两个集合之间的映射关系。很多时候我们希望\(x\)和\(y\)是一对一映射，但是这往往无法做到，因为对散列函数的设计要求太高了。所以绝大部分时候，不同的键可能会映射成相同的地址，即\(\exists\ x_1,x_2,有f(x_1)=f(x_2)\)，我们称这种情况为散列表的冲突。
冲突的解决方案
分离连接法（开散列、链地址法、开链法）
开放定址法（闭散列、开地址法）
Open address。
评判标准
应用
有hash的索引
当我们使用数组、集合等多数据作为索引，并且所有的索引都可能被访问（甚至多次被访问）时，可以设计hash函数来减少索引之间重复比较的时间复杂度。即构建一个hash函数，利用这个函数计算索引的“特征值”。
这个过程在没有冲突的情况下时间复杂度为\(O(mnlogn)\)，n是集合或数组的数量，m是里面的元素数量。这种方案可以避免后续比较带来的计算开销（仅仅只多了一个“特征值”的空间开销）。
- “特征值”的计算可以是懒惰的，它可以在被比较的过程中进行计算。
- 如果作为索引的集合或者数组允许它里面的元素无序，那此方案性能将会更加优异。
注意：
这个方案在建立“特征值”时：
- 最坏情况时间复杂度和普通比较一样；
- 最好情况时间复杂度和平均时间复杂度均比普通的比较差。
但是在建立“特征值”后且没有冲突时：
- 最好情况时间复杂度和普通比较一样；
- 最坏情况时间复杂度和平均时间复杂度均大大优于普通比较。
注意2：
此方案和创建双重索引是有区别的。
具体区别等我想起来了再写:) 23333