Java集合

一、集合概述

1、集合、数组都是对多个数据进行存储操作的结构简称Java容器
说明此时主要指内存层面的存储不涉及持久化的存储.txt.jpg数据库中等
2、数组在存储多个数据方面的特点
①一旦初始化后其长度就确定了
②数组一旦定义好其元素的类型也就定义了只能操作指定类型的数据如String[ ] arr;Object[ ] arr1

3、数组在存储多个数据方面的缺点
①一旦初始化后其长度就不可修改
②数组中提供的方法非常有限对于添加、删除、插入等操作非常不便同时效率不高
③获取数组中实际元素的个数的需求数组中没有现成的方法或属性可用
④数组存储数据的特点有序体现在添加数据中间不能有空等、可重复。对于无序、不可重复的要求不满足。

二、集合框架

Collection接口单列集合用于存储一个个的对象
①List接口有序、可重复的数据“动态数组”
主要实现类ArrayList、LinkedList、Vector
②set接口无序、不可重复的数据
主要实现类HashSet、LinkedHashSet、TreeSet
Map接口双列集合用于存储一对一对key-value的数据
主要实现类HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

三、Collection接口中的方法的使用

1、add(Object e)将元素e添加到集合中
2、size获取添加元素的个数

3、addAll(Collection c)将Collection c中的元素添加到当前集合中

4、isEmpty()判断当前集合是否为空
5、clear清空集合元素

6、containsObject obj判断当前集合中是否包含obj
在判断时会调用obj所在类的equals方法
向Collection接口的实现类对象中添加对象obj时要求obj所在类要重写equals方法一般是比较内容是否一致而不是地址值

7、containsAll(Collection coll1)判断形参coll1中所有元素是否都存在于当前集合中

8、removeObject obj从当前集合中移除obj

9、removeAllCollection coll1差集从当前集合移除coll1中所有元素这时返回的元素是赋给了coll因为是coll调用的此方法。相当于对coll进行了修改

10、retainAllCollection coll1获取当前集合与coll1的交集并返回给当前集合

11、equalsObject obj如果前面是集合调用此方法想要返回true形参肯定也得是一个集合

12、hashcode返回当前对象的哈希值

13、toArray集合——>数组
【补充】数组——>集合Arrays.asList
调用Arrays的静态方法asList

【注意】创建int类型数组时注意写法不然可能会把整个内容看成是集合中的一个元素

四、遍历集合

Iterator迭代器

14、iterator返回迭代器Iterator接口的实例用于遍历集合元素
①内部主要方法hasNext——是否还有下一个元素、Next——输出下一个元素第一个next调用输出的就是集合中的第一个元素一开始Iterator的位置相当于在集合外

图示

【注意】Iterator并不是一个容器只是一个迭代器
错误方式一会跳着输出并报异常

错误方式二会一直输出123死循环

原因每次调用Iterator都会产生一个新的迭代器默认初始位置都是集合第一个元素前面

②remove内部定义remove方法可以在遍历时删除集合中的元素不同于集合调用remove
如果在调用next之前就调remove或在调用remove后在next之前又调remove会报错

再次遍历时需要重新创建一个迭代器因为经过上一个while迭代器已经在集合末尾处此时如果还用旧的迭代器不能达到遍历删除元素后的集合的目的

foreach循环

jdk5.0新增了foreach循环遍历集合和数组
1、集合
格式 for(集合变量类型 局部变量集合对象)

2、数组
格式 for(数组变量类型 局部变量数组对象)

3、练习题

普通方式输出内容为GG、GG、GG因为直接对数组元素进行修改
增强方式输出MM、MM、MM因为增强方式是定义了一个变量s然后将数组元素赋值给s之后对s进行修改

五、Collection接口之一List接口

ArrayList作为List接口的主要实现类线程不安全的效率高底层使用Object[ ] elementData存储
LinkedList对于频繁插入、删除操作效率比ArrayList高底层使用双向链表存储
Vector作为List接口的主要古老类线程安全的效率低底层使用Object[ ] elementData存储

