前言
本章主要是讲数据结构与集合,这章内容涉及到非常基础的知识,内容相对较多,首先从数组讲起,引申到集合框架,之后再到集合源码,最后介绍了高并发集合框架
集合
集合在代码中是collection,对应英文为set,具有确定性,无序性,互异性的特点。java中的集合元素可以是有序的,也可以是重复的,与数学中的要求不同,这章的内容都是指collection,用来保存各种对象的集合
数据结构
- 定义:数据结构是一种逻辑上的数据组织和处理方式,这里的逻辑意义很关键,以二叉树为例,它不是像一颗树形进行存储,物理保存时是一个格子存一个节点;数据组织方式就是那些树,图,队列,哈希之类,这些都是组织方式;处理方式指的是以特定的算法进行数据的增加,删除,修改,查找和遍历,这些不同的处理方式间会有性能差异
- 数据结构的分类:数据结构是算法的基础,如果有缺陷就会造成系统风险高,可拓展性差,根据直接前后继的角度可以把数据结构分为以下四类
1.线性结构:0到1个直接前驱和后继,非空时有唯一的首尾元素,包括顺序表,链表,栈,队列等 2.树结构:0到1个直接前驱和0到n个直接后继(n>=2) 3.图结构:0到n个直接前驱和直接后继 4.哈希结构:没有直接前驱和后继,通过哈希函数索引,查找效率很高 - 衡量数据处理性能:时间复杂度和空间复杂度,量级描述有
  实际场景中数据规模大了以后,算法性能差异会变得很明显
集合框架图
java集合是一种用于存储对象的容器,提供增删改查和遍历方法,下图为java中实际的集合框架图  蓝色是抽象类,红色是接口,绿色是并发包里的类,灰色是一些线程安全的类,基本已经弃用 其中最主要的就是四个:List,Set,Queue,Map
list集合
List是线性数据结构,存在明确的前驱后继元素,明确的首尾元素,遍历结果稳定,常用集合类有arraylist和linkedlist
- arraylist容量可改变,线程不安全,支持对元素快速随机访问,但插入删除时很慢,因为需要移动元素
- linkedlist是双向链表,相比arraylist,它插入删除速度更快,但随机访问很慢,它继承了AbstractList抽象类和Deque接口,Deque接口具有队列和栈的性质
LinkedList有三个重要成员:size,first,last;size是节点个数,first指向头节点,last指向最后一个节点,LinkedList的优点在于把零散内存单元关联起来,提高了内存利用率
Queue集合
Queue即队列,是一种先进先出的线性表,两端分别只能获取和插入,没有元素称为空队列 BlockingQueue阻塞队列可在高并发的场景下作为数据缓冲区使用
Map集合
Map集合是以Key-value键值对存储元素的哈希结构,key不可重复,值可重复; KeySet()查看所有key,values()查看所有value,entryset()查看所有键值对,hashtable已经被淘汰,HashMap线程不安全,ConcurrentHashMap线程安全,JDK8中对锁进行了优化,TreeMap是Key有序的Map集合,多线程并发中推荐使用ConcurrentHashMap而非HashMap
Set集合
元素不重复,常用HashSet,TreeSet和LinkedHashSet HashSet是HashMap把Value固定住,用Key保证集合元素唯一性,不保证有序性 TreeSet是TreeMap实现,底层为树结构,插入时会比较保证有序性 LinkedHashSet继承HashSet,有HashSet的优点,内部用链表保证元素插入顺序
集合初始化
集合初始化需要分配容量,设置参数,比如ArrayList和HashMap,分别是顺序表和哈希结构,从源码可以看到他们的初始化逻辑 ArrayList     这段代码可以看出:
- 扩容时,可能超出int的最大值,超出就返回原来的长度
扩容时是利用位移运算,二进制下右移一位,再加到旧的长度上 在JDK7之前,扩容方式是旧容量x3÷2+1,也就是1.5倍加1 初始化时默认为10,那么第一次add后每次扩容都使用array.copyof,会创建一个新的数组再复制,如果是1000个元素,就会扩容13次,很影响性能,但如果初始化1000长度,就不需扩容,对于更大的值,甚至会有oom风险 - HashMap放1000个元素,需要扩容7次,扩容需要重建hash表,很影响性能,
HashMap有两个参数,Capacity和LoadFactor;Capacity决定存储容量,默认16,LoadFactor决定填充比例,默认0.75,两者之积是threshold,就是能放入的元素个数 HashMap不会在new时分配,而是在第一次put时完成创建 HashMap的容量大小为2的n次方,就是为了在运算时能充分散列,这块详细在之前的面试题里有讲 初始化ArrayList是10,HashMap是16,默认值最好是预估一个范围,避免扩容造成的损耗
数组与集合
数组是一种顺序表,下标从0开始,这样设计是为了方便计算偏移量,否则就要-1,提倡类型紧挨着中括号,比如int[]来定义数组,就相当于定义数组对象 可以用两种方法定义  args3是静态初始化,args4是动态初始化,动态初始化new后面要给初始容量,动态数组有Vector和 Arraylist操作,分别是线程安全但性能差,线程不安全但使用频繁 数组遍历优先推荐使用foreach方法,for(元素:数组名),可以不使用下标 需要使用下标可以用for循环,数组用length属性获取长度 也可以用jdk8的函数式接口遍历 
- 数组与集合的互相转换:Arrays.asList ()可以把数组转换为集合,但注意不能使用修改集合的方法,例如add/remove/clear,否则报Uns upportedOperationException异常,因为aslit方法是一种适配器模式,后台数据仍是原有数组,set方法可以修改,但其他就会抛出异常

