集合(ArrayList|LinkedList|vector|stack|Queue|hashSet|TreeSet|HashMap|TreeMap)

2024-02-22 13:22:46

集合
collection接口 map接口
存储的都是value 存储的是以key-value形式存在
List接口 set接口 Queue接口
有序可重复无序无重复有序可重复 key无序无重复 value无序可重复

序：顺序，添加进去的元素，取得元素的顺序一致，注意指的不是集合自己的顺序。
重复：两个对象元素一致。

一、List集合———ArrayList类

1.ArrayList 2.LinkedList 3.Vector
1.ArrayList—>所属的包：java.util.ArrayList底层就是一个数组，利用(动态)数组形式实现，1.5倍扩容。
2.ArrayList特点适合遍历轮询，不适合插入删除。
3.如何构建一个ArrayList对象：
无参数构造方法，带默认容量的构造方法,带collection参数的构造方法。
4.ArrayList中常用的方法：增删改查 add(E e); remove(index); set(index value); get(index); size();
类中其它常用的方法：
addAll(Collection c); 并集 removeAll();差集 retainAll();交集
int=indexOf(Object obj); lastIndexOf(); boolean=contains(Object);找寻某一个给定的元素是否在集合中拥有 List=subList(int begin,int end);
boolean=isEmpty(); clear(); ensureCacity(); iterator();迭代器
toArray(T[] x); trimToSize();//变成有效元素个数那么长

常见的方法—小容器
add(E e); add(int index,E e);
add(int index,Collection c);
ensureCapacity(int minCapacity);
E =get(int index);
Iterator=list.iterator();//迭代器
remove(int index); remove(Object obj);
E=set(int index,E value);
int size();有效元素个数，集合一旦元素发生个数变化，值就改变。不同于数组的length。
toArray();集合变成数组

5.泛型
用来规定数据类型。注意：泛型造型
在类或接口描述的时候，可以使用某种符号来表示一个未知的类型。
在类型使用的时候，需要一个具体类型来代替。
注意：泛型需要使用引用数据类型来代替。

关于泛型的问题：
由于arrayList底层是一个Object[] 什么类型都可以存进去。
取出来的时候多肽的效果，需要自己造型，显得用起来非常的麻烦。
JDK1.5之后—>泛型
用来规定数据类型的，定义的时候用一个符号代替某种类型。
在使用的时候用具体的数据类型，将定义的那个符号替换掉。
泛型可以用在哪里？
1.泛型类
类定义的时候描述某种数据类型，集合的使用就是这样。
2.泛型接口
与泛型类的使用基本一致，子类实现接口时必须添加泛型。
3.泛型方法
方法调用时传参数，方法的泛型与类无关，带有泛型的方法可以不放在带有泛型的类中
4.高级泛型规范边界 extends super
方法参数泛型限制：addAll(Collection<? extends E> c);

二、List集合———Vector类

1.java.util包。
2.是ArrayList集合的早期版本。（StringBuffer早期 StringBuilder后来）
vector底层也是利用（动态）数组的形式存储。
vector是线程同步的，安全性高，效率低。
3.扩容方式与ArrayList不同
默认是扩容2倍，可以通过构造方法创建对象时修改这一机制。
4.构造方法
5.常用方法

Stack栈类继承自Vector类

1.java.util包。
2.构造方法只有一个五参数。
3.除了继承自Vector类的方法外还有特殊的方法
push(E e);将某一个元素压入栈顶(add());
E=pop();将某一个元素从栈顶取出并删掉(E=remove())
E=peek();查看栈顶的一个元素，不是删除(get())
boolean=empty();判断栈内元素是否为空(isEmpty())
int=search();查找给定的元素在栈中的位置(indexOf())
4.应用：中国象棋悔棋
栈中存储每一次操作的步骤
撤销功能

Stack<String> stack=new  Stack<String>();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack);
System.out.println(stack.peek());//c
System.out.println(stack);
System.out.println(stack.search("b"));//不是索引，是第几个

三、collection集合———Queue接口

1.java.util。通常子类LinkedList，ArrayDeque。
2.通常五参数构造方法创建。
3.一般方法：
add();
element();—>get
remove()
boolean=offer(E e);//相当于add 不会抛出异常
E=peek();//相当于element方法
E=poll();剪短// 相当于remove();
4.双十一零点秒杀
所有进入秒杀系统的人存入队列。

四、list集合————LinkedList类

