算法与数据结构|java之初识集合框架数据结构|java

初识集合什么叫集合框架所谓集合就是指java中已经写好的数据结构，而框架则指的是各种数据结构的一种相互关系。
所谓数据结构就是用以描述和组织数据
java中的集合框架：java Collection Framework,又称为container,是定义在**java.util包下的一组接口（interfaces）和其具体实现类（classes）**比如下图：

文章图片

对集合的一些基本认识

实现了Iterable接口的类可以使用for-each进行遍历
实现List接口的多为一线线性结构：如顺序表和链表
之所以出现队列接口：Queue，而不将其包含在List当中，是因为Queue当中包含了非线性结构，如PriorityQueue（优先级队列）
实现Set接口的集合中元素不可以重复，其次我们需要知道接口SortedSet实现了Set接口，针对SortedSet，其会被TreeSet具体去实现，HashSet直接实现了Set接口，两者的区别就是：HashSet无序，而TreeSet有序。
Map接口的实现去Set类似，它也有SortedMap接口实现了Map接口，而TreeMap具体实现了SortedMap，HashMap具体实现了Map

文章图片

对集合框架的简单熟悉和使用（其实就是学会使用底层已经编写好的数据结构就可以啦）先简单介绍一个泛型的知识?

当我们“申请”一个数据结构（集合）时：如申请一个顺序表，我们之前所学习的都是简单的放一些整型数据进去，其实底层实现的顺序表是可以放任意类型的数据的。那此时我们就想采取一种手段去完成以下目的：
可不可以实现一个顺序表，在这个顺序表中放的元素类型可以由我们指定？（先了解这一个目的，往后看还有别的目的）
上代码

public class TestDemo { public static void main(String[] args) { Collection collection=new ArrayList<>(); collection.add("hehe"); collection.add("嘻嘻"); //写collection.add(10); 就会当场报错，因为10是Integer，与String冲突 System.out.println(collection); collection.clear(); //清空顺序表 } } //打印结果 //[hehe, 嘻嘻]

这里有一个疑问：打印集合collection时，为什么就可以打印出[hehe,嘻嘻]呢？
之前的学习我们有了解到：println进行打印一个引用时：会调用这个引用所对应的toString（）,那我们知道Object是所有类的父类，并且呢，Object类中有toString（）,那此时printltn会调用哪个toString（）,得看此时的具体实现类里有没有对Collection里的toString()进行重写！若有重写，则发生动态绑定，调用具体实现类里的toString()，好的，去找找：(可能会在具体实现类里找不到toString()，那就顺着ArrayList类的一层层父类去寻找toString())果不其然，我们在AbstractCollection中找到了：

public String toString() { Iterator it = iterator(); if (! it.hasNext()) return "[]"; StringBuilder sb = new StringBuilder(); sb.append('['); for (; ; ) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); } }

从中我们可以看出：打印一个引用时：其结果是：[]括在最外面，里面的元素一个个的都是用逗号隔开，这里要说一下：元素具体怎么打印取决于这个元素的打印方式，刚才我们的”呵呵“和”嘻嘻“都是字符串，打印字符串都是原模原样的打印出来，综述：println（collection）打印出的结果就是：[hehe,嘻嘻]；否则元素的打印方式取决于元素（对应类）里有没有重写toString()。
collection常用方法?? 代码中去看：

