1 集合
1.1 为什么会出现集合框架
[1] 之前的数组作为容器时,不能自动拓容
[2] 数值在进行添加和删除操作时,需要开发者自己实现添加和删除。
1.2 Collection接口
1.2.1 Collection基础API
Java集合框架提供了一套性能优良、使用方便的接口和类,它们位于java.util包中。
Collection表示集合的根接口,可以看成一个容器,存储了很多对象,这些对象称为Collection元素。Collection要求元素必须是引用数据类型。
Collection 根据其元素的特征可以分为
List接口->元素有序、可重复
Set 接口-> 元素无序、不可重复
思考:Collection提供了具备什么能力?=> 对容器增删改查
public class Test01 { public static void main(String[] args) { /** * 增:add/addAll * 删:clear/remove/removeAll/retainAll * 改: * 查:contains/constainsAll/size/isEmpty * 其他:equals * 遍历:iterator() */ Collection col1 = new ArrayList(); col1.add("apple"); // Object obj = "apple" 多态 col1.add("banana"); // Integer i = 1; 装箱 // 注意:Collection可以添加任意类型的数据,最好添加统一类型的数据方便未来统一访问。 Collection col2= new ArrayList(); col2.add("apple"); col2.add("banana"); // col1.addAll(col2); //System.out.println(col1); //col1.clear(); // 清空集合 //col1.remove("apple"); // 移除指定元素 //col1.removeAll(col2); // 移除指定集合中的多个元素 //col1.retainAll(col2); // 保留指定集合col2中的元素,其他删除 //System.out.println(col1); //col1.remove(1); // [apple, banana, 2] //System.out.println(col1.contains("apple")); //System.out.println(col1.containsAll(col2)); //System.out.println(col1.size()); // 返回元素个数 //System.out.println(col1.isEmpty()); boolean r = col1.equals(col2); System.out.println(r); } } |
1.2.2 遍历和Iterable
Iterable 表示可遍历的,具备遍历的能力。其定义了一个方法iterator用于返回集合上的迭代器,该迭代器用于foreach快速遍历。
public static void main(String[] args) { Collection col1 = new ArrayList(); col1.add("apple"); col1.add("coco"); col1.add("banana"); // 遍历集合中的元素 /* * Object 表示迭代元素类型 * item 表示迭代变量 * */ // 快速遍历 for (Object item : col1) { System.out.println(item); } // 迭代器遍历 Iterator it1 = col1.iterator(); // 返回集合的迭代器 while(it1.hasNext()) { String item = (String)it1.next(); System.out.println(item); } // 写法(更节省内存) for(Iterator it2 = col1.iterator();it2.hasNext();) { String item = (String)it2.next(); System.out.println(item); } } |
1.3 List接口
List 接口称为有序的序列,提供了索引(index)对容器中的元素进行增、删、改、查。
index让List集合中的元素有序、可重复。
1.3.1 List接口常用方法
public static void main(String[] args) { /** * 增:add(index,e)/addAll(index,c)/add(e)/addAll(c)/ * 删:remove(index)/clear()/remove(e)/removeAll(c)/retainAll(c) * 改:set(index,e); * 查:get(index)/indexOf(e)/lastIndexOf(e)/contains/constainsAll/size/isEmpty * 其他:equals * 遍历:iterator() / listIterator() */ List list1 = new ArrayList(); // 【1】添加 // 追加 list1.add("apple"); list1.add("banana"); // 在指定index位置添加元素coco list1.add(0,"coco"); List list2 = new ArrayList(); list2.add(1); list2.add(2); list1.addAll(0, list2); System.out.println(list1); // 【2】移除 //list1.remove(0); //System.out.println(list1); // 【3】修改 list1.set(0, 100); System.out.println(list1); // 【4】查看元素 可能产生IndexOutOfBoundsException // System.out.println(list1.get(6)); System.out.println(list1.indexOf(200)); // list1.add(2); // System.out.println(list1.lastIndexOf(2)); } |
1.3.2 List接口遍历
List接口中提供了一个listIterator方法,返回列表的列表迭代器,属于ListIterator接口,提供以任意方向(正向、逆向)遍历列表,同时在遍历列表的过程中还可以操作列表。
public static void main(String[] args) { // List 集合的遍历 List list = new ArrayList(); list.add("apple"); list.add("banana"); list.add("coco"); // 【1】 for 循环 for(int i=0;i<list.size();i++) { String item = (String) list.get(i); System.out.println(item); } // 【2】 快速遍历 for(Object item:list) { System.out.println(item); } // 【3】iterator Iterator it1 = list.iterator(); while(it1.hasNext()) { System.out.println(it1.next()); } // 【4】listIterator 获取列表的迭代器 ListIterator it2 = list.listIterator(); // 正向遍历(A) while(it2.hasNext()) { System.out.println(it2.next()); } // 逆向遍历(B) while(it2.hasPrevious()) { System.out.println(it2.previous()); } // 【5】从指定位置开始迭代(C) System.out.println("--listIterator(index)--"); ListIterator it3 = list.listIterator(1); while(it3.hasNext()) { System.out.println(it3.next()); } } |
思考:Iterator和ListIterator区别?
1.4 数据结构(补充知识)
1.4.1 线性表
根据物理空间是否连续,可以把线性表分为数组和链表。
数组:物理上连续、逻辑上也连续的内存空间,通过index来访问元素。
链表:物理上不连续、逻辑上连续的内存空间,也可以通过index来访问元素。
1.4.2 队列
队列是以一个方向先进先出的数据结构
1.4.3 栈
栈是一种先进后出的数据结构
1.5 ArrayList、 LinkedList、Vector
1.5.1 ArrayList
ArrayList 类是List接口的实现类,底层数据结构是数组。
ArrayList 是数组的包装类,jdk1.2出现,提供了操作底层数据的很多方法,同时向ArrayList中添加元素时,容器可以自动拓容。
ArrayList 是线程不安全。
API和List接口一样。
1.5.2 Vector
Vector 类是List接口的实现类,底层数据结构也是数组。
Vector是数组的包装类,jdk1.0出现,提供了操作底层数据的很多方法,同时向Vector中添加元素时,容器可以自动拓容,也提供了自身特有的方法xxxElement等方法。
Vector 是线程安全。
面试题:ArrayList和Vector有什么区别?
相同点:
[1] 都是List接口的实现类、底层数据结构都是数组
不同点
[1] ArrayList jdk1.2;Vector jdk1.0
[2] ArrayList 线程不安全,效率高;Vector 线程安全,效率低
[3] Vector较ArrayList拥有特有的方法。
1.5.3 LinkedList
LinkedList 是List接口的实现类,底层数据结构是链表。
LinkedList是链表的包装类,jdk1.2出现,提供了操作底层数据的很多方法,当向LinkedList中添加元素时,通过链入元素增加容量。
LinkedList线程不安全。
public class Test01 { public static void main(String[] args) { List list1 = new LinkedList(); // 【1】添加 list1.add("apple"); list1.add("banana"); list1.add("coco"); System.out.println(list1); // 【2】删除 list1.remove("apple"); // 【3】修改 list1.set(0, "banana x"); System.out.println(list1); // 【4】查看 System.out.println(list1.get(0)); } } |
LinkedList也实现了栈、队列、双向队列接口。
以栈的方式访问LinkedList
public class Test02 { public static void main(String[] args) { // 以栈形式访问 LinkedList stack1 = new LinkedList(); // 入栈 stack1.push("apple"); stack1.push("banana"); // 出栈 System.out.println(stack1.pop()); System.out.println(stack1.pop()); // 如果栈中没有元素,抛出NoSuchElementException System.out.println(stack1.pop()); } } |
以队列(Queue接口)的方式访问LinkedList
public static void main(String[] args) { // 以队列形式访问 LinkedList queue = new LinkedList(); // 入队 /* 头(出口)<----------尾(入口) --------------------- apple banana coco --------------------- */ //queue.add("apple"); //queue.add("banana"); //queue.add("coco"); //System.out.println(queue); // 出队 //queue.remove(); //queue.remove(); //queue.remove(); // 抛出NoSuchElementException //queue.remove(); //System.out.println(queue); // 检测元素:获取但不移除此列表的头(第一个元素) //System.out.println(queue.element()); //System.out.println(queue.element()); /*queue.offer("apple"); queue.offer("banana"); queue.offer("coco");*/ System.out.println(queue); //queue.poll(); //System.out.println(queue); //queue.poll(); //queue.poll(); // 如果队列为空,返回null //String item = (String)queue.poll(); //System.out.println(item); System.out.println(queue.peek()); } |
以双向队列(DeQue接口)方式访问LinkedList
public static void main(String[] args) { // 以双向队列形式访问 LinkedList queue = new LinkedList(); /* * 头 尾 <------------------- --------------------- apple banana coco --------------------- -------------------> */ queue.addFirst("apple"); queue.addLast("banana"); queue.addLast("coco"); //queue.removeFirst(); //queue.removeLast(); //queue.removeLast(); // NoSuchElementException //queue.removeLast(); //System.out.println(queue); System.out.println(queue.getFirst()); System.out.println(queue.getLast()); } |
1.6 泛型(generic)
1.6.1 泛型概念(A)
泛型允许程序员在强类型程序设计语言中编写代码时定义一些可变部分。
那些可变部分在使用前必须作出指明。形式
ArrayList<T> list = null;
表示声明了一个ArrayList容器,容器中存储的数据类型是T类型,T类型此时就是泛型。
T表示一种数据类型,但现在还不确定。
泛型在使用时,一定要确定类型。
ArrayList<String> list2 = new ArrayList<String>();
表示声明了一个ArrayList容器,容器中存储的数据类型是String类型。
泛型只在编译器起作用,运行时不知道泛型的存在。
1.6.2 泛型擦除(C)
public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); System.out.println(list instanceof ArrayList); System.out.println(list instanceof ArrayList<?>); System.out.println(list instanceof ArrayList<Integer>); //error } |
Cannot perform instanceof check against parameterized type ArrayList<Integer>. Use the form ArrayList<?> instead since further generic type information will be erased at runtime |
泛型就是程序设计过程中将类型参数化。
1.6.3 泛型类(A)
当一个类中的属性类型不确定时,此时可以把该属性声明为泛型。
public class Student<T> { private T t; public T getT() { return t; } public void setT(T t) { this.t = t; } } |
思考:请设计一个容器,提供增删改查的方法?
1.6.4 泛型方法(A)
当一个方法的形参参数类型不确定时,可以使用泛型。
public class Student{ /* public void add(int a,int b) { System.out.println(a+b); } public void add(float a,float b) { System.out.println(a+b); } public void add(char a,char b) { System.out.println(a+b); } public void add(String a,String b) { System.out.println(a+b); } */ public <T> void add(T a,T b) { System.out.println(a.toString()+b.toString()); } } |
泛型方法在一定程度上优化了方法重载,不能取代。
泛型的可变参数
// 方法的可变参数 /*public void add(int...args) { // 方法的可变参数在方法调用时,以args数组形式存在于方法中 System.out.println(Arrays.toString(args)); }*/ public <T> void add(T...args) { System.out.println(Arrays.toString(args)); } |
泛型的可变参数方法进一步优化了方法重载,不能完全取代。
1.6.5 泛型接口(C)
当泛型接口中的方法类型(返回值、形参)不太确定,可以使用泛型接口。
public interface MyInterface<T> { public void showInfo(T a); } |
实现类知道操作接口中方法的参数类型
public class ImplClass implements MyInterface<String>{ @Override public void showInfo(String a) { // TODO Auto-generated method stub } } |
实现类不知道实现接口中方法的参数类型,实现类继续泛下去。
public class ImplClass2<T> implements MyInterface<T>{ @Override public void showInfo(T a) { // TODO Auto-generated method stub } } |
1.6.6 泛型的上限和下限(C)
[1]泛型上限
public static void print(ArrayList<? extends Pet> list) { for(Pet pet:list) { pet.showInfo(); } } |
<? extends A> 表示?必须A的子类,A作为上限已经确定。
ArrayList<? extends A> list 表示声明了一个容器list,list中存储的元素必须是A的子类。
[2]泛型下限
<? super A> 表示?必须A的父类,A作为下限已经确定。
ArrayList<? super A> list 表示声明了一个容器list,list中存储的元素必须是A的父类。
1.7 Iterator和ListIterator
读Iterator实现类源码(hasNext、next)
public static void main(String[] args) { ArrayList<String> list = new ArrayList<String>(); list.add("apple"); list.add("banana"); list.add("coco"); // 需求:在遍历的过程中,添加元素 Iterator<String> it = list.iterator(); while(it.hasNext()) { String item = it.next(); if(item.equals("banana")) { // list.add("test"); } } System.out.println(list); ListIterator<String> it2 = list.listIterator(); while(it2.hasNext()) { String item = it2.next(); if(item.equals("banana")) { it2.add("test"); } } System.out.println(list); } |
Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909) at java.util.ArrayList$Itr.next(ArrayList.java:859) at cn.sxt06.iterator.Test01.main(Test01.java:18) |
当遍历一个集合时,不能对集合进行添加操作,可能会出现并发修改异常。如果要对其进行添加操作,需要使用ListIterator接口。
1.8 Set接口
Set接口表示的集合元素是无序、唯一的。
public static void main(String[] args) { /** * 增:add/addAll * 删:clear/remove/removeAll/retainAll * 改: * 查:contains/containsAll/isEmpty/equals/size * 遍历:iterator */ Set<String> set = new HashSet<String>(); // 【1】添加 boolean r; r = set.add("apple"); System.out.println(r); set.add("coco"); set.add("banana"); r = set.add("apple"); // 没有添加成功 System.out.println(r); // 【2】删除 // set.clear(); set.remove("coco"); System.out.println(set); } |
set遍历
public static void main(String[] args) { Set<String> set = new HashSet<String>(); set.add("apple"); set.add("coco"); set.add("banana"); // foreach for(String str:set) { System.out.println(str); } Iterator<String> it = set.iterator(); while(it.hasNext()) { System.out.println(it.next()); } } |
1.8.1 HashSet
HashSet是Set接口的实现类,底层数据结构是哈希表。
HashSet 线程不安全。
1.8.1.1 HashSet的工作原理
HashSet底层数据结构是哈希表/散列表
HashSet存储元素时
[1] 求元素的hash码
[2] equals比较集合是否存在相同元素。
思考:如何把自定义对象存入HashSet中?
package cn.sxt02.hashset; public class Student { private String id; private String name; private int age; // … @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + age; result = prime * result + ((id == null) ? 0 : id.hashCode()); result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Student other = (Student) obj; if (age != other.age) return false; if (id == null) { if (other.id != null) return false; } else if (!id.equals(other.id)) return false; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } @Override public String toString() { return "Student [id=" + id + ", name=" + name + ", age=" + age + "]"; } } |
总结:
[1]存入HashSet中的元素必须实现hashCode和equals方法
[2]元素的hashCode一样,经过y=k(x)散列出来的位置一定一样。元素的hashCode不一样,经过y=k(x)散列出来的位置有可能一样。
[3] 散列函数多半是 hashCode % 空间长度。为什么?
1.8.2 LinkedHashSet
LinkedHashSet 是Set接口的实现类,底层数据结构是哈希表+链表,其中链表应用维持添加次序。
画LinkedHashSet工作原理图?
1.8.3 TreeSet
TreeSet 是Set接口的实现类,底层数据结构是二叉树,按照自然升序存储。
TreeSet实现线程不安全的。
1.8.3.1 TreeSet工作原理
TreeSet<Integer> set = new TreeSet<Integer>(); set.add(2); set.add(3); set.add(1); set.add(4); set.add(3); System.out.println(set); |
当向TreeSet存入一个元素时,
[1]把待添加的元素T和根节点比较,如果T小于根节点,T存入左子树;如果T大于根节点,T存入右子树
[2]一旦确定子树后,T元素要和子树根节点比较,重复[1]步骤,如果需要相等,丢弃T。
需求: 把自定义对象按年龄存入TreeSet中?
把自定义对象存入TreeSet中一定要提供比较策略,否则会出现ClassCastException异常。
比较策略分为两种,一种是内部比较器,一种是外部比较器。
1.8.3.2 内部比较器
内部比较器就是实现Comparable接口
package cn.sxt04.treeset; public class Student implements Comparable<Student>{ private String id; private String name; private int age; // . . . @Override public int compareTo(Student o) { // 按照年龄比较 if(this.getAge() < o.getAge()) { return -1; }else if(this.getAge() == o.getAge()) { return 0; }else { return 1; } } } |
思考:把自定义对象按年龄升序存入treeset中,如果年龄一样,再按照名字自然升序。
@Override public int compareTo(Student o) { // return this.getAge() - o.getAge(); // 按照年龄比较 if(this.getAge() < o.getAge()) { return -1; }else if(this.getAge() == o.getAge()) { /*if(this.getName().compareTo(o.getName()) < 0) { return -1; }else if(this.getName().compareTo(o.getName()) == 0) { return 0; }else { return 1; }*/ return this.getName().compareTo(o.getName()); }else { return 1; } } |
1.8.3.3 外部比较器
当开发者不知道添加元素类的源代码时,此时可以使用外部比较策略。外部比较器就是Compartor接口。
public class Test04 { public static void main(String[] args) { LenCompare lenCompare = new LenCompare(); TreeSet<String> set = new TreeSet<String>(lenCompare); set.add("alex"); set.add("ben"); set.add("cocos"); set.add("scott"); // 需求:按照字符串的长度升序? System.out.println(set); } } class LenCompare implements Comparator<String> { @Override public int compare(String o1, String o2) { // [1] 按名称长度升序 // System.out.println("o1:"+o1); // System.out.println("o2:"+o2); // return o1.length() - o2.length(); // [2] 先按照名称长度,如果相等,按名称自然顺序 /*if (o1.length() == o2.length()) { return o1.compareTo(o2); } return o1.length() - o2.length();*/ // [3]按照长度降序 return o2.length() - o1.length(); } } |
package cn.sxt04.treeset;
import java.util.Comparator; import java.util.TreeSet;
public class Test05 { public static void main(String[] args) {
LenCompare lenCompare = new LenCompare(); TreeSet<String> set = new TreeSet<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { return o1.length() - o2.length(); } }); set.add("alex"); set.add("ben"); set.add("cocos");
set.add("scott");
System.out.println(set);
} } |
Map接口
java集合详解(附栈,队列)的更多相关文章
-
Java集合详解2:一文读懂Queue和LinkedList
<Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整理到我在GitHub上的<Java面试指南>仓库,更多精彩内容请到我的仓库里查 ...
-
Java集合详解1:一文读懂ArrayList,Vector与Stack使用方法和实现原理
本文非常详尽地介绍了Java中的三个集合类 ArrayList,Vector与Stack <Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整 ...
-
Java集合详解8:Java集合类细节精讲,细节决定成败
<Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整理到我在GitHub上的<Java面试指南>仓库,更多精彩内容请到我的仓库里查 ...
-
Java集合详解7:一文搞清楚HashSet,TreeSet与LinkedHashSet的异同
<Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整理到我在GitHub上的<Java面试指南>仓库,更多精彩内容请到我的仓库里查 ...
-
Java集合详解6:这次,从头到尾带你解读Java中的红黑树
<Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整理到我在GitHub上的<Java面试指南>仓库,更多精彩内容请到我的仓库里查 ...
-
Java集合详解4:一文读懂HashMap和HashTable的区别以及常见面试题
<Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整理到我在GitHub上的<Java面试指南>仓库,更多精彩内容请到我的仓库里查 ...
-
Java集合详解3:一文读懂Iterator,fail-fast机制与比较器
<Java集合详解系列>是我在完成夯实Java基础篇的系列博客后准备开始写的新系列. 这些文章将整理到我在GitHub上的<Java面试指南>仓库,更多精彩内容请到我的仓库里查 ...
-
Java集合详解8:Java的集合类细节精讲
Java集合详解8:Java集合类细节精讲 今天我们来探索一下Java集合类中的一些技术细节.主要是对一些比较容易被遗漏和误解的知识点做一些讲解和补充.可能不全面,还请谅解. 本文参考:http:// ...
-
Java集合详解6:TreeMap和红黑树
Java集合详解6:TreeMap和红黑树 初识TreeMap 之前的文章讲解了两种Map,分别是HashMap与LinkedHashMap,它们保证了以O(1)的时间复杂度进行增.删.改.查,从存储 ...
-
Java集合详解3:Iterator,fail-fast机制与比较器
Java集合详解3:Iterator,fail-fast机制与比较器 今天我们来探索一下LIterator,fail-fast机制与比较器的源码. 具体代码在我的GitHub中可以找到 https:/ ...
随机推荐
-
学习笔记——EM算法
EM算法是一种迭代算法,用于含有隐变量(hidden variable)的概率模型参数的极大似然估计,或极大后验概率估计.EM算法的每次迭代由两步组成:E步,求期望(expectation):M步,求 ...
-
js创建对象的方法
1. 使用Object构造函数来创建一个对象,下面代码创建了一个person对象,并用两种方式打印出了Name的属性值. var person = new Object(); person.name= ...
-
ural 1208 Legendary Teams Contest
题意描述:给定K支队伍,每队三个队员,不同队伍之间队员可能部分重复,输出这些队员同时能够组成多少完整的队伍: DFS,利用DFS深度优先搜索,如果该队所有队员都没有被访问过,那么将该队计入结果,再去选 ...
-
MATLAB对话框设计[转]
Matlab之对话框 对话框设计:在图形用户界面程序设计中,对话框是重要的信息显示和获取输入数据的用户界面对象. 1.公共对话框: 公共对话框是利用windows资源的对话框,包括文件打开.文件保存. ...
-
对EV-Globe5.0资源体系的简单理解
如果直接从OpenGL或DirectX底层做起的话,根本就不存在资源管理这一个思想.所谓的资源,就是说内容要从文件读取为我所用的那些文件,所以我们看到的更多的是模型.骨骼.材质.着色器. ...
-
MongoDB的常用命令
[转]http://blog.csdn.net/ithomer/article/details/17111943 mongodb由C++编写,其名字来自humongous这个单词的中间部分,从名字可见 ...
-
ios7 webapp touch bug
// ios7 touchstart bug if(navigator.userAgent.indexOf("iPhone OS 7") != -1){ var startX = ...
-
javap -s 查看java方法签名
工程先用eclipse生成class目录,转到class目录下执行: javap -s com.example.hellojni.MainActivity Compiled from "Ma ...
-
2016-04-25-信息系统实践手记6-JS调用Flex的性能问题一例
layout: post title: 2016-04-25-信息系统实践手记6-JS调用Flex的性能问题一例 key: 20160425 tags: GIS JS FLEX 技术选型 性能 API ...
-
CentOS 7.x 用shell增加、删除端口
一.在/usr/local/sbin/下创建port文件,不要扩展名,并给权限 chom 777 port #!/bin/bash num=$# ok=0 if [ ${num} == 1 ]; t ...