线性数据结构----(数组,链表,栈,队列，哈希表)

线性数据结构

数组
链表
栈
- 使用场景
队列
- 应用场景
哈希表
- 特点
- 哈希函数，哈希值，哈希冲突
- - 键值对 Entry
- 开放寻址法和拉链法
参考文档

数组

数组(Array) 是一种很常见的数据结构。由相同类型的元素组成，并且是使用一块连续的内存来存储的。
在数组中我们可以直接利用元素的索引（index）计算出该元素对应的存储地址。

数组的特点是：随机访问，但容量有限

  int[] arr = new int[n];
  访问：O（1）//访问特定元素
  插入/删除：O（n）//插入到数组头，或删除数组头元素--》都需要将数组中所有元素进行移动操作

链表

有趣的理解（只是便于理解）
可以这么理解链表

  把链表看成一个家庭关系（只查单线哈），把链表中的数据看成家庭里的人。
  
  有一天啊，来你家做人口调查
  怎么查呢？按常理--》从最年长的开始，比如：
  爷爷
  爷爷的孩子--》爸爸
  爸爸的孩子--》你
  你--》null
  
  这里，每个人，就相当于链表中的一个数据元素，
  它包括了爷爷本身 和 从爷爷出发找爸爸的指针
  同理，爸爸 也包括了它自身 和 指向你的指针
  你没有孩子，所以指针为空
  
  这就是，单链表

链表分类（常见）
- 单链表
- 双向链表
- 循环链表
- 双向循环链表
链表由一系列节点（链表中每一个元素成为节点）组成，节点在运行时动态生成，每个节点包括两个部分：
```
  - 数据域：存储数据元素
  - 指针域：存储下一个节点地址
```
- 单链表
- 循环链表
  尾节点不指向null，而是指向头结点
- 双向链表
  包含两个指针，一个prev指向前一个节点，一个next指向后一个节点
双向循环
链表（LinkedList）
- 虽然是一种线性表，但它和数组不同，它不是顺序存储的，而是使用不连续的内存空间存储数据（链表的结点一般都有后继指针next–》指向后面的元素存储位置）。
- 因此，插入和删除操作：O（1）；查找O（n）；
- 这种结构可以克服数组需要预先知道数据大小的缺点，充分利用计算机的内存空间，实现灵活的内存动态管理。
- 同时，也因此链表不具有数组的随机读取的特点（必须知道目标位置元素的上一个元素）
数组VS链表
- 数组可以随机访问，链表不可以随机访问
- 如果需要存储的数据元素的个数不确定，并且需要经常添加和删除数据的话，使用链表比较合适
- 如果需要存储的数据元素的个数确定，并且不需要经常添加和删除数据的话，使用数组比较合适
- 数组使用的是连续的内存空间，对CPU的缓存机制友好，链表则相反
- 数组大小固定，而链表天然支持动态扩容。如果声明的数组过小，需要另外申请一个更大的内存空间放数组元素，然后将原数组拷贝进去（这个操作是比较耗时的！）

栈

栈（Stack）就像个无顶的盒子
只允许在有序的线性数据集合的一端（称为栈顶top）进行加入数据（push）和移除数据（pop）的操作。
因而按照后进先出（LIFO，last in first out）的原理运作。
在栈中，push和pop的操作都发生在栈顶

在这里插入图片描述

栈常用一维数组或链表来实现，用数组实现的栈叫做顺序栈，用链表实现的栈叫做链式栈。

使用场景

eg.实现浏览器的回退和前进功能

队列

可以把队列看做是食堂打饭的队伍
队列（Queue）是先进先出（FIFO，first int first out）的线性表。

应用场景

当我们需要按照一定顺序来处理数据的时候，可以考虑使用队列这个数据结构。

哈希表

百科解释：

散列表（Hash
table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

特点

提炼一下：

哈希表（也叫散列表）。
哈希表本质是一种数据结构----》特点：可以根据一个key值直接访问数据，因此查找速度快

提到数据结构，特点是查找速度快的还有什么呢？

数组—》所以，Hash Table本质就是一个数组
？？？那它跟数组有什么区别呢？

哈希函数，哈希值，哈希冲突

这有一个例子：

  eg.在电话表里找“王三”这个人
  - 如果是数组，怎么找呢？---》遍历
  	for(...){ if(...)... }
  - 那哈希表呢？
  我们把电话表中的数据，按照首字母进行分类
  然后，查找 ‘w’ 里面的数据
  从而，找到 “王二”

这里，我们把按首字母排序这个方法叫做哈希函数（散列函数）

键值对 Entry

这还有个不算例子

  我们都知道，哈希表经常存放的是一些键值对（key，value），jdk中把键值对叫做Entry。这是啥意思呢？
  就是key对应着value
  也就是value是由key通过哈希函数映射来的
  value就叫做哈希值（hash值）

啥玩应？

这是个例子：

  eg. 王二的学生信息：002，王二
  
  我们根据之前说的，要有一个哈希函数，
  假设哈希函数的作用是 将002--》0
  那么 key = 0；value = 王二
  
  （0，王二）就是一个键值对(key,value)
  根据 0，我们可以查找出 王二 来

那如何把kv对存到哈希表中呢？

	我们说了，哈希表本质还是个数组嘞
	根据 key 的值，就可以把value存到对应的位置上去

在这里插入图片描述
那这就有个问题了？

	如果 还有个学生 （007，翠花）
	key=0 value=翠花
	那不就和 王二的key冲突了吗？

这个就叫做哈希冲突（也叫做哈希碰撞）
怎么解决？

开放寻址法和拉链法

开放寻址法
在这里插入图片描述
这里会一直找不到空位置吗？

  不会的，对于HashMap来说，当它的增长因子（也叫负载因子），到达0.7--》比如，一共10个位置，被占了7位，那就要扩容了
  扩容 是create一个数组，是原来的2倍，然后把原数组的所有Entry都重新Hash一遍，放到新数组中
  
  重新hash 就是：把之前的数据，通过新的哈希函数计算出新的位置来存放。（因为数组扩大了，所以一般哈希函数也会有变化，就需要重新hash一遍）