如图,这是arraylist的内部类,实际返回的是这个类,它只实现了部分方法,这个异常由其父类抛出
 实际业务中,为避免数组转集合时添加元素引发异常,可以用java.util.arrayList直接创建一个新集合 ,参数就是aslist方法返回的不可变集合 
- 集合转数组,相对更加可控,通常用于适配别人的数组接口,或者进行局部方法计算
  如图,不要用toarray()无参方法转换集合,会导致泛型丢失 也要注意数组容量是否分配足够,书中实验了不同容量对性能影响,结果如下  可见,数组容量正好时,运行最快,使用toArray()时,注意两点 1,传入类型完全一致的数组 2.它的容量应该为list.size()
集合和泛型
泛型用在集合上,有很强效果,但也要注意类型转换异常  这种放入不同类型元素,转换就会出现类型转换异常  赋给object是可以的,也可以继续添加不同类型的元素   但赋给integer后,再赋值不同类型就会不允许  这里问号在正则表达式里可以匹配任何字符,这个list也就可以接受任何类型引用赋值,可以remove和clear,但不可以添加元素,一般用作为参数接收外部集合或者返回未知类型的集合
- List只能放置一种类型,不能随意转换,如果需要放置多种受泛型约束的类型,则可以用<? extends T>与<? super T>,前者是get first,适合消费为主的集合,后者是put first,适合生产为主的集合
- <? extends T>可以赋值给任何T 及T 子类的集合,上界为T 取出来的类型带有泛型限制, 向上强制转型为T。null 可以表示任何类型,所以除null 外,任何元素都不得添加进<? extends T> 集合内。
- <? super P 可以赋值给任何T 及T 的父类集合,下界为T。在生活中,投票选举类似于<? super T> 的操作。选举代表时,你只能往里投选票,取数据时,根本不知道谁的票,相当于泛型丢失;比如一些评价问卷,提交后不能再访问链接修改评价
- 总结:extends put受限,super get 受限,如果经常往出取的话,使用extends,经常放的话,使用super
元素的比较
- comparable和comparator
java元素的排序经常用到比较,比较有两个常用接口:Comparable和Comparator,分别用compare to和compare方法实现比较 自然排序,也就是123,abc这种,Integer和String中实现的就是Comparable自然排序,有时需要自己定义排序规则,就可这样做   实现Comparable,可以加上泛型限定,这样就可以在编译期间检查传入参数是否是SearchResult对象,免去类型检查和强转,如果是封包类或者是开闭原则,就可以利用外部比较器,Comparator,代码如下  JDK中Arrays.sort的比较器参数排序就是Comparator实现的   这里的<? super T>是泛型限制为T及其父类,直到Object
两个比较器返回值都是小于-1,等于0,大于1;在集合中比较器排序,直接使用正负返回比较结果 
- 上面的TimSort方法是归并排序加插入排序,避免了两者缺点,减少了归并次数,引入了二分排序概念,加快了效率,对于部分有序的数组,时间复杂度可达O(n),随机排序数组则是nlogn,它主要有两个优化
1.归并排序的分段不再从单个元素开始,而是每次先查找最大的有序数组片段run,然后利用二分排序,将该run与其他有序的run进行归并 2.引入二分排序,使得插入排序中每次不再从后向前比较,时间复杂度由n降低到nlogn
hashCode和equals
这两个方法用来判断两个对象是否相同,通常协同工作,首先Object.hashcode生成哈希值,相同则进一步比较equals,不同则直接返回不同 如下是object类对这两个方法的要求  
如上是HashMap的get方法代码判断,先比较hash值,后执行阴影部分,equals一般不要求hashcode相同,但hashcode散列充分,降低冲突,有利于提高执行效率  如上是没有重写hashcode的案例,之后放到hashset里  本该结果是,但执行结果是3,说明不重写hashcode,重写了equals毫无意义,如果想要存储不重复元素,重写hashcode版本如下 
这个name是String类型,自带hashcode重写,直接调用即可
- equals的判定逻辑与类的具体情况有关,
  上面代码的var就是动态类型,jdk10引入的语法糖,它会检测右边类型,并应用于左侧 第2处可能抛出空指针npe异常,推荐使用jdk7自带equals方法,代码如下 
 上面这段代码可以看出它是类型可变化的,也有类型限定格式
