Java集合:Collection、List、Set、Map、泛型
0.集合的学习思路
层面1:应用层面 √
- 可以掌握重点的集合类的使用步骤
层面2:理解层面【面试前掌握】
- 理解ArrayList的源码
- 理解HashMap的源码
掌握:
- Collection和Map的对比
- List和Set的对比
- ArrayList和Vector的对比
- ArrayList和LinkedList的对比
- HashMap和Hashtable的对比
- Collections和Collection的对比
1.理解
集合:就是一种容器,都是用于保存一组元素
2.集合和数组的对比:
数组的不足:
- 数组的长度必须提前指定,而且一旦指定不能更改
- 数组只能保存相同类型的元素
集合:
- 集合在使用时,长度不用指定,而且可以实现自动扩容或截断
- 集合没有指定泛型之前,默认保存的是任意类型的元素(Object类型)
指定泛型之后,可以保存对应类型 的元素
示例代码:
// 使用数组-------------------- Animal[] animals = new Animal[3]; animals[0] = new Animal(); animals[1] = new Animal(); animals[2] = new Animal(); Animal[] newAni = new Animal[animals.length+1]; //复制数组 //添加新元素 animals=newAni; // 使用集合-------------------- List list= new ArrayList(); list.add(new Animal());
①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小(HashMap 中的tableSizeFor()
方法保证,下面给出了源代码)。
总结:
- 数组:比较适合保存基本类型的元素
- 集合:比较适合保存引用类型的元素(对象)
1.特点
里面没有提供直接的实现类,而是提供了子接口,子接口中有具体的实现类
该接口中提供了一系列常见的集合操作的方法:增加、删除、查找
2.常见方法 ★
* add/addAll
* remove/removeAll
* contains/containsAll
* clear
* size
* isEmpty
/** * 此类用于演示Collection接口的常见方法 * @author liyuting * add/addAll * remove/removeAll * contains/containsAll * clear * size * isEmpty * * */ public class TestCollection1 { public static void main(String[] args) { //1.创建Collection接口对象 Collection col = new ArrayList(); //2.调用常见方法 //方法1:add col.add("赵四"); col.add(true); col.add(null); col.add('男'); col.add(180.5); System.out.println(col); //方法2:addAll Collection c = new ArrayList(); c.add("蓝盈莹"); c.add("周一围"); col.addAll(c); System.out.println(col); //方法3:remove col.remove("蓝盈莹2"); System.out.println(col); //方法4:removeAll Collection c1 = new ArrayList(); c1.add(null); c1.add(180.5); col.removeAll(c1); System.out.println(col); //方法5:clear清除 // col.clear(); // System.out.println(col); //方法6:contains查找 boolean contains = col.contains("赵四"); System.out.println(contains?"赵四存在":"赵四没了"); //方法7:containsAll批量查找 Collection c2 = new ArrayList(); c2.add("赵四"); c2.add("蓝盈莹"); c2.add("周一围"); System.out.println(col.containsAll(c2)); //方法8:size 获取实际元素个数 System.out.println(col.size()); //方法9:isEmpty 判断是否为空 System.out.println(col.isEmpty()); } }
对象型元素示例:
/** * 此类用于演示使用Collection添加对象类型元素 ★ * */ public class TestCollection2 { public static void main(String[] args) { //1.创建Collection对象 Collection col = new ArrayList(); //2.调用方法 col.add(new Book("红楼梦",98,"曹雪芹")); col.add(new Book("西游记",93,"吴承恩")); col.add(new Book("水浒传",108,"施耐庵")); col.add(new Book("三国演义",88,"罗贯中")); col.add(new Book("西厢记",68,"王师傅")); System.out.println(col); col.remove(new Book("三国演义",88,"罗贯中")); // 这种删除无法删掉,需要按地址删除 System.out.println(col); } }
3.遍历方式 ★
迭代器工作特点:★
1、每次只能下移一位
2、只能下移不能上移!
注意: ★ 不适合做增删改
* ①使用迭代器过程,不适合做增删,容易报异常ConCurrentModificationException
* ②使用迭代器过程,可以做修改,但如果修改地址,没有效果!
* ③使用迭代器过程,如果非要做删除,可以使用迭代器本身的remove方法!
方式1:使用迭代器
迭代器的使用步骤:
① 获取迭代器对象,指针默认在最上方
② 通过调用hasNext判断下一个是否有元素
③ 通过调用next下移一位并获取当前元素
@Test public void test1(){ //3.遍历集合 //①获取迭代器 Iterator iterator = col.iterator(); //②判断,如果返回true,则进行下一步 while(iterator.hasNext()){ //③下移一位,并获取对应元素 System.out.println(iterator.next()); } }
方式二:为了简化Iterator的语法,jdk5.0出现了增强for
增强for的本质就是Iterator,只是语法简化了!
语法:
for(元素类型 元素名:集合或数组名){ //访问元素即可 }
示例:
@Test public void test2() { //3.遍历集合 for(Object o: col){ System.out.println(o);
} }
1.List接口的特点
- 有序(插入和取出的顺序一致的),原因:按一个整数索引记录了插入的位置,可以按索引操作
- 允许重复
2.List接口的特有方法
* add(object)增
* remove(index)按指定索引删
* set(index,object)改
* indexOf(object)查
* add(index,object)插入
* get(index)获取
public static void main(String[] args) { //1.创建List接口的对象 List list = new ArrayList(); //2.调用添加 list.add("john"); list.add("lucy"); list.add(null); list.add("john"); list.add(null); list.add("jack"); System.out.println(list); //特有方法1:add(index,object)插入 list.add(0, "张益达"); System.out.println(list); //特有方法2:remove(index) 删除 /* * 细节:如果元素类型为整型,如果删除的实参为int类型,默认是按索引删除;如果想按指定元素删除,则需要装箱再删除! */ list.remove(2); //特有方法3:set(index,object)修改 System.out.println(list); // [张益达, john, null, john, null, jack] list.set(2, "虚竹"); //特有方法4:indexOf(object)查找 System.out.println(list.indexOf("张益达")); //特有方法5:get(index)获取 System.out.println(list.get(30)); //3.遍历 System.out.println(list); }
3.List接口的遍历方式
//方式1:使用iterator @Test public void test1() { //3.遍历 Iterator iterator = list.iterator(); while(iterator.hasNext()){ Object book = iterator.next(); System.out.println(book); } } //方式2:使用增强for @Test public void test2() { //3.遍历 for (Object object : list) { System.out.println(object); } } //方式3:使用普通for @Test public void test3() { for(int i=0;i<list.size();i++){ Object object = list.get(i); System.out.println(object); } }
1.ArrayList
底层结构:可变数组
jdk8:
ArrayList中维护了Object[] elementData,初始容量为0.
第一次添加时,将初始elementData的容量为10
再次添加时,如果容量足够,则不用扩容直接将新元素赋值到第一个空位上
如果容量不够,会扩容1.5倍
jdk7:
ArrayList中维护了Object[] elementData,初始容量为10.
添加时,如果容量足够,则不用扩容直接将新元素赋值到第一个空位上
如果容量不够,会扩容1.5倍
jdk7和jdk8区别:
jdk7 相当于饿汉式,创建对象时,则初始容量为10
jdk8 相当于懒汉式,创建对象时,并没有初始容量为10,而在添加时才去初始容量为10
2.Vector、LinkedList
1)List接口的实现类:Vector
底层结构:可变数组,和ArrayList很像
2)List接口的实现类:LinkedList
底层结构:双向链表
LinkedList中维护了两个重要的属性 first和last,分别指向首节点和尾节点。
每个节点(Node类型)里面又维护了三个属性item、next、prev,分别指向当前元素、下一个、上一个元素。最终实现手拉手的链表结构!
3.总结:实现类对比
1)ArrayList和Vector的对比
底层结构 | 版本 | 线程安全(同步) | 效率 | 扩容的倍数 | |
ArrayList | 可变数组 | 新 | 不安全(不同步) | 较高 | 1.5倍 |
Vector | 可变数组 | 老 | 安全(同步) | 较低 | 2倍 |
2)ArrayList和LinkedList的对比
底层结构 | 线程安全(同步) | 增删的效率 | 改查的效率 | |
ArrayList | 可变数组 | 不安全(不同步) | 前面和中间的增删,较低 | 较高 |
LinkedList | 双向链表 | 不安全(不同步) | 前面和中间的增删,较高 | 较低 |
3)总结:
- 如果考虑线程安全问题:Vector
- 不考虑线程安全问题:
- 查找较多:ArrayList
- 增删较多:LinkedList
1.Set接口的特点
- 不允许重复,至多一个null
- 无序(插入和取出的顺序不一致),没有索引
2.Set接口的特有方法:没有特有方法,都是从Collection继承来的
3.Set接口的遍历方式:和Collection的遍历方式同
4.Set接口的实现类:HashSet
底层结构:维护了一个HashMap对象,也就是和HashMap的底层一样,基于哈希表结构的
如何实现去重【重点】
底层通过调用hashCode方法和equals方法实现去重
先调用hashCode,获取一个整数索引index(要存放在数组的位置, (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度)),如果该索引处没有元素,则直接可以添加;
如果该索引处有其他元素则进行equals判断,如果不相等,则以链表形式追加到已有元素后面;(不同数据的哈希值肯定不同,但计算出的索引可能相同;相同的数据哈希值和索引肯定相等)
如果相等,则直接覆盖,返回false
应用:通过HashSet添加元素时,如果认为内容相等的为重复元素,则需要重写该元素的hashCode和equals方法(引用型)
hashCode和equals重写示例:
public class Book{ private String name; private double price; private String author; /** * 原则: * 1、和属性值相关 * 2、属性一样的话,要求哈希值肯定一样 * 属性不一样的,尽最大的限度让哈希值不一样! */ // // 简单方式 // @Override // public int hashCode() { // return name.hashCode()+(int)price+author.hashCode()*31; // } // @Override // public boolean equals(Object obj) { // System.out.println(this.name+" pk "+((Book)obj).name); // // if(this==obj) // return true; // if(!(obj instanceof Book)) // return false; // Book b = (Book) obj; // // return this.name.equals(b.name)&&this.price==b.price&&this.author.equals(b.author); // } public String getName() { return name; } // 推荐的重写 @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((author == null) ? 0 : author.hashCode()); result = prime * result + ((name == null) ? 0 : name.hashCode()); long temp; temp = Double.doubleToLongBits(price); result = prime * result + (int) (temp ^ (temp >>> 32)); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Book other = (Book) obj; if (author == null) { if (other.author != null) return false; } else if (!author.equals(other.author)) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; if (Double.doubleToLongBits(price) != Double.doubleToLongBits(other.price)) return false; return true; } public void setName(String name) { this.name = name; } public double getPrice() { return price; } public void setPrice(double price) { this.price = price; } public String getAuthor() { return author; } public void setAuthor(String author) { this.author = author; } public Book(String name, double price, String author) { super(); this.name = name; this.price = price; this.author = author; } public String toString(){ /* * %s:字符串 * %c:字符 * %f:浮点 * %d:整数 */ return String.format("名称:%s 价格:%.2f 作者:%s",name,price,author); } }
【问题】为什么用eclipse复写hashCode方法,有31这个数字?
- 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)
- 并且31只占用5bits,相乘造成数据溢出的概率较小。
- 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。(提高算法效率)
- 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终的出来的结果只能被素数本身和被乘数还有1来整除!(减少冲突)
5.Set接口实现类:LinkedHashSet
LinkedHashSet 是 HashSet 的子类
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
LinkedHashSet插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
LinkedHashSet 不允许集合元素重复。
6.Set接口的实现类:TreeSet
特点:
- 不允许重复,里面不允许null
- 可以实现对里面元素进行排序
自然排序、定制排序
底层结构:底层维护了一个TreeMap,而TreeMap底层是红黑树结构,可以实现对元素进行排序
应用:
方式一:自然排序
要求:必须让添加元素的类型实现Comparable接口,实现里面的compareTo方法
方式二:定制排序
要求:创建TreeSet对象时,传入一个Comparator接口的对象,并实现里面的compare方法
示例:
public class TestTreeSet { //使用自然排序 @Test public void test1(){ //1.创建TreeSet对象 TreeSet set = new TreeSet(); //2.添加 set.add(new Book("百年孤独",100,"马尔克斯")); set.add(new Book("春风十里不如你",80,"冯唐")); set.add(new Book("多情剑客无情剑",60,"古龙")); set.add(new Book("春风十里不如你",80,"冯唐")); //3.遍历 CollectionUtils.print1(set); } //使用定制排序 @Test public void test2(){ //1.创建TreeSet对象 TreeSet set = new TreeSet(new Comparator(){ @Override public int compare(Object o1, Object o2) { Book b1 = (Book) o1; Book b2 = (Book) o2; return Double.compare(b2.getPrice(),b1.getPrice()); } }); //2.添加 set.add(new Book("百年孤独",100,"马尔克斯")); set.add(new Book("春风十里不如你",80,"冯唐")); set.add(new Book("多情剑客无情剑",60,"古龙")); set.add(new Book("春风十里不如你",80,"冯唐")); //3.遍历 CollectionUtils.print1(set); } }
如何实现去重:
通过比较方法的返回值是否为0来判断是否重复
1.Map接口的特点
用于保存一组键值对映射关系的
其中键不可以重复,值可以重复。而且一个键只能映射一个值
2.Map接口的常见方法
put 添加
remove删除
containsKey查找键
containsValue查找值
get根据键获取值
size获取键值对的个数
isEmpty判断元素是否为空
clear清除
entrySet 获取所有的关系
keySet获取所有的键
values获取所有的值
3.Map接口的遍历方式
方式1:通过调用entrySet
@Test public void test1() { //步骤1 :获取所有的关系 Set entrys = map.entrySet(); //步骤2:遍历所有的关系 Iterator iterator = entrys.iterator(); while(iterator.hasNext()){ //获取每一对关系 Map.Entry entry = (Entry)iterator.next(); //根据关系,获取对应的键 //根据关系,获取对应的值 System.out.println(entry.getKey()+":"+entry.getValue()); } }
方式2:通过调用keySet
@Test public void test2() { //步骤1:获取所有的键 Set keys = map.keySet(); //步骤2:遍历所有的键 for (Object key : keys) { System.out.println(key+":"+map.get(key)); } }
HashMap
1.底层分析
底层结构:哈希表
jdk7:数组+链表
jdk8:数组+链表+红黑树
JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
源码分析:
jdk8: HashMap中维护了Node类型的数组table,当HashMap创建对象时,只是对loadFactor初始化为0.75;table还是保持默认值null
当第一次添加时,将初始table容量为16,临界值为12
每次添加调用putVal方法:
①先获取key的二次哈希值并进行取与运算,得出存放的位置, (n - 1) & hash 判断当前元素存放的位置(这里的 n 指的是数组的长度)
②判断该存放位置上是否有元素,如果没有直接存放
如果该存放位置上已有元素,则进行继续判断:
如果和当前元素直接相等,则覆盖
如果不相等,则继续判断是否是链表结构还是树状结构,按照对应结构的判断方式判断相等
③将size更新,判断是否超过了临界值,如果超过了,则需要重新resize()进行2倍扩容,并打乱原来的顺序,重新排列
④当一个桶中的链表的节点数>=8 && 桶的总个数(table的容量)>=64时,会将链表结构变成红黑树结构
jdk7和jdk8的区别
1.jdk7:创建HashMap对象时,则初始table容量为16
jdk8:创建HashMap对象时,没有初始table,仅仅只是初始加载因子。只有当第一次添加时才会初始table容量为16.
2.jdk7:table的类型为Entry
jdk8:table的类型为Node
3.jdk7:哈希表为数组+链表,不管链表的总结点数是多少都不会变成树结构
jdk8:哈希表为数组+链表+红黑树,当链表的节点数>=8 && 桶的总个数(table的容量)>=64时,会将链表结构变成红黑树结构
【问题】HashMap 的长度为什么是2的幂次方
为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀。我们上面也讲到了过了,Hash 值的范围值-2147483648到2147483647,前后加起来大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。(n代表数组长度)。这也就解释了 HashMap 的长度为什么是2的幂次方。
取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。
2.应用层面:
要求添加元素的key重写hashCode和equals方法
Map接口的实现类:Hashtable
底层结构:哈希表 ,同HashMap
Hashtable是个古老的 Map 实现类,线程安全。
与HashMap不同,Hashtable 不允许使用 null 作为 key 和 value
与HashMap一样,Hashtable 也不能保证其中 Key-Value 对的顺序
Hashtable判断两个key相等、两个value相等的标准,与hashMap一致。
Map接口的实现类:TreeMap
底层结构:红黑树,可以实现对添加元素的key进行排序
应用:
自然排序:要求key的元素类型实现Comparable,并实现里面的compareTo方法
定制排序:要求创建TreeMap对象时,传入Comparator比较器对象,并实现里面的compare方法
Map接口的实现类的对比
HashMap和Hashtable的对比
底层结构 | 版本 | 线程安全(同步) | 允许null键null值 | |
HashMap | 哈希表 | 1.2 | 不安全 | 允许 |
Hashtable | 哈希表 | 1.0 | 安全 | 不允许 |
①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。
②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小(HashMap 中的tableSizeFor()
方法保证,下面给出了源代码)。
HashMap 多线程操作导致死循环问题 主要原因在于 并发下的Rehash 会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题,但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。 详情请查看:https://coolshell.cn/articles/9606.html
Map接口的实现类Properties
Properties 类是 Hashtable 的子类,该对象用于处理属性文件
由于属性文件里的 key、value 都是字符串类型,所以 Properties 里的 key 和 value 都是字符串类型
存取数据时,建议使用setProperty(String key,String value)方法和getProperty(String key)方法
Properties pros = new Properties(); pros.load(new FileInputStream("jdbc.properties")); String user = pros.getProperty("user"); System.out.println(user);
九、Collections工具类的学习
- 常见方法
reverse反转
sort排序
swap两各索引处元素的交换
shuffle随机打乱顺序
max获取最大值
min获取最小值
frequency 查找指定元素出现的次数
replaceAll替换旧值为新值
copy 复制,注意:新集合的size>旧集合的size
1.泛型的理解
泛型:jdk5.0出现的新特性;参数化的类型。可以将某个类型当做参数传递给类、接口或方法中
联想:
A a = new A();
class A<T>{
T t;
}
method("john");
public void method(String s){
//访问s
}
区别:
方法的参数:传递的是值,必须传参,只能用在方法中
泛型:传递的是类型,可以不用传参,默认为Object,可以用在方法、类、接口中
2.好处
- 编译时检查待添加的元素类型,提高了类型的安全性
- 减少了类型转换的次数,提高了效率
没有使用泛型:
String——>Object——>String
使用泛型:
String——>String——>String
- 减少了编译警告
3.泛型的语法和使用 ★
语法:
类型<指定的泛型> 名 = new 类型<>();
表示形式如下:
Set<Integer> set = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<>();//jdk7.0 类型推断 Set<Integer> set3 = new HashSet();//为了新老版本兼容性,不推荐使用 Set set4 = new HashSet<Integer>();//为了新老版本兼容性,不推荐使用
注意:
①泛型的类型只支持引用类型
②编译类型和运行类型的泛型必须一致
4.自定义泛型类、泛型方法、泛型接口【了解】
- 自定义泛型类
定义语法:
class MyClass<T>{ T name; publci void setName(T t){} }
注意:里面可以定义使用泛型的属性、方法也可以定义不使用泛型的普通属性和普通方法
但不能定义使用泛型的静态方法和使用泛型的数组初始化!
什么时候确定泛型类的具体类型?
答:创建对象时
语法:
MyClass<String> m = new MyClass<>();
- 自定义泛型接口
定义语法:
interface MyInter<T,U>{ U method(T t); }
什么时候确定泛型接口的具体类型?
答:被继承或实现时,可以确定,如果不确定,则默认是Object类型。如果想延续泛型,则需要将子接口或实现类设计成泛型形式!