面试题

ArrayList、LinkedList、Vector三者的异同
同三者都实现了List接口存储数据特点相同有序、可重复
不同见上

ArrayList源码分析

JDK7

ArrayList list=new ArrayList( );//底层创建了一个长度是10的Object[ ]数组elementData
……
list.add123//如果此次添加的数据导致elementData容量不够则扩容默认情况下扩容为原来的1.5倍同时将原数组内容复制到新数组中

结论建议使用带参构造器创建ArrayList list=new ArrayList(int capacity);

JDK8

ArrayList list=new ArrayList( );//底层创建Object[ ]数组elementData初始化为{ }并没有创建长度是10的数组
list.add123//第一次调用add时底层才创建了长度为10的数组并将123添加到数组第一个位置
后续的添加和扩容操作和jdk7无异

小结

JDK7中ArrayList的对象的创建类似于单例模式的饿汉式而JDK8中的ArrayList对象创建过程类似于懒汉式。JDK8中延迟了数组的创建时间节省内存

LinkedList源码分析

LinkedList list=new LinkedList();//内部声明了Node类型的first和last属性默认值为null
list.add123//将123封装到Node中创建了Node对象
其中Node定义为(体现了双向)

Vector源码分析

JDK7和JDK8中通过Vector创建对象时底层都创建了长度为10的数组。在扩容方面默认扩容为原来的二倍

List中常用方法

1、void add(int index,Object ele)在index位置插入元素ele
2、boolean(int index,Collection ele)从index位置开始将ele中的所有元素加入集合
3、Object get(int index)获取指定index位置的元素
4、int indexOf(Object obj)返回obj在集合中首次出现的位置
5、int lastIndexOf(Object obj)返回obj在集合中末次出现的位置
6、Object remove(int index)移除指定index位置的元素是Collection中remove方法的重载因为没有覆盖这个方法
7、Object set(int index,Object ele)设置指定位置的内容为ele
8、List subList(int fromdex,int toindex)返回从fromindex到toindex的子集合左闭右开本身的List并没有改变

总结List中常用方法

增add(Object obj)
删remove(int index)、remove(Object obj)
改set(int index,Object ele)
查get(int index)
插add(int index,Object ele)
长度size( )
遍历①Iterator ②增强for循环

练习

输出内容为1、2
因为前面添加时括号里面的内容是包装类。后面remove中的是索引因为如果是对象即包装类的话还需要涉及到自动装箱等操作而现成的就有参数是int的方法

六、Collection接口之二Set接口

Set接口存储无序、不重复的数据
HashSet作为Set的主要实现类线程不安全的可以存储null值
LinkedHashSet作为HashSet的子类遍历其内部数据时可按照添加顺序进行遍历
TreeSet可以按照添加对象的属性进行排序
【说明】Set中没有定义新的方法用的都是Collection的

Set的无序性和不可重复性的理解

1、无序性不等于随机性。以HashSet为例存储的数据在底层数组中并非按照数组索引的位置进行添加。而是根据数据的哈希值决定
2、不可重复性保证添加的元素按照equals判断时不能返回true即相同的原只能添加一个

添加元素以HashSet为例

向HashSet中添加元素a首先调用a的hashCode方法计算a的哈希值此哈希值计算出该元素在底层数组中的存放位置即为索引位置判断数组上的此位置是否有元素
如果没有元素则元素a添加成功。————情况1
如果此位置上有其他元素b以链表形式存在多个元素则比较a与b的哈希值
如果哈希值不相同则元素a添加成功。————情况2
如果哈希值相同则需要调用a元素的equals方法
若equals方法返回true则添加失败。
若equals方法返回false则添加成功。————情况3
对于情况2和情况3来说元素a与已经存在于指定索引位置上的元素以链表形式存储。
jdk7中元素a放到数组中指向原来的元素
jdk8中原来的元素放在数组中指向元素a
总结七上八下

