数据结构
是大学学习的内容，今天只讲和集合有关的内容，常见的栈，队列，数组，红黑树
栈结构Stack
集合元素先进后出，（出口入口在一侧）给集合添加元素，集合元素第一个进来的直接到栈的最底部，然后依次进入第二个，第三个等等。取出元素，最后进的元素最先出，直到最后出来的是第一个进栈的元素
队列结构Queue
集合元素先进先出，出入口在两侧
数组结构Array
特点：查询快，增删慢
查询快是因为通过数组首地址和索引可以快速定位到元素
增删慢是因为数组长度固定，我们想实现增删，就必须把新建数组把修改后的数组内容赋值过来，原始数组在内存中等待垃圾回收，这就是效率低下的原因
链表linkedlist
特点：查询慢，增删快
查询慢的原因是数组的地址是连续的，而链表不是，每次查询都必须从头开始
增删快是因为链表的结构，每个节点数据存储三块，自身地址，自身数据，和下一个节点的地址，查询必须从首地址依次获得下个节点地址直到索引值增加到指定值的位置
链表又分为单向链表和双向链表，单向链表是无序的，因为存入和取出是可能无序的，双向链表，是因为多了个前一个节点的地址，变成了4块结构，所以其存入取出是有序的
1
其增删过程如上图，我们删除一个节点，只需要把前一个节点的下节点地址换成被删除节点下一个地址值即可，该节点即和前后节点无关联
红黑树结构（平衡二叉排序/查找树）
以二叉树为例（每个节点的分支不超过2个）
2
如上，树的节点的分支又可以当做一棵树，左边左子树，右边右子树，二叉树是没有大小区分的，红黑树是加了限制，左边子树比右边和节点小，右子树比左子树和节点大
3
平衡树，任意节点的左子树节点数量和右子树节点差值不超过1，红黑树满足这个原理，所以排序查找时间复杂度为logn
List集合
之前我们讲过Collection接口的直接子接口为List和Set，这里我们讲List，在java.util下，需要导包，其是有序的，可以使用索引访问（但是索引不要越界），可以存储重复的元素
我们查看文档，比较关心的几个方法是添加删除等等，以代码来说明
4
具体方法多使用来增加熟练
其迭代可以使用3种方法，for i,for each,iterator，代码如下
5
ArrayList类
我们知道其是List的实现类，查看文档可以知道其是长度可变的数组实现的（查询快，增删慢），我们可以看到文档说，数组有扩容操作（当大量添加删除使用多线程+-长度，不是同步的）
6
我们可以ctrkl+B查看文档，使用alt+7调出所有成员方法变量，我们点击add，可以看到其有一个增删使用了grow方法
7
可以看到其会导致容量+1，其他的方法我们在之前已经讲过了，暂时不用太详细讲解
LinkedList类
也是List的实现类，是基于双向链表实现，其查询慢，增删快，其提供了大量开头结尾添加元素的方法
8
其不能使用多态写法，所以使用自身类实例，
9
如上，结果太长，就写代码注释里了，这里pop和removeFirst效果一样
Vector类
是List的又一个实现类，早其是单独的，1.2以后归于Collection,其实现是同步的，所以比其他慢
使用比较少
HashSet类
其是Set接口的实现类，而Set接口继承自Collection接口，其不允许存储重复元素，没有索引，只能使用foreach循环，底层是HashMap实例，不保证迭代顺序，实现是异步的，查询非常快
迭代可使用增强for和iterator
10
如图，重复的元素不会额外添加，然后使用2种方法遍历
哈希表HashMap结构
哈希值，系统给出的随机十进制数，是代表地址的逻辑地址值，不是实际物理地址
Object类有方法hashcode()获取哈希值
11
我们查看文档可以看到其源码，native表示是本地操作系统的方法
12
我们创建Person类，因为默认继承Object类，所以我们可以直接打印哈希值
13
我们还知道Object类的toString方法，默认会打印物理地址，我们可以看到，其地址是16进制显示的，我们可以重写hashcode方法使某些实例哈希结果相同，但是一般不建议
14
如上，String类是重写了hashcode的，相同内容的字符串其哈希值是一样的，但是字符串不一样也会导致哈希值一样
15
哈希表结构，1.8之前，数组加链表，1.8以后，是当相同哈希值串联的链表长度超过了8位，使用红黑树进行提升查询速度，如图中的“重地”和“通话”，我们知道其哈希值相同，会先后串联起来
16
Set不存储重复元素的原理
set集合会判断equals和hashcode2者是否都相等，相等则相同
17
如上，我们插入了3次abc字符串，其hash值是相同的，因为其equals也相等，所以不多存储，而重地和通话，虽然哈希值相同，但是其equals不满足，此时，就会把“重地”和“通话”形成链表，首地址送给集合，如上上图
Demo体验哈希，通过自建person类，复写哈希和equals，只要name,age相同就不重复存入集合中，
18
其中，equals和hashcode和setter,getter,constructor一样，通过alt+insert添加进来，默认的即是满足我们要求的，之前我们也用过
19
如上，我们定义了4个人，其中p1,p2年龄姓名都一样，我们通过遍历，可以发现我们存的人只有3个
LinkedHashSet类
20
我们知道HashSet还有个子类LinkedHashSet，在哈希表的基础上多了一个维护顺序的链表
21
22
我们先体验下HashSet，如上2图，我们改变了字符串的添加顺序，但是其取出顺序不一样
23
24
改用LinkedHashSet后，可以发现添加和取出顺序一致
函数可变参数
jdk1.5以后出现，参数列表类型确定，个数不确定
格式 修饰符 返回类型 函数名（变量类型...变量名）{}
这里...就代表可变参数，底层是用可变长数组看来接收，传入多少个参数，就数组长度多少
25
如上，我们实现个加法，可以传入任意个参数，这个变量名就作为数组名
网友评论