漫画算法-小灰的算法之旅-数据结构基础（二）
1. 逻辑结构和物理结构
- 逻辑结构：
- 线性结构：
- 顺序表、栈、队列
- 非线性结构：
- 树、图
- 线性结构：
- 物理结构：
- 顺序存储结构：
- 数组
- 链式存储结构：
- 链表
- 顺序存储结构：
2. 数组 VS 链表
相关操作的性能：
| 查找 | 更新 | 插入 | 删除 | |
| 数组 | O(1) | O(1) | O(n) | O(n) |
| 链表 | O(n) | O(1) | O(1) | O(1) |
可以看出，数组的优势在于能够快速定位元素，对于读操作多、写操作少的场景来说比较合适；链表的优势在于能够灵活地进行插入和删除操作，如果需要在尾部频繁插入、删除元素，链表更合适。
3. 栈
栈的数组实现：
栈的链表实现：
入栈出栈的时间复杂度都是O(1)。
栈的应用：
栈的输出顺序和输入顺序相反，所以栈通常用于对历史的回溯，也就死后逆流而上追溯历史。
例如实现递归的逻辑，就可以用栈来代替；还有面包屑导航也是栈的著名应用场景。
4. 队列
队列的数组实现：
为了入队操作方便，可以把队尾的位置规定为最后入队元素的下一个位置。
队列的链表实现：
入队出队的时间复杂度都是O(1)。
循环队列：
当队尾已经达到数组末尾位置，并且队列未满，这时需要入队一个元素，可以将队尾移到数组起始位置。
一直到(队尾下标 + 1) % 数组长度 = 队头下标时，代表队列真正满了。
(4 + 1) % 8 = 5
队列的应用：
队列的输出顺序和输入顺序相同，所以队列通常用于对历史的回放，也就是按照历史顺序，把历史重演一遍。
例如多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的；还有网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，在按照存入队列的顺序来依次抓取和解析的。
5. 散列表
散列表也叫哈希表，这种数据结构提供了键和值的映射关系，只要给出一个key，就可以高效地查找到它所匹配的value，时间复杂度接近于O(1)。
Java中的HashMap：
- put操作过程：
- 通过哈希函数，把key转换成数组下标；
- 如果下标对应的位置没有元素，就把这个Entry填充到对应位置；
- 如果已有元素（由于数组的长度是有限的，当插入的Entry越多时，不同的key通过哈希函数可能得到同样的值，叫做哈希冲突），采用开放寻址法或链表法。
- 开放寻址法：通过某种方法寻找下一个空档位置，如ThreadLocal；
- 链表法：HashMap数组的每一个元素不仅是一个Entry对象，还是一个链表的头结点。
- get操作过程：
- 通过哈希函数，把key转换成数组下标；
- 找到对应下标的元素，判断这个元素的key，如果相同，则返回，如果不同，则在链表中往下找。
- 扩容过程（当经过多次put操作，散列表达到一定饱和度时，哈希冲突的概率逐渐提高，形成很长的链表，对后续的插入或查询操作的性能带来影响）：
- 扩容：创建一个新的Entry数组，长度是原来的2倍；
- 重新hash：遍历原Entry数组，把所有的Entry重新hash到新数组中。
【注】影响HashMap扩容的因素有2个：
- Capacity：HashMap的当前长度；
- LoadFactor：HashMap的负载因子，默认0.75f。
当HashMap.size >= Capacity * LoadFactor时进行扩容。