HashSet底层数组+链表

要求
向HashSet中添加元素要求所在元素的类必须重写两个方法hashCode、equals
重写的两个方法尽量保持一致性即相等的对象要有一致的散列码
其实就是两个方法最好不要自己写直接alt+shift+s自动生成

LinkedHashSet的使用

LinkedHashSet作为HashSet的子类再添加数据的同时每个数据还维护了两个引用记录此数据的前一个数据和后一个数据。
优点对于频繁的遍历操作LinkedHashSet比HashSet效率高

TreeSet的使用

1、向TreeSet添加的数据要求是相同类的对象因为TreeSet的主要目的是比较指定属性的大小如果不是相同类就没有相同属性
2、两种排序方式Comparable接口、Comparator接口
3、在Comparable接口中比较两个元素是否相同的标准是compareTo方法的返回值是否为0不再是equals方法
4、在Comparator接口中比较两个元素是否相同的标准是compare方法的返回值是否为0不再是equals方法

每日一考

1、equals方法
Listequalsff
SetHashSet、LinkedHashSethashCode、equals
TreeSet:compareTo、compare

练习

hashset已经重写了hashcode、equals

答案①2个分别是aa、bb②2个是bb、cc③3个cc、bb、cc④4个aa、cc、bb、cc
①不用解释
②在将aa改成cc后remove时是对1001 cc进行移除因为此时p1的内容已经改变但是在移除时会先通过hashcode查找元素位置也就是说再插入1001 aa后元素占的位置是1001 aa的后来元素被改成1001 cc但还是在1001 aa的位置上。在remove时找的是p1代表的对象的哈希值即1001 cc的位置此时这个位置和1001 aa不同相当于要移除的位置上并没有元素所以输出结果是bb cc都存在
③新加入的元素是 1001 cc根据②可知1001 cc的哈希值对应的存储位置并没有元素所以插入成功输出结果是三个
④1001 aa计算哈希之后发现位置上已经有元素了然后调用equals方法进行判断发现1001 aa和位置上的元素不是一个插入成功所以输出结果是4个

七、集合中的Map接口

双列数据存储key-value值
HashMap主要实现类线程不安全效率高存储null的value和key
LinkedHashMap保证在遍历Map元素时可以按照添加的元素顺序遍历。原因在底层原有的HashMap基础上添加了一对指针指向前一个和后一个元素。对于频繁的遍历操作效率高于HashMap
TreeMap保证按照添加的key-value值进行排序实现排序遍历。此时考虑key的自然排序或定制排序底层使用红黑树
Hashtable古老实现类线程安全效率低不能存储null的value和key
Properties常用来处理配置文件key和value都是String类型

HashMap底层
数组+链表jdk7及之前
数组+链表+红黑树jdk8

Map结构的理解

Map中的key无序、不可重复。用set存储——以HashMap为例要求key所在的类重写equals和Hashcode方法
Map中的value无序、可重复。用Collection存储value——所在类重写equals
一个键值对key-value构成一个键值对象
Map中的Entry无序、不可重复。用set存储所有Entry

HashMap的底层实现原理

jdk7
HashMap map=new HashMap();//在实例化后底层创建了一个长度为16的数组Entry [ ] table
……
map.put(key1, value1)
首先调用key1所在类的hashCode方法计算key1的哈希值通过某种算法得到key1在底层数组Entry中的存储位置。
如果此位置上的数据为空则key1-value1即Entry1添加成功————情况1
如果此位置上的数据不为空以为这次位置上存在一个或多个数据若是多个数据则以链表形式存储则比较key1和一个或多个数据的哈希值
若key1与已经存在的数据的哈希值都不相同则key1-value1即Entry1添加成功。————情况2
若key1与已经存在的某个数据的哈希值key2-value2相同继续比较调用key1所在类的equals(key2)
若equals返回false则key1-value1即Entry1添加成功。————情况3
若equals返回true使用value1替换value2