fail-fast机制
-
fail-fast机制是一种错误检测机制,主要用于遍历集合元素过程中 -
书中举了个例子,班长点全班同学的名,这里是遍历的意思,然后有人进进出出,就老是需要重新点名,这就是fail-fast机制 多线程时,维护一个expectedModCount,记录已经修改的次数,进入遍历前把实时修改次数modCount付给eMC,如果两个值不同就报异常 -
java.util包下都是fail-fast,concurrent下都是fail-safe,failsafe就是相当于班长直接拍照,然后用照片点名,不管进出 -
比如arraylist.sublist(),获取子列表时,主列表的元素变化会引起子列表的遍历和元素增删,进而出现fail-fast异常  如上代码,通常比较常见的是修改子列表会影响父列表,但比较少见的是父列表改动会导致子列表操作异常 subList返回Sublist类的对象,它是ArrayList的内部类,没有实现序列化接口,无法网络传输 -
在foreach循环中测试fail-fast机制,如下 -
这段代码运行没有报异常,这是一个特例,因为游标遍历到size的时候,退出了遍历,执行remove后,size=size-1=2,这时cursor也等于2,执行hasnext时值为false,也就不会执行next()的checkForComodification方法,这个方法就是用来判断expectedMod和modcount的,不同会抛异常,都没有执行,也就不报异常 -
 -
为了避免删除元素引起fail-fast,可以用Iteator进行遍历时删除,多线程并发时,还需要加锁,如下 -
- 也可以使用并发容器CopyOnWriteArrayList代替ArrayList,内部对迭代器进行了加锁操作 它的原理是读写分离,在写操作时分出一个新集合,在里面操作添加删除,之后把原集合引用指向新集合,用COW的时候要注意1.设置合理初始值,扩容代价较大2.添加删除可以攒一下,积累一些再操作,避免频繁复制整个几个,导致内存占用,进而频繁GC影响服务器性能 如上代码,20万次循环数据插入花费了97.8秒,ArrayList只需39毫秒,这样就得不偿失了,所以COW只适合于读多写少的场景 -
COW是fail-safe的,并发包中的集合都是这种机制实现的,也就是在安全的副本中遍历,集合修改与副本遍历无关,缺点就是读取不到最新数据,这反映了一致性和可用性的矛盾
Map集合
Map是与Collection平级的一个借口,它也与Collection有关联:部分方法比如values()会返回Collection视图,一个vaule的列表。Map集合的存储单位是KV键值对,就是用哈希算法做一组比较均匀的Key,然后把Vaule挂在上面 特点有: 取代了Dictionary类,性能更好 Key不重复,Vaule可重复 Vaule可以试List,Map,Set类对象 KV是否允许为空,以实现类约束为准
- Map接口除了crud,还有KeySet,values,EntrySet方法
在这里插入图片描述  这些返回的视图支持删除,但修改添加元素会报异常,因为AbstractCollection没有add操作,但有remove,clear等操作 这些集合类见证了java进化的过程,线程不安全到线程安全 使用时,直接用ConcurrentHashMap代替HashMap大多数时间可行,性能差别不大,线程安全,但是尽量要避免设置KV为空值或者做好空值判断,避免NPE
红黑树
首先介绍树,树是一种有限节点(结点)组成的层次集合,数据存在节点中,顶层的唯一节点称为根节点,底层没有分支的称为叶子节点,。从某节点出发,到叶子节点为止,最长简单路径上的条数称为该节点的高度,从根节点出发,到某节点边的条数,称为该节点的深度  这棵树,根节点高度为5,深度为0,节点2的深度是1.高度是4 树结构有五个特点 ( I )一个节点,即使只有根节点,也可以是一棵树。 ( 2 )其中任何一个节点与下方所有节点构成的树称为子树。 ( 3 )根节点没有父节点,而子节点没有父节点。 ( 4 )除根币点外任何节点有且仅有个1父节点。 ( 5 )任何节点可以有0 ~ n 个子节点(0-n叉树)。 在二叉树世界中,最重要的是平衡二叉树,二叉查找树,红黑树
平衡二叉树
如果把一棵树的树枝砍到只剩一条路径,那么它就变成一个类似链表,约束一棵树具有层次结构,就是平衡二叉树 平衡二叉树的性质如下 ( 1 )树的左右高度差不能超过1。 ( 2 )任何往下递归的左子树与右子树,必须符合第一条性质。 ( 3 )没有任何节点的空树或只有根节点的树也是平衡二叉树。 
二叉查找树
- 二叉查找树又称二叉搜索树,BST(BinarySearchTree),或者Sort,二叉排序树,节点的左子树比它小,右子树比它大。
从根节点开始,大于往右,小于往左,直到叶子节点就是没找到。 遍历所有节点的方法有三种:前序遍历,中序遍历,后序遍历 这些遍历规律有:1.任何遍历,左节点一定先于右节点2.前中后序,指的是根节点在遍历序列中的位置 前序就是根左右,中序就是左根右,后序就是左右根,下面这张图非常直观  下面是一个普通树转换为二叉查找树的过程,它的子树也是查找树  二叉查找树的元素有增删时可能会失衡,比如用AVL树,红黑树,SRB,树堆就是用来解决这个问题的
AVL树
avl树是一种平衡二叉树算法,可以让二叉树的使用效率最大化,增删元素后,就会通过旋转重新达到平衡。 下图展示了右旋和左旋的过程,一般是左长右短右旋,反之左旋,有一些右边的左子树失衡,需要lr或者rl旋转,比较复杂 