1.java.util包。自己封装过LinkedBox，内部类Node对象(节点 prev item next)
2.底层使用双向链表的数据结构形式来存储：适合于插入或删除，不适合遍历轮询。
3.构建对象：无参数构造方法，带参数的构造方法(collection)
4.常用的方法
增删改查 add() remove() set() get() size()
手册中提供的其他常用方法
addAll() addFirst() addLast() clear() contains()
element() getFirst() getLast() indexOf() lastIndex()
…
5.插入删除的特性是否像想的那样
对比：ArrayList LinkedList

package testlist;
public class TestLinked{
	public static void main(String[] args){
		//ArrayList   向后插入时间
		ArrayList<String> arrayList=new ArrayList<String>();
		long time1=System.currentTimeMillis();
		for(int i=1;i<=200000;i++){
			arrayList.add("a");
		}
		long time2=System.currentTimeMillis();
		System.out.println('arrayList向后追加元素时间："+(time2-time1));//5毫秒  20万次
	}
}

package testlist;
public class TestLinked{
	public static void main(String[] args){
		//ArrayList  向前插入元素时间
		ArrayList<String> arrayList=new ArrayList<String>();
		long time1=System.currentTimeMillis();
		for(int i=1;i<=200000;i++){
			arrayList.add(0，"a");
		}
		long time2=System.currentTimeMillis();
		System.out.println('arrayList向前插入元素时间："+(time2-time1));//1104毫秒  20万次
	}
}

package testlist;
public class TestLinked{
	public static void main(String[] args){
		//ArrayList  遍历元素时间
		ArrayList<String> arrayList=new ArrayList<String>();
		for(int i=1;i<=200000;i++){
			arrayList.add("a");
		}
		long time1=System.currentTimeMillis();
		for(String v:arrayList){
			System.out.println(v);
		}
		long time2=System.currentTimeMillis();
		System.out.println('arrayList遍历轮询元素时间："+(time2-time1));//3毫秒  20万次  //删除元素  4037毫秒
	}
}

package testlist;
public class TestLinked{
	public static void main(String[] args){
		//LinkedList   向后插入时间
		LinkedList<String> linkedList=new LinkedList<String>();
		long time1=System.currentTimeMillis();
		for(int i=1;i<=200000;i++){
			linkedList.add("a");
		}
		long time2=System.currentTimeMillis();
		System.out.println('linkedList向后追加元素时间："+(time2-time1));//4毫秒  20万次
	}
}

package testlist;
public class TestLinked{
	public static void main(String[] args){
		//LinkedList   向后插入时间
		LinkedList<String> linkedList=new LinkedList<String>();
		long time1=System.currentTimeMillis();
		for(int i=1;i<=200000;i++){
			linkedList.addFirst("a");
		}
		long time2=System.currentTimeMillis();
		System.out.println('linkedList向前插入元素时间："+(time2-time1));//4毫秒  20万次
	}
}

package testlist;
public class TestLinked{
	public static void main(String[] args){
		//LinkedList   向后插入时间
		LinkedList<String> linkedList=new LinkedList<String>();
		for(int i=1;i<=200000;i++){
			linkedList.addFirst("a");
		}
		long time1=System.currentTimeMillis();
		for(String v:linkedList){
			System.out.println(v);
		}
		long time2=System.currentTimeMillis();
		System.out.println('linkedList遍历轮询元素时间："+(time2-time1));//4毫秒  20万次   //删除时间  2毫秒
	}
}

五、Set集合———HashSet类

set具体的类：HashSet TreeSet。基本的使用。
无序：添加的顺序，获取的顺序不一致（不是集合本身是否有序 Tree自然有序）。
无重复：添加的元素不能一致（如果出现重复元素，只存第一个，不再存入）。
集合本身是有自己的算法排布顺序，hash算法。

1.java.util。数组+链表=散列表(连接链表）。底层数组，初始数组16个，0.75扩容。
2.如何创建对象，无参数，有参数。
3.集合容器的基本使用
增删改查
boolean=add(value); addAll(collection c); retainAll removeAll
boolean=remove(Object);
没有修改方法。
可以使用增强for进行集合遍历 1.5之后。
iterator();获取一个迭代器对象。
size();//有效元素个数。

package testset;
public class TestHashSet{
	public static void main(String[] args){
		HashSet<String> set=new HashSet<String>();
		set.add("A");
		set.add("a");
		set.add("b");
		set.add("B");
		set.add("c");
		set.add("C");
		//获取一个迭代器对象  通过set集合获取
		Iterator<String>  it=set.iterator<String>();//Iterator接口  多肽效果
		//判断下一个位置是否有元素
		if(it.hasNext){
			String value=it.next();
			System.out.println(value);
		}
	}
}

4.无重复原则
首先通过String类型和Person类型存储。
大概猜测无重复的原则利用equals方法进行比较。
如果我们想要让Person对象的name一致的话，认为是同一个对象。
我们可以重写equals方法。
重写了equals方法，发现还没有产生无重复的效果。
证明可能原则不止equals一个方法这么简单。
还有另一个规则同时起着作用 hashCode方法 int。
五个Person对象只剩一个，第一次存储的还是最后一次存储

package testset;
public class Person{
	private String name;
	private  int  testNmu;//记录人是谁
	public Person(String name,int testNum){
		this.name=name;
		this.testNum=testNum;
	}

	//重写equals方法  将person放入set集合中  去掉重复
	public boolean equals(object obj){
		if(this==obj){
			return true;
		}
		if(obj instanceof  Person){
			//obj还原回Person类型
			Person  anotherPerson=(Person)obj;
			//this  anotherPerson比较对象中的name属性
			if(this.name.equals(anotherPerson.name)){//递归
				return true；
			}
		}
		return false;
	}
	
	//重写  hashCode方法
	public int hashCode(){
		//两个person对象name属性一致  需要让hashCode返回值一致
		return this.name.hashCode();
	}
	
	//重写toString方法  让对象打印输出的时候直接输出对象的属性  而不是hashCode码
	public String toString(){
		StringBuilder builder=new StringBuilder("{");
		builder.append(this.name);
		builder.append(",");
		builder.append(this.testNum);
		builder.append("}");
		return new String(builder);
	}
	public String getName(){
		return this.name;
	}
	public String getTestNum(){
		return this.TestNum;
	}
}

package testset;
public class Person{
	public static void main(String[] args){
		HashSet<String>  stringSet=new HashSet<String>();
		stringSet.add(new String("某某",1));
		stringSet.add(new String("某某",2));
		stringSet.add(new String("某某",3));
		stringSet.add(new String("某某",4));
		stringSet.add(new String("某某",5));
		System.out.println(“string集合的size：”+stringSet.size);//1
		System.out.println(personSet.iterator().next().getTestNum());
		System.out.println(personSet);
		
		HashSet<Person>  Personset=new HashSet<Person>();
		Personset.add(new Person("某某"))；
		Personset.add(new Person("某某"))；
		Personset.add(new Person("某某"))；
		Personset.add(new Person("某某"))；
		Personset.add(new Person("某某"))；
		System.out.println(“person集合的size：”+personSet.size);//5
	}
}

六、Set集合———TreeSet类

无序无重复 java.util。底层TreeMap 二叉树利用Node(left item right)。
五参数构造方法带Collection构造方法。
基本常用方法
add(E e); iterator(); remove(E e); 没有修改 size();
无重复的规则是如何实现的
treeSet集合本身有顺序我们指的无序存入的和取出来的不一致。
compareTo----->String类按照字母的自然顺序排布(Unicode)。

如果想要把自己写的类型，比如Person对象存入TreeSet集合里。
不能随意地存储需要让自己写的类先实现Comparable接口。

package testset;
 
import java.util.TreeSet;
public class TestTreeSet{
	public static void main(String[] args){
		TreeSet<String>  stringSet=new TreeSet<String>();
		stringSet.add("b");
		StringSet.add("C");
		StringSet.add("A");
		StringSet.add("c");
		stringSet.add("a");
		StringSet.add("B");
		StringSet.add("C");
		StringSet.add("a");
		System.out.println(stringSet.size());//6  set家族如有相同的对象，拒绝存入
		System.out.println(stringSet);//集合本身有自己的排布顺序
	}
}

package testset;
 
import java.util.TreeSet;

public class TestTreeSet{
	public static void main(String[] args){
		TreeSet<String>  stringSet=new TreeSet<String>();
		stringSet.add(new String("某某"));
		StringSet.add(new String("某某"));
		StringSet.add(new String("某某"));
		StringSet.add(new String("某某"));
		stringSet.add(new String("某某"));
		System.out.println(stringSet.size());//1  set家族如有相同的对象  拒绝存入

		TreeSet<Person>  personSet=new TreeSet<Person>();
		personSet.add(new Person("某某",18,1));
		personSet.add(new Person("某某",16,2));
		personSet.add(new Person("某某",20,3));
		personSet.add(new Person("某某",24,4));
		personSet.add(new Person("某某",25,5));
		System.out.println(personSet.size);//???   5
		System.out.println(/personSet);
		//ClassCastException---->造型异常
		
	}
}

package testset;
public class Person implements Comparable<Person>{
	private String name;
	private int age;
	private  int  testNmu;//记录人是谁
	public Person(String name,int age,int testNum){
		this.name=name;
		this.age=age;
		this.testNum=testNum;
	}

	//重写equals方法  将person放入set集合中  去掉重复
	public boolean equals(object obj){
		if(this==obj){
			return true;
		}
		if(obj instanceof  Person){
			//obj还原回Person类型
			Person  anotherPerson=(Person)obj;
			//this  anotherPerson比较对象中的name属性
			if(this.name.equals(anotherPerson.name)){//递归
				return true；
			}
		}
		return false;
	}
	
	//重写  hashCode方法
	public int hashCode(){
		//两个person对象name属性一致  需要让hashCode返回值一致
		return this.name.hashCode();
	}
	
	//重写toString方法  让对象打印输出的时候直接输出对象的属性  而不是hashCode码
	public String toString(){
		StringBuilder builder=new StringBuilder("{");
		builder.append(this.name);
		builder.append(",");
		builder.append("this.age");
		builder.append(",");
		builder.append(this.testNum);
		builder.append("}");
		return new String(builder);
	}

	//如果想要让person对象存入TreeSet集合内 必须实现接口  重写这个方法
	public int compareTo(Person o){
		int value=this.name.compareTo(o.name);
		if(value!=0{
			return this.age-o.age;//当前对象name和另一个对象name的compateTo结果。
		}
		return this.name.compareTo(o.name);//返回值整数  靠后  返回值负数  靠前
	}
	public String getName(){
		return this.name;
	}
	public String getTestNum(){
		return this.TestNum;
	}
}

六、Map集合————HashMap类

map 映射通过某一个key可以直接定位到一个value值。
存储的方式以键值对存储 key-value。
key无序无重复，value无序可重复。
key无序还是一样，指的是存入顺序与取得顺序不一致。
key无重复当然指的是元素不能一致。
map基本使用：HashMap、TreeMap、properties。

1.包 java.util。HashMap初始16个，扩容因子0.75。
特点：（数组+链表）底层散列表形式存储 key无序无重复 value无序可重复。
找寻某一个唯一元素的时候建议建议使用map，更适合于查找唯一元素。
2.如何创建对象：构造方法创建对象，无参数，带默认容量的，带map参数的构造方法。
3.基本方法
增删改查
增：put(key,value); 存放一组映射关系 key-value
1.key存储的顺序与取得顺序不同；
2.不同的key可以存储相同的value；
3.key若有相同的，则将原有的value覆盖而不是拒绝存入（跟set刚好相反）。
删：E=remove(key);
改：put(key,value1); put(key,value2);
replace(key,newValue);—>put();map集合第二次存储相同的key 则会覆盖之前的value。
查：E=get(key);

遍历：map集合？key不一定什么样。
获取到所有的key，遍历key，通过key获取value。
Set<Key>=keySet();获取全部的key。
Set<Entry>=entrySet();获取全部的entry(Node)对象。
size();
--------------------------------------------------------------------------------
putAll  clear   containsKey   containsValue   isEmpty
E value=getOrDefault(key,defaultValue);若key存在就返回value 若不存在则返回defaultValue。
putIfAbsent(key,value);key若不存在就存入，若存在就放弃。

package testmap;
import java.util.HashMap;
public class TestHashMap{
	public static void main(String[] args){
		//创建一个HashMap对象
		HashMap<Integer,String>  map=new HashMap<Integer,String>();
		//将一些key-value的映射关系存入集合
		map.put(2,"bbb");
		map.put(5,"eee");
		map.put(6,"aaa");//key不同  value与1相同
		map.put(4,"ddd");
		map.put(3,"ccc");
		map.put(5,"xxx");//key相同   value与之前的5不同
		map.put(1,"aaa");
		
		Set<Map.Entry<Integer,String>>  entrys=map.entrySet();//获取集合中全部的entry对象
		Iterator<Entry<Integer,String>>  it=entrys.iterator();
		while(it.hasNext()){
			Entry<Integer,String> entry=it.next();//entry  key  value
			Integer key=entry.getKey();
			String value=entry.getValue();
			System.out.println(key+"--"+value);
		}
		
		//map.putIfAbsent(20,"yyy");
		//System.out.println(map);
		System.out.println(map.gerOrDefault(10,"1000"));
		
		//获取map集合的全部key
		Set<Integer>  keys=map.keySet();
		//通过迭代器遍历keys
		Iterator<Integer>  it=keys.iterator();
		while(it.hasNext()){
			Integer key=it.next();
			String value=map.get(key);
			System.out.println(key+"---"+value);
		}
		//System.out.println(map);
		//map.remove(3);
		//System.out.println(map);
	}
}

4.除了上述几个常用的方法外，其它API中提供的方法
clear(); containsKey(key); containsValue(value);
getOrDefault(key,defaultValue);如果key存在就返回对应的value，若没有找到则返回默认值。
isEmpty();
putAll(map);
putIfAbsent(key,value);//如果key不存在才向集合内添加，如果key存在就不添加啦
5.map集合在什么情形下用？
1.想要存储一组元素：数组 or 集合
如果存储的元素以后长度不变用数组，如果长度以后不确定，用集合。
2.如果发现长度以后不确定—>集合
List Set Map
List家族有序的，存储有顺序用这个
ArrayList 更适合遍历轮询
LinkedList 更适合插入和删除
Stack LIFO
Set家族无重复，存储元素希望自动去掉重复元素用这个
Hash 性能更高
Tree 希望存进入的元素自动去重复，同时还能自动排序
Map家族k——v，通过唯一的k快速找寻v用这个
Hash 性能更高
Tree 希望存进去的元素key自动排序
6.登录小流程
能体会每一个不同集合的特点。

package testmap;

public class LoginService{
	//设计一个方法  用来登录认证  一堆数组
	public String logingForArray(String name,String password){
		private  String[]  userBox=new String[]{"某某某","某某某某某","java"};
		private  int[]  passwordBox=new  int[]{123,666,888};
		for(int i=0;i<userBox.length;i++){
			if(userBox[i].equals(name)){
				if(passwordBox[i]==Integer.parseInt(password)){
					return "登录成功";
				}
				break；
			}
		}
		return "用户名或密码错误";
	}

	//设计一个方法  用来登录认证————ArrayList
	private ArrayList<String>  userBox=new ArrayList<String>();
	{
		userBox.add("某某某-123");
		userBox.add("某某某某某-666");
		userBox.add("java-888");
	}
	public String loginForList(String name,String password){
		for(int i=0;i<userBox.size();i++){
			String[] value=userBox.get(i).split("-");//一个人的信息  v[0]  v[1]
			if(value[0].equals(name)){
				if(value[1].equals(password)){
					return "登录成功";
				}
				break;
			}
		}
		return "用户名或密码错误"；
	}

	//设计一个方法  用来登录认证————set
	private HashSet<String>  userBox=new HashSet<String>();
	{
		userBox.add("某某某-123");
		userBox.add("某某某某某-666");
		userBox.add("java-888");
	}
	public String loginForSet(String name,String password){
		Iterator<String> it=userBox.iterator();
		while(it.hasNext()){
			String[] value=it.next().split("-");
			if(value[0].equals(name)){
				if(value[1].equals(password)){
					return "登录成功";
				}
				break;
			}
		}
		return "用户名或密码错误";
	}

	//设计一个方法  用来登录认证————map   name(唯一)  pass
	private HashMap<String,Integer>  userBox=new HashMap<String,Integer>();
	{
		userBox.put("某某某",123);
		userBox.put("某某某某某"，666);
		userBox.put("java",888);
	}
	public String loginForMap(String name,String password){
		Integer  realPassword =userBox.get(name);//null
		if(realPassword!=null && realPassword.equals(Integer.parseInt(password))){
			return "登录成功";
		}
		return "用户名或密码错误";
	}
}

7.HashMap底层的数据结构存储
散列表的形式数组+链表
Person对象存入HasMap中？可以
hashCode方法----->不同的对象可以产生相同的hashCode码的
不同的hashCode码---->不同的对象

七、Map集合————TreeMap类

TreeMap 自然有序，按照Unicode编码自然有序。

1.java.util包。
2.构造方法：无参数，带map参数。
3.常用方法：put get remove replace size
4.底层数据结构的存储
红黑二叉树

package  testmap;
public class TestTreeMap{
	public static void main(String[]  args){
		TreeMap<Integer,String> map=new TreeMap<Integer,String>();
		map.put(5,"e");//map集合中的key需要可比较的  key的对象需要实现Comparable接口
		map.put(2,"b");
		map.put(3,"c");
		map.put(7,"g");
		map.put(1,"a");
		map.put(8,"h");
		map.put(9,"a");
		map.put(4,"d");
		System.out.println(map);
	}
}

码农公寓