数据结构
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
解决问题方法的效率，跟数据的组织方式有关，跟空间的利用效率有关，跟算法的巧妙程度有关。
常用数据结构：数组、栈、队列、链表、树、图、堆、散列表（哈希表）
数组
数组是一种最简单的数据结构，它占据一块连续的内存并且顺序存储数据，所以我们需要首先指定数组的大小。
数组的特点：
- 数组中所有元素的类型都必须相同(都为int、double等)。
- 数组中的元素在内存中都是相连的。
- 数组支持顺序访问和随机访问。
- 数组的读取速度很快。
- 数组的插入和删除比较困难。
链表
链表是一种在物理内存上不连续的数据结构。
链表的特点：
- 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
- 在链表中添加元素很容易:只需将其放入内存，并将其地址存储到前一个元素中。
- 链表只支持顺序访问。
- 链表的插入和删除速度很快。
- 链表的查询速度很慢，因为必须要一个元素一个元素顺序查找。
- 相比数组只存储元素，链表的元素还要存储其它元素的地址，内存开销相对增大。
常见数组和链表操作的运行时间
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
栈
- 栈是一种后进先出(Last In First Out，LIFO)的数据结构。
- 栈有两种操作：压入和弹出。
队列
- 队列是一种先进先出(First In First Out，FIFO)的数据结构。
- 队列有两种操作：入队和出队。
哈希表（散列表）
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
hash就是找到一种数据内容和数据存放地址之间的映射关系。
当使用哈希表hashtable(key，value) 进行查询的时候，就是使用哈希函数将关键码key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。
Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。
应用
- 将散列表用于查找，例如：DNS解析
- 防止重复
- 将散列表用作缓存
哈希冲突
哈希冲突(hash collision)：哈希函数将两个不同的键映射到同一个索引的情况。
哈希冲突是不可避免的，如果遇到冲突，最常用的解决办法就是开放定址法和链地址法。
开放定址法
开放定址法是遇到冲突的时候查找顺着原来哈希地址查找下一个空闲地址然后插入。
但是也有一个问题就是如果空间不足，那他无法处理冲突也无法插入数据，因此需要装填因子(空间/插入数据)>=1。
链地址法
链地址法的原理时如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。
性能
在平均情况下，散列表执行各种操作的时间都为O(1)。O(1)被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。
在最糟情况下，散列表所有操作的运行时间都为O(n)——线性时间，这真的很慢。我们来将散列表同数组和链表比较一下。
| 数组 | 链表 | 散列表平均情况 | 散列表最糟情况 | |
|---|---|---|---|---|
| 查找 | O(1) | O(n) | O(1) | O(n) |
| 插入 | O(n) | O(1) | O(1) | O(n) |
| 删除 | O(n) | O(1) | O(1) | O(n) |
在平均情况下，散列表的查找(获取给定索引处的值)速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点!但在最糟情况下，散列表的各种操作的速度都很慢。因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有:
- 较低的填装因子
- 填装因子：散列表元素数 / 位置总数
- 填装因子大于1意味着元素数量超过了数组的位置数。
- 一旦填装因子开始增大，你就需要在散列表中添加位置，这被称为调整长度(resizing)，通常将数组增长一倍。
- 一个不错的经验规则是:一旦填装因子大于0.7，就调整散列表的长度。
- 良好的散列函数
- 最理想的情况是：散列函数将键均匀地映射到散列表的不同位置。
- 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很 好，这些链表就不会很长!
树
图
堆
算法
- 一个有限指令集
- 接受一些输入（有些情况下不需要输入）
- 产生输出
- 一定有限步骤后终止
- 每一条指令必须：
- 有充分明确的目标，不可以有歧义
- 计算机能处理的范围之内
- 描述应不依赖于任何一种计算机语言以及具体的实现方式