对于情况2、情况3此时的key1-value1与原来数据以链表的方式存储

在不断添加数据的过程中涉及到扩容问题当超出临界值且要存放数据所在的位置非空时默认扩容为原来的2倍并将原数据复制过来

jdk8
①new HashMap();没有在底层创建一个长度为16的数组
②jdk8的底层数组Node[ ] 而非Entry[ ]
③首次调用put方法时底层创建一个长度为16的数组
④jdk7中的底层结构链表+数组jdk8中的底层结构数组+链表+红黑树
当数组的为一个索引位置上的元素一链表形式存在的数据个数 > 8且当前数组长度 > 64时此时此位置上的所有数据改用红黑树存储

DEFAULT_INITIAL_CAPACITYHashMap默认容量16
DEFAULT_LOAD_FACTORHashMap默认加载因子0.75
threshold扩容的临界值=容量加载因子=160.75=12
TREEIFY_THRESHOLDBucket中链表长度大于该默认值转换为红黑树8
MIN_TREEIFY_CAPACITYNode被树化时最小的hash表容量数组的长度为该值时变为红黑树64

HashMap源码分析

HashMap中常用变量

LinkedHashMap源码分析

Map中常用方法

添加、删除、修改操作
1、Object putObject keyObject value将指定key-value值添加或修改到当前map对象中

2、void putAllMap m将m中所有的key-value都放到当前map中
3、Object removeObject value移除指定key的key-value对并返回value没找到时返回null
4、void clear清空当前map中所有数据

元素查询的操作
5、Object getObject key获取指定key对应的value
6、boolean containsKeyObject key是否包含指定的key
7、boolean containsValueObject value是否包含指定的value
8、int size获取当前map中key-value的个数
9、boolean isEmpty判断当前map是否为空
10、boolean equalsObject obj判断当前map和参数obj是否相等前提是obj是map

元视图的操作遍历
因为Map中并没有迭代器iterator所以不能直接调hasNext、next方法
11、Set keySet返回所有key构成的set集合
12、Collection values返回所有value构成的Coolection集合
13、Set entrySet返回所有key-value对构成的集合

总结

增Object putObject keyObject value
删Object removeObject value
改Object putObject keyObject value
查Object getObject key
长度int size
遍历keySet、values()、entrySet

向TreeMap中添加操作

向TreeMap中添加key-value时要求key必须是同一个类创建的对象
因为要按照key进行排序自然排序、定制排序

Properties

是处理属性文件的属性文件中的key和value都是String类型所以Properties中的key和value也都是String类型

Collections工具类

常用方法

Collections是一个操作List、Set、Map的工具类
1、reverseList list反转list中元素的顺序只有list是有序的
2、shuffleList list对list集合中的元素进行随机排序
3、sortList list使用自然排序comparable对list集合中的元素进行升序排列
4、sortList listComparator com根据Comparator指定的顺序对list中元素进行排序
5、swapListintint将list中的 i、和 j 位置上的元素交换

6、Object max(Collection)根据元素的自然顺序返回集合中的最大元素
7、Object maxCollectionComparator根据Comparator中指定的顺序返回集合中元素的最大值
8、Object min(Collection)根据元素的自然顺序返回集合中的最小元素
9、Object minCollectionComparator根据Comparator中指定的顺序返回集合中元素的最小值
10、int frequencyCollectionObject返回集合中指定元素出现的次数
11、void copyList destList src将src中内容复制到dest中

在复制时要求dest的大小要大于等于src的大小如果只是新建一个listdest的size是0不满足要求会报异常。正确的写法是上面的

12、boolean replaceAllList listObject oldObject new使用新值替换list对象中所有的旧值

转换为线程安全

collections提供了synchronizedXXX方法可以将指定集合包装成线程同步集合从而解决多线程的线程安全问题

每日一考