public class TestDemo { public static void main(String[] args) { Collection collection=new ArrayList<>(); collection.add("hehe"); boolean ret1=collection.isEmpty(); //判断顺序表是否为空 System.out.println(ret1); System.out.println("====================================="); Object[] objects=collection.toArray(); //将顺序表变为一个Object数组 System.out.println(Arrays.toString(objects)); } }

注意上述的一个及其容易出错的地方： collection.toArray(),返回值类型是Object[],如果写成：

String[] ret1=(String[])collection.toArray();

编译是可以通过的，但是运行会报错：java.lang.ClassCastException
究其本质是：String[]和Object[]属于同级的数组类型，即使用String[]将Object[]进行强转，也无法改变后者的每个元素依然是Object的事实。不建议数组类型的整体转换
Map接口

常用方法：

V get(Object k)	根据k返回对应的V
V getOrDefault(Object k,V defauktValue)	根据K返回对应的V，如果没有此K，则返回默认值
V put(K key,V value)	将指定的键值对放入Map
boolean containskey(Object key)	判断是否包含key
boolean containsValue(Object value)	判断是否包含value
set> entrySet()	将所有键值对返回
boolean isEmpty()	判断是否为空
int size()	返回键值对的数量

具体使用

public class TestDemo { public static void main(String[] args) { Map map=new HashMap<>(); //要实例化具体的实现类，接口不可以实例化 map.put("豹子头","林冲"); map.put("大威天龙","法海"); String value=https://www.it610.com/article/map.get("豹子头"); System.out.println(value); String value1=map.getOrDefault("及时雨","默认的宋江"); System.out.println(value1); } }

针对：entrySet():

public class TestDemo { public static void main(String[] args) { Map map=new HashMap<>(); //要实例化具体的实现类，接口不可以实例化 map.put("豹子头","林冲"); map.put("大威天龙","法海"); Set> ret=map.entrySet(); //可以将Map.Entry视作一种类型 for (Map.Entry entry:ret) { System.out.println("key="+entry.getKey()+",value="https://www.it610.com/article/+entry.getValue()); } } } //注释： //map.entrySet(),将会把map引用的对象中的一个个键值对“打包”,每个键值对的类型为：Map.Entry，一个个的键值对依次放到Set当中，Set被ret引用。

如果直接打印一个map会是什么结果？

public class TestDemo { public static void main(String[] args) { Map map=new HashMap<>(); //要实例化具体的实现类，接口不可以实例化 map.put("豹子头","林冲"); map.put("大威天龙","法海"); System.out.println(map); } } //打印结果：{豹子头=林冲, 大威天龙=法海} //HashMap中重写的toString(): //public final String toString() { return key + "=" + value; }

原因：HashMap类中对Object的toString()进行了重写。
调换上述两个键值对再打印回事什么结果？

public class TestDemo { public static void main(String[] args) { Map map=new HashMap<>(); //要实例化具体的实现类，接口不可以实例化 map.put("大威天龙","法海"); map.put("豹子头","林冲"); System.out.println(map); } } //打印结果：{豹子头=林冲, 大威天龙=法海}

发现和没调换顺序时的打印结果一模一样！
究其本质：map底层用哈希表进行存储键值对，哈希表之前的博文也有所提及，它进行存储时，要先根据映射函数去存储到指定的位置，所以说：无论我们的键值对在程序中的先后顺序怎么去摆，它们都“注定”会放到指定的位置上，所以上述两次打印方式相同。
泛型（基础）

给出顺序表（仅存放int类型数据）的情况：

public class MyArrayList { public int[] elem; public int usedSize; public MyArrayList() { this.elem = new int[10]; //顺序表容量初始化为10 }public void add(int data){ if(isFull()){ this.elem= Arrays.copyOf(this.elem,2*this.elem.length); //2倍扩容 } this.elem[this.usedSize]=data; //尾插一个元素 } private boolean isFull(){ return this.usedSize==this.elem.length; } private boolean isEmpty(){ return this.usedSize==0; }//获取pos位置处的元素 public int getPos(int pos){ if(isEmpty()){ System.out.println("顺序表为空！"); return -1; } if(pos<0||pos>=this.usedSize){ System.out.println("下标不合法！"); return -1; } return this.elem[pos]; } }

上述代码局限于存放int类型的数据，我们的想法是想放什么类型的数据，就放什么类型的数据！
很简单，我们将上述代码的int（指定元素类型的int）都改成Object，不就可以解决了吗。如：

public class MyArrayList { public Object[] elem; public int usedSize; public MyArrayList() { this.elem = new Object[10]; //顺序表容量初始化为10 }public void add(Object data){ if(isFull()){ this.elem= Arrays.copyOf(this.elem,2*this.elem.length); //2倍扩容 } this.elem[this.usedSize]=data; //尾插一个元素 } private boolean isFull(){ return this.usedSize==this.elem.length; } private boolean isEmpty(){ return this.usedSize==0; }//获取pos位置处的元素 public Object getPos(int pos){ if(isEmpty()){ System.out.println("顺序表为空！"); return null; } if(pos<0||pos>=this.usedSize){ System.out.println("下标不合法！"); return null; } return this.elem[pos]; } }

对上述代码进行使用：

public class TestDemo { public static void main(String[] args) { MyArrayList myArrayList=new MyArrayList(); myArrayList.add("hehe"); myArrayList.add(10); String ret=(String)myArrayList.getPos(0); System.out.println(ret); } }//该代码特点： 1、什么类型都能放 2、获取元素还要做强转

为了让类型参数化（我们可以指定放什么类型的元素）和免去强制类型转换的步骤：引入泛型：
直接看代码：

public class MyArrayList {//注意点1 public E[] elem; //注意点2 public int usedSize; public MyArrayList() { this.elem = (E[])new Object[10]; //顺序表容量初始化为10（这里最好用反射去写）注意点3 }public void add(E data){//注意点4 if(isFull()){ this.elem= Arrays.copyOf(this.elem,2*this.elem.length); //2倍扩容 } this.elem[this.usedSize]=data; //尾插一个元素 } private boolean isFull(){ return this.usedSize==this.elem.length; } private boolean isEmpty(){ return this.usedSize==0; }//获取pos位置处的元素 public E getPos(int pos){//注意点5 if(isEmpty()){ System.out.println("顺序表为空！"); return null; } if(pos<0||pos>=this.usedSize){ System.out.println("下标不合法！"); return null; } return this.elem[pos]; } }

上述5个注意点，就是我们修改的地方，进而使这个顺序表变成一个泛型类。
使用：

public class TestDemo { public static void main(String[] args) { MyArrayList myArrayList=new MyArrayList<>(); myArrayList.add("hehe"); myArrayList.add("xixi"); MyArrayList myArrayList1=new MyArrayList<>(); myArrayList1.add(10); myArrayList1.add(20); int a=myArrayList1.getPos(0); //这里没进行强制类型转换（Object->int） System.out.println(a); //打印10 } }//类型得以参数化

如果将上述的MyArrayList进行打印：MyArrayList@1b6d3586 这显然就是Object的toString()。但重点是：并没有出现在类名的组成上。记住这一结论：泛型不参与类名的组成。
一个面试问题：泛型如何编译？
泛型是编译时期的一种机制，擦除机制
【算法与数据结构|java之初识集合框架】编译期起到类型检查的功能，只要我们指定的类型（包装类）写好了，那这个泛型类实例化的对象里就只能放你指定的对应的数据类型的数据了。如果放的不是这个类型的数据，编译器当场报错（你都还没run呢）.这就叫编译期的类型检查。其次编译结束后，我们指定的E，在泛型类里会都被替换成Object,而主函数中调用泛型类时写的被擦的干干净净。这就是擦除机制。有人会问强制类型转换在哪？究其本质是编译器在调用泛型类里的方法结束（给返回值的时候）自动为我们做了强制类型转换（因为擦除机制，E变成了Object,所以底层作的强制类型转换就是：将Object转成了我们指定的那个类型）。
总结