Java集合框架概述
数组弊端:
- 初始化以后,长度不可变,不便于扩展。
- 数组提供的属性和方法少,添加、删除、插入等操作不便,且效率不高。无法直接获取存储元素个数。
- 数组存储数据的特点单一(有序、可重复)。
Java集合类可用于存储数量不等的多个对象,还可保存具有映射关系的关联数组。
Java集合可分为Collection和Map两种体系:
Collection接口:单列数据,定义了存储一组对象的方法集合。
①List:元素有序,可重复
②Set:元素无序,不可重复
③Collection接口继承树
Map接口:双列数据,保存具有映射关系的“key-value对”的集合。
①Map接口继承树
Collection接口方法
Collection接口
- Collection接口是List、Set和Queue接口的父接口,该接口里定义的方法既可用于操作Set集合,也可用于操作List和Queue集合。
- JDK不提供此接口的任何直接实现,而是提供更具体的子接口(如:Set和List)实现。
- 在Java5之前,Java集合会丢失容器中所有对象的数据类型,把所有对象都当成Object类型处理;从JDK 5.0增加了泛型以后,Java集合可以记住容器中对象的数据类型。
注意:向Collection接口的实现类对象中添加数据obj时,要求obj所在类重写equals()。
接口方法
操作 | 方法序号 |
---|---|
增加 | ①③ |
除删 | ④⑧⑨ |
查找 | ⑥⑦ |
修改 | |
插入 | |
长度 | ② |
遍历 |
add(Object e): 将元素e添加到集合coll中。
size(): 获取添加的元素个数。
addAll(Collection coll1): 将coll1集合中的元素添加到当前的集合中。
clear():清空集合元素。
isEmpty():判断当前集合是否为空。
contains(Object obj):判断当前集合中是否包含obj。
在判断时会调用obj对象所在类的equals()方法。
containsAll(Collection coll1):判断形参coll1中所有元素是否都存在于当前集合中。
remove(Object obj):从当前集合中移除obj元素。
removeAll(Collection coll1):移除当前集合与coll1交集中的元素。
retainAll(Collection coll1): 交集,将当前集合修改为当前集合与coll1的交集。
equals(Object obj): 判断当前集合与形参集合的元素是否都相同。
hashCode():返回当前对象的哈希值。
toArray():集合转换成数组。
拓展: 数组转换成集合: 调用Arrays类的静态方法asList()。
List list = Arrays.asList(new String[]{"AA", "BB", "CC"});
iterator(): 返回Iterator接口的实例,用于遍历集合元素。
- 集合的默认遍历方法(jdk8新特性)
|
Iterator迭代器接口
- Iterator仅用于遍历集合,Iterator本身并不提供承装对象的能力。如果需要创建Iterator对象,则必须有一个被迭代的集合。
- 集合对象每次调用iterator()方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前。
- 使用迭代器遍历集合一般使用的方式以及迭代器执行原理:
remove()方法
①Iterator可以删除集合的元素,区别集合的remove()方法和迭代器的remove()方法。
②注意指针的位置,若调用remove()方法时指针位置为空,则报异常IllegalStateException。
foreach循环(增强for循环):
- Java 5.0 提供了foreach循环迭代访问Collection和数组。
- 无需长度、索引。
- 底层:Iterator。
for(元素类型 局部变量 : 数组/Collection对象){ |
注意:增强for循环是将值赋给局部变量,改变的是局部变量,不影响对象中的元素。
练习:判断输出结果为何?
|
Collection子接口一:List
- 存储有序的、可重复的数据。==> “动态”数组,替换原有的数组
List接口方法:除了从Collection集合继承的方法外,List 集合里添加了一些根据索引来操作集合元素的方法。
操作 | 方法序号 |
---|---|
添加 | ①② |
删除 | ⑥ |
查找 | ③④⑤⑧ |
修改 | ⑦ |
void add(int index,Object ele):在index位置插入ele元素;
boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来;
Object get(int index):获取指定index位置的元素;
int indexOf(Object obj):返回obj在集合中首次出现的位置;
int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置;
Object remove(int index):移除指定index位置的元素,并返回此元素;
Object remove(Object obj):移除指定的元素(若有多个,则只移除首位的元素),并返回被移除的元素;
Object set(int index, Object ele):设置指定index位置的元素为ele;
List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合。
ArrayList
作为List接口的主要实现类;线程不安全的,效率高;底层使用Object[] elementData存储。
源码分析:
//jdk7的情况下: |
小结:jdk7中ArrayList对象的创建类似于单例的饿汉式,而jdk8则类似于懒汉式,延迟了数组的创建,节省内存。
【面试题】
|
LinkedList
对于频繁的插入和删除操作,使用此类效率比ArrayList高;底层使用双向链表存储。
LinkedList list = new LinkedList();//内部声明了Node类型的first和last属性,,默认值为null |
Node除了保存数据,还定义了两个变量:
①prev:记录前一个元素的位置;
②next:记录下一个元素的位置。
新增方法:
- void addFirst(Object obj)
- void addLast(Object obj)
- Object getFirst()
- Object getLast()
- Object removeFirst()
- Object removeLast()
Vector
作为List接口的古老实现类(1.0);线程安全的,效率低;底层使用Object[] elementData存储。
源码分析:
Vector的源码分析:jdk7和jdk8中通过Vector()构造器创建对象时,底层都创建了长度为10的数组。在扩容方面,默认扩容为原来数组长度的2倍。
新增方法:
- void addElement(Object obj)
- void insertElementAt(Object obj,int index)
- void setElementAt(Object obj,int index)
- void removeElement(Object obj)
- void removeAllElements()
面试题:请问ArrayList/LinkedList/Vector的异同?谈谈你的理解。ArrayList底层是什么?扩容机制?Vector和ArrayList的最大区别?
ArrayList和LinkedList的异同
二者都线程不安全,相对线程安全的Vector,执行效率高。
此外,ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。对于随机访问get和set,ArrayList绝对优于LinkedList,因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove,LinkedList比较占优势,因为ArrayList要移动数据。ArrayList和Vector的区别
Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized),属于强同步类。因此开销就比ArrayList要大,访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间,而ArrayList是1.5倍。Vector还有一个子类Stack。
Collection子接口二:Set
- Set接口是Collection的子接口,set接口没有提供额外的方法。都是Collection中声明过的方法。
- 存储无序的、不可重复的数据 ==> 高中数学中的“集合”
- Set判断两个对象是否相同不是使用 == 运算符,而是根据equals()方法
HashSet
作为Set接口的主要实现类;是线程不安全的,可以存储null值。
以HashSet为例说明:Set存储无序的、不可重复的数据:
- 无序性:不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加,二是根据数据的哈希值决定的。
- 不可重复性:保证添加的元素按照equals()判断时,不能返回true。即:相同的元素只能添加一个。
- 要求:向Set中添加元素所在类,其所在类一定要重写hashCode()和equals();
重写的hashCode()和equals()尽可能保持一致性:相等的对象必须具有相等的散列码;
重写两个方法的小技巧:对象中用作equals()方法比较的Field,都应该用来计算hashCode值。
添加元素的过程:以HashSet为例
向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为:索引位置),判断数组此位置上是否已有元素:
- 没有其他元素==>添加成功。==>情况1
- 有其他元素b(或以链表形式存在的多个元素),则比较元素a与b的哈希值:
- 哈希值不同==>添加成功。==>情况2
- 哈希值相同,进而调用元素a所在类的equals()方法:
- 返回false==>添加成功。==>情况3
- 返回true,则添加失败。
对于添加成功的情况2和3而言:元素a与已经存在指定索性位置上的数据以链表的方式存储。
jdk7:元素a放到数组中,指向原来的元素。(头插)
jdk8:原来的元素在数组中指向a元素。(尾插)
总结:七上八下
HashSet底层:数组+链表的结构。
**Eclipse/IDEA工具里hashCode()的重写:**以Eclipse/IDEA为例,在自定义类中可以调用工具自动重写equals和hashCode。
问题:为什么用Eclipse/IDEA复写hashCode方法,有31这个数字?
- 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)
- 31只占用5bits,相乘造成数据溢出的概率较小。
- 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。(提高算法效率)
- 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结果只能被素数本身和被乘数还有1来整除!(减少冲突)
LinkedHashSet
作为HashSet的子类;遍历其内部数据时,可以按照添加顺序遍历。对于频繁的遍历操作,LinkedHashSet效率高于HashSet。
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
TreeSet
以按照添加对象的指定属性进行排序。
- 向TreeSet中添加的数据。要求是相同类的对象。
- 两种排序方式:自然排序(实现Comparable接口)和定制排序(Comparator)。默认情况下,TreeSet采用自然排序。
- 自然排序中,比较两个对象是否相同的标准为:compareTo()返回0,不再是equals()。
- 定制排序中,比较两个对象是否相同的标准为:compare()返回0,不再是equals()。
新增方法:(了解)
- Comparator comparator()
- Object first()
- Object last()
- Object lower(Object e)
- Object higher(Object e)
- SortedSet subSet(fromElement, toElement)
- SortedSet headSet(toElement)
- SortedSet tailSet(fromElement)
TreeSet底层使用红黑树结构存储数据。特点:有序,查询速度比List快。
User类:
package top.triabin._05set; |
自然排序实现:
//按照姓名从大到小排序,年龄从小到大排列 |
|
定制排序实现:
/** |
非常非常经典的面试题:
|
Map接口
概述:
- 双列数据,存储key-value对的数据 ==> 类似于高中的函数
- Map中的key:无序的,不可重复的,使用Set存储所有的key。 ==> key所在的类必须要重写equals()和hashCode()(以、HashMap为例)
- Map中的value:无序的,可重复的,使用Collection存储所有的value。 –> value所在类要重写equals()
- 一个键值对:key-value构成一个Entry对象。
- Map中的Entry:无序的,不可重复的,使用Set存储所有entry。
常用方法:
添加、删除、修改等操作:
- Object put(Object key,Object value):将制定key-value添加到(或修改)当前map对象中。
- void putAll(Map m):将m中所有key-value对存放到当前map中。
- Object remove(Object key):移除指定key的key-value对,并返回value。没有相应的key则返回null
- void clear():清空当前map中的所有数据。与map=null操作不同
元素查询的操作:
- Object get(Object key):获取指定key对应的value。没有相应的key则返回null
- boolean containsKey(Object key):是否包含指定的key。
- boolean containsValue(Object value):是否包含指定的value。
- int size():返回map中key-value对的个数。
- boolean isEmpty(): 判断当前map是否为空。
- boolean equals(Object obj):判断当前map和参数对象是否相等
元视图操作的方法:
- Set keySet():返回所有key构成的Set集合。
- Collections values():返回所有value构成的Collection集合。
- Set entrySet():返回所有key-value构成的Set集合。
总结:常用方法
- 添加:put(Object key,Object value)
- 删除:remove(Object key)
- 修改:put(Object key,Object value)
- 查询:get(Object key)
- 长度:size()
- 遍历:keySet() / values() / entrySet()
HashMap
作为Map的主要实现类;线程不安全,效率高;存储null的key和value。
底层实现原理:(jdk7)
HashMap map = new HashMap();//在实例化以后,底层创建了一个长度为16的一维数组Entry[] table。 |
补充:情况2和情况3:此时key1-value1和原来的数据以链表的方式存储。
在不断的添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容。
默认扩容方式:扩容为原来容量的2倍,并将原有数据复制过来。
jdk8相较于jdk7在底层实现方面的不同:
new HashMap():底层没有创建一个长度为16的数组;
jdk8底层的数组是Node[],而非Entry[];
首次调用put()时,底层创建长度为16的数组;
jdk7底层结构只有:数组+链表。jdk8中底层结构:数组+链表+红黑树。
当某一个索引位置上的元素以链表形式存在的数据个数 > 8 且 当前数组长度 > 64 时,此索引位置上的的所有数据改为用红黑树存储。
几个常量值:
- DEFAULT_INITIAL_CAPACITY:HashMap的默认容量,16
- DEFAULT_LOAD_FACTOR:HashMap的默认加载因子,0.75
- threshold:扩容的临界值等于容量x填充因子:16*0.75 = 12
- TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树:8
- MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量:64
- table:存储元素的数组,总是2的n次幂
- entrySet:存储具体元素的集
- size:HashMap中存储的键值对的数量
- modCount:HashMap扩容和结构改变的次数
- threshold:扩容的临界值 = 容量*填充因子
- loadFactor:填充因子
面试题:谈谈你对HashMap中put/get方法的认识?如果了解再谈谈HashMap的扩容机制?默认大小是多少?什么是负载因子(或填充比)?什么是吞吐临界值(或阈值、threshold)?
面试题:负载因子的值太小,对HashMap有什么影响?
- 负载因子的大小决定了HashMap的数据密度。
- 负载因子越大密度越大,发生碰撞的几率越高,数组中的链表越容易长,造成查询或插入时的比较次数增多,性能会下降。
- 负载因子越小,就越容易触发扩容,数据密度也越小,意味着发生碰撞的几率越小,数组中的链表也就越短,查询和插入时比较的次数也越小,性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能,建议初始化预设大一点的空间。
- 按照其他语言的参考及研究经验,会考虑将负载因子设置为0.7~0.75,此时平均检索长度接近于常数。
LinkedHashMap
作为HashMap的子类
保证在遍历map元素时,可以按照添加的顺序实现遍历。
原理:在原有的HashMap地层结构基础上,添加了一对指针,指向前一个和后一个元素。
对于频繁的遍历操作,此类执行效率高于HashMap。
底层实现原理:(了解)
//源码: |
TreeMap
保证按照添加的key-value对进行排序,实现遍历。此时考虑key的自然和定制排序。底层使用红黑树存储。
向TreeMap中添加key-value,要求key必须是由同一个类创建的对象,因为要按照key进行自然排序、定制排序。
排序类似于之前的TreeSet。
TreeMap判断两个key相等的标准:两个key通过compareTo()方法或者compare()方法返回0。
Hashtable
- 作为Map古老的实现类(jdk1.0);线程安全的,效率低;不能存储null的key和value。
- Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询速度快,很多情况下可以互用。
- 与HashMap不同,Hashtable 不允许使用 null 作为 key 和 value。
- 与HashMap一样,Hashtable 也不能保证其中 Key-Value 对的顺序。
- Hashtable判断两个key相等、两个value相等的标准,与HashMap一致。
Properties
- Properties 类是 Hashtable 的子类,常用来处理配置文件。key和value都是Sting类型。
- 存取数据时,建议使用setProperty(String key,String value)方法和getProperty(String key)方法。
Collections工具类
- Collections 是一个操作 Set、List 和 Map 等集合的工具类。
- Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。
常用方法:
排序操作:(均为非static方法)
- reverse(List):反转 List 中元素的顺序
- shuffle(List):对 List 集合元素进行随机排序
- sort(List):根据元素的自然顺序对指定 List 集合元素按升序排序
- sort(List,Comparator):根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
- swap(List,int, int):将指定 list 集合中的 i 处元素和 j 处元素进行交换
查找、替换:
- Object max(Collection):根据元素的自然顺序,返回给定集合中的最大元素
- Object max(Collection,Comparator):根据 Comparator 指定的顺序,返回给定集合中的最大元素
- Object min(Collection)
- Object min(Collection,Comparator)
- int frequency(Collection,Object):返回指定集合中指定元素的出现次数
- void copy(List dest,List src):将src中的内容复制到dest中
- boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List 对象的所有旧值
同步控制:
Collections 类中提供了多个 synchronizedXxx() 方法,该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题。
补充:Enumeration
Enumeration 接口是 Iterator 迭代器的 “古老版本”。
①hasMoreElements()
②nextElement()
Enumeration stringEnum = new StringTokenizer("a-b*c-d-e-g", "-"); |