红黑树
72年发明了对称二叉B树,后来改名为红黑树,主要特征是每个节点有一个颜色属性,红或者黑色 红黑树也是插入删除后进行旋转保持平衡,但它的平衡不是左右高度差不大于1,而是从根节点到叶子节点的最长路径不超过最短路径的二倍 它有五个约束条件 1、节点都是红或者黑色 2、根节点必须是黑色 3、所有NIL(叶子节点下挂的两个虚节点)节点都是黑色 4、一条路径不能有两个红节点相连 5、任何递归子树中,根节点到叶子节点的黑节点数目相等 总结:有红必有黑,红红不相连,这些条件的意义在于可以控制最坏时间复杂度为logn,红黑树任何旋转均可在三次内
红黑树与AVL树相比
红黑树的黑深度满足Black Depth小于等于 height / 2,也就是含有n个节点的红黑树,根节点高度一定小于2log2( n + l ) 常规BST的操作,时间复杂度为h,取决于树高度 红黑树平衡性不如AVL树,它维持的是大致的平衡,而失衡时恢复也比avl更简单,最差时间复杂度更低 结论:频繁插入删除时,红黑树更好;低频修改,大量查询时,AVL树更好 如下图是按顺序插入36.34.37.33.35.32  可以看到红黑树不是绝对平衡的
TreeMap
TreeMap用Key的排序重新组织了Map的结构,相比ConcurrentHashMap和HashMap,插入删除效率降低了,但在要求Key排序的场景下,TreeMap更加高效,它与另外两个都继承与AbstractMap抽象类  TreeMap有继承这两个接口:SortedMap和NavigableMap,前者Key是有序不可重复的,插入Key时需要比较,所以key不可为空,value可空 NavigableMap接口继承了继承了SortedMap,根据搜索条件提供适合的KV元素,同时TreeMap可以不重写Hashcode和equals来去重Key  
上面的代码hashmap下size是1,因为两者使用的去重办法不同,如果要用TreeMap要对Key排序,调用方法如下  Comparator为空则调用compareto方法,不为空调用compare方法 都不满足就抛出异常: TreeMap的crud操作的最好最坏时间复杂度均为(logn),特点是key有序   TreeMap通过put和deleteEntry方法实现红黑树的增删节点操作,删除类似插入,只讲插入操作 需要调整的新节点一定是红色的 插入的新节点是黑色的,无需调整 插入新节点是红色的,由于红黑树不能红红相邻,就要重着色,或者左右旋转  根节点直接退出,设置为黑色即可,不是根节点且父节点是红色,则一直调整直到退出循环 TreeMap的插入操作是正常比较,小于向左,按照二叉查找树规则,无需关心颜色平衡,后续会调整   
插入时要之前为非空树并且新节点的Key和任何节点都不同,才能运行到FixAfterInsertion进行着色并且旋转
后记
这篇字数已经一万三左右,后续写在第二篇
|