众所周知，计算机只能按顺序储存二进制数，存储单位是字节（8位二进制数），因此计算机实际上只有一种储存方式——按字节顺序储存。

　　实际的数据是多种多样，为了能用计算机储存数据结构（结构化集合），把数据结构中的元素分为两类：一类是原型数据元素，一般包括整型数和浮点型数，具有固定的字节长度；另一类是对象（Object）数据元素，字节长度可变。

　　对于只有原型数据元素的数据结构（例如整数列表[0,3,5,9,3,4,6]），可以把元素本身按顺序储存在计算机中（Python不一定这样做的，这里只是为了说明问题）；对于只有对象数据元素的数据结构（例如字符串列表["Hello","world","Python","Good!"]），可以把元素本身储存后返回句柄（指针，一个整型数），按顺序把句柄储存在计算机中。这两种储存数据结构的方法就叫做顺序存储结构。

　　Python的列表中的元素看起来是可以包括原型数据元素和对象数据元素的，例如[1,2,3,"HelloWorldPython"]是合法的，它又如何实现储存的呢？也许Python能实现原型数据的自动打包（对象化）然后采用对象储存方法。在需要使用这个数据时进行相反的过程自动解包（去对象化或原型化）。Python的这种灵活性是以损失性能为代价的。如果要编写高性能的程序，一是用C/C++、Fortran等提供原型数据操作的编译语言；另一种是用这些编译语言编写库模块，然后用Python作为输入输出终端调用这些库模块（例如numpy）。

　　我们可以忽略储存细节，把元素的储存位置分为两种逻辑关系：相邻和不相邻。

　　（一）顺序存储结构：逻辑上相邻的元素在计算机内也相邻叫做顺序存储结构。

　　顺序存储结构采用一段连续的存储空间，将逻辑上相邻的元素（或元素的指针）存储在连续的空间内，中间不允许有空。顺序存储结构可以通过“下标”快速定位第几个元素，但由于元素间没有空位置，在插入和删除数据时，可能需要移动大量元素，如下图（来源参考资料1）所示。

　　短时间内移动大量元素，会消耗较多的CPU计算资源、造成内存碎片，可能会造成某些应用的卡顿。为了说明问题的需要，不管Python实际的实现方法，只从形式上考虑，认为Python的列表和元组属顺序储存结构。

　　如果想保持数据结构的逻辑顺序，但又可以在添加或删除时无需移动其他元素，应该怎样做呢？解决方案的一种是：

　　（二）链式存储结构：逻辑上相邻的元素在计算机内存中的存储位置不要求必须相邻，逻辑相邻元素借助元素的指针域定位下一个元素的地址。

　　链式存储结构的优点是可以利用碎片位置，可以实现快速增加和删除数据；缺点是需要额外空间存储指针域，不能实现随机访问(下标访问）。有单向链式（只有指向后继元素指针域）和双向链式（有指向前导和后继元素的指针域）等。下图（来源网络）所示各种列表的拓扑结构：

　　下图（来源网络）举例说明链式储存结构是如何添加和删除节点的。

　　链式存储结构虽然达到了快速删除和添加元素的目的，但由于不能随机访问，定位元素速度慢，适用的情景不太多（在一些寻宝游戏中使用）。举个例子，假如有一本链式词典，要查“yes”，从“a”开始，顺藤摸瓜，一直到“yes”那不知要多少时间！

　　有没有一种储存方式，能像链式存储结构一样快速删除和添加元素，又能像顺序储存结构一样快速定位元素呢？

　　（三）散列存储结构：散列存储结构也称为哈希存储(Hash)结构，是由节点（数据元素）的关键码值通过散列函数决定节点的存储地址。

　　节点（数据元素）的关键码是数据元素的身份证号码，与节点有一一对应的关系；散列函数及其冲突解决方法（附录１）能够实现关键码与内存地址一一对应的关系，从而使节点与储存位置有确定的联系，达到快速查询、添加、删除节点等操作。下图（来源参考资料１）所示（冲突解决办法是单向链式储存）。

　　计算机也可以像书本一样储存数据。

　　（四）索引存储结构：指除建立在存储节点信息外，还建立附加的索引表来表示节点的地址，索引表是由若干索引项组成。

　　索引储存结构就像字典一样，有目录（索引表），能够通过关键字对应数据元素的内存地址，因此检索速度快。但附加的索引表额外占用存储空间，增加和删除数据时也要修改索引表，会花费多余时间。索引存储结构如图下图（来源参考资料1）所示。

　　为了说明数据结构问题，我们只从形式上来看，Python的字典（如{"a":4,"b":"123"}）是一种索引储存结构。

　　数据结构的基本运算包括：创建数据结构，清除数据结构，插入数据元素，删除数据元素，更新数据元素，查找数据元素，按序重新排列数据，判定某个数据结构是否为空，或者是否已达到最大允许容量。统计数据元素的个数等。在后续的章节中对常见的数据结构基本运算进行讨论。

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社

附录１：散列函数及其冲突解决方法（来源百度百科）

　　散列函数是哈希函数的别名，指将哈希表中元素的关键键值映射为元素存储位置的函数。

　　一般的线性表、树中，记录在数据储存结构中元素的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在数据储存结构中查找记录时需进行一系列和关键字的比较的运算。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。我们希望能直接找到需要的记录而无需进行比较，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和数据储存结构中一个唯一的存储位置相对应。哈希函数就是能实现它的方法。

哈希表的概念及作用
　　哈希表中元素是由哈希函数确定的。将数据元素的关键字（key）作为自变量，通过一定的函数关系（称为哈希函数），计算出的值，即为该元素的存储地址。表示为：

Addr = H（key）

　　为此，在建立一个哈希表之前需要解决两个主要问题：

　　（１）构造一个合适的哈希函数；
　　（２）冲突的处理。
　　冲突：在哈希表中，不同的关键字值对应到同一个存储位置的现象。即关键字K1≠K2，但H（K1）= H（K2）。

哈希表的构造方法

直接定址法
　　例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。

数字分析法
　　有学生的生日数据如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。

平方取中法
　　取关键字平方后的中间几位为哈希地址。

折叠法
　　将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。

除留余数法
　　取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)

随机数法
　　选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key)=random(key），其中random为随机函数。通常用于关键字长度不等时采用此法。
　　若已知哈希函数及冲突处理方法，哈希表的建立步骤如下：
　　Step1.　取出一个数据元素的关键字key，计算其在哈希表中的存储地址D=H(key）。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；否则发生冲突，执行Step2。
　　Step2.　根据规定的冲突处理方法，计算关键字为key的数据元素之下一个存储地址。若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。

冲突
　　无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，要有一些方法可以避免冲突。

拉链法
　　拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。

多哈希法
　　设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低（几乎不可能冲突）。

开放地址法
　　开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1）
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,...m-1，称线性探测再散列。
　　如果di取1，则每次冲突之后，向后移动1个位置。如果di取值可能为1,-1,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2）
　称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

建域法
假设哈希函数的值域为[0,m-1]，则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。