Set|集合

一.容器类
1.1定义
容器其实就是一种用来存储数据的数据结构,在java中容器可以分为集合(Collection)和映射(Map)。至于为什么需要容器,总的来说主要是在艺术组作为数据的存储结构中,其长度难以扩充,同时数组中的元素的类型必须相同,而容器类就可以弥补数组的这两个缺陷。
1.2容器类的特点
1)容量可以动态的改变,并且可以根据size()方法来获取容器类中有效元素的个数。
2)容器类中只能存放对象,如果存放的是基本数据类型,会自动进行装箱操作转换为对象的包装类。
3)容器类存放的是对象的引用,对象的本身还是在堆内存中。
4)如果没有规定泛型结构的话,一个容器类可以存放不同类型的对象,即使规定了泛型也可以通过反射机制来向容器中添加其他类型的元素。
5)有多重实现方式和不同的适用场合,以类的形式存在,具有封装、继承、多态等类的特点,可以通过简单的方法和属性实现各种复杂的操作,提高了开发效率。
1.3容器类的继承体系
Set|集合
文章图片

图1.容器类的继承体系
从图中可以看出,Collection是所有容器集合的父接口,list,Set,是Collection的子接口。其中 List是可重复集合,类似于动态数组,长度是动态改变的,存储的元素是有序的,表示的是一个有序的Collection接口,Set是不可重复集合,存储的内容是没有顺序,是一个不包含重复元素的Collection接口,只能存放一个null。LinkedList相当于数据结构中的线性结构中的链式存储结构,ArrayList相当于顺序存储结构,分别实现了Set和List接口。
【Set|集合】二.Iterator(迭代器)接口
2.1定义
Iterator是所有集合和映射的父接口,通过调用迭代器中的iterator()方法来获取一个迭代器对象,但是本身不具备承载对象的能力,通过集合的操作来获取遍历集合的指针,hashNext()方法用于判断集合中的下一个元素是否为null,next()方法主要作用就是用于游标的移动,并且返回当前游标元素的值,此处的游标就相当于链表的头结点。
2.2使用迭代器遍历集合的操作
1)正确的遍历方式

//迭代器遍历 Iterator iters=c.iterator(); while(iters.hasNext()) { //next方法的两个作用:1.游标向下移动2.返回移动之后游标位置的元素 System.out.println(iters.next()); }/

2)错误实例1

迭代器使用过程中的错误用例1 while(c.iterator().hasNext()) { System.out.println(c.iterator().next()); }

这段代码发生的原因就是每一次都会创建一个Iterator对象,每次输出的都是第一个元素,会发生死循环。
3)错误示例2
错误用例2 while(iters.next()!=null) { //会出现跨越式输出,还会出现NoSuchElementsException System.out.println(iters.next()); }

这段代码错误的原因就是会进行跳跃式输出。
三.List接口
3.1 定义
1)位于java.util.List包中,该接口继承了Collection接口,主要实现类是ArrayList、LinkedList、Vector,List接口是一个有序的可重复集合,属于单列集合。
2)ArrayList的底层是一个Object数组有序有下标,底层数组的默认长度是10,如果添加元素的长度超过10的话数组会进行扩容,长度变为原来的1.5倍,线程是不安全的,相对于其他的实现类来说查询速度快;LinkedList的底层实现是数组+双向链表实现的,通过Node节点来实现,包含三部分,前驱指针,数据,后继指针,相对于其它的实现类,对于频繁的插入和删除速度快,使用双向链表主要是可以提高平均访问效率;Vector是集合中的元老,线程是安全的,但是在目前的实际开发过程中已经很少使用。
3)不能创建实例,但是可以通过多态来使用。
3.2 List集合中常用的方法
Set|集合
文章图片

图2.List中常用的方法
代码实现:
@Test public void test() { //如果可以知道要添加的数据量的时候 //尽量不要使用空的构造方法 List list=new ArrayList(); //添加元素 list.add("one"); list.add("two"); list.add("three"); list.add("foue"); //判断当前集合是否包含指定的元素 boolean b= list.contains("one"); System.out.println(b); //获取元素 Object o=list.get(0); System.out.println(o); //移除指定位置的元素 Object o1=list.remove(0); System.out.println(o1); //修改指定位置的元素 list.set(1, "yi"); // System.out.println(list); } public static void main(String[] args) { List list=new ArrayList(); for(int i=0; i<10; i++) { list.add(i); } System.out.println(list); //获取3-7 List list1=list.subList(3, 8); System.out.println(list1); for(int i=0; i

3.3 将List集合转换为数组
List的toArray方法用于将集合转换为数组。但是实际上该方法是在Collection中定义的,所以所以集合都具备这个功能。其中有两个方法:Object[]toArray() T[] toArray(T[] a)
其中第二个方法是比较常用的,我们可以传入一个指定类型的数组,该数组的元素类型与集合的元素类型一致。返回值则是转换后的数组,该数组保存集合中的所有元素。若给定的数组可用,即数组可以存放集合中元素的时候,则使用该数组,如果不可用,会自动创建一个与给定的数组同类型的数组。
代码示例:
public static void main(String[] args) { Collection c=new ArrayList(); c.add("one"); c.add("two"); c.add("three"); c.add("four"); /* * 集合提供了一个方法toArray,可以将当前集合转换为组 */ String []array=c.toArray(new String[c.size()]); System.out.println(array.length); for(String str:array) { System.out.println(str); }

3.4 将数组转换为集合
需要注意,只能转换为List集合,使用的是数组的工具类Arrays的静态方法asList,只能转换为List集合,主要原因就是Set集合不能存放重复元素,所以如果转换为Set集合可能会发生元素丢失的情况,当将一个数组转换为集合的时候不允许向该集合中添加元素,原因在于,该集合是由数组转换过来的,那么该集合就表示的是原始的数组,所以对集合的操作就是对原来数组的操作。如果添加元素就会导致数组的扩容,扩容之后的数组就不能表示原来的数组,所以不允许向集合中添加元素。
代码演示:
String [] array= {"one","two","three","four","five"}; /* * */ List list=Arrays.asList(array); System.out.println(list);

3.5 LinkedList集合中特有的方法
@Test public void testLinkedList() { LinkedList list=new LinkedList(); list.add("sss"); list.add(123); list.addFirst("345"); list.addLast("456"); System.out.println(list); Object first=list.getFirst(); System.out.println(first); Object last=list.getLast(); System.out.println(last); list.removeFirst(); list.removeLast(); System.out.println(list); }

addFirst方法用来向头部添加一个元素,addLast方法用来向尾部添加一个元素,getFirst方法用来获取LinkedList的头部,getLast方法用来获取LinkedList的尾部,removeFirst方法用来移除LinkedList的头部,removeLast方法用来移除LinkedList的尾部。
四.Set接口
4.1定义
1)Set集合是一个无序的Collection集合,不能存放重复的元素类似于数学中的集合,具有交叉并补等这样的方法,是一个接口不能创建实例,只能通过创建子类的对来来进行构造。实现类是HashSet和TreeSet。
2)HashSet底层是一个哈希表,具有Set集合的特点,是一个不可重复集合,其底层的哈希表的实现采用了一种散列算法,该算法是通过某种公式进行快速的运算来进行数据的查找,但是会消耗一定的空间,影响该算法效率的有三个因素:桶(每一个容量就是一个桶)、容量(哈希表中桶的数量默认是11,添加元素的时候如果超出容量的话,会进行整体扩容,即哈希表的长度将变为原来的2倍)、加载因子(默认是0.75,加载因子越高,空间的开销可以减少但是会增加运算的时间)。
3)TreeSet底层是一个倒挂的二叉树,由于TreeSet是Set的实现类,因此Set有的特点TreeSet也具有,不允许存放重复的元素,但是添加到TreeSet里面的元素应该可以排序。TreeSet中添加元素的顺序:添加的元素首先和根元素进行比较,如果比根元素大,就在根元素的右边添加元素,如果比根元素小,就在根元素的左边添加元素。如果添加的是引用类型的数据,就必须实现Comepareable接口并重写Comapareto()方法,如果没有重写该方法就会发生异常,该方法的返回值是一个整数,返回值如果大于0,则表示当前对象大于传进来的参数,如果等于0则表示当前对象等于传进来的值,如果小于0则表示当前值小于传进来的值。
4.2 HashSet的增删改查
增:HashSet类中提供的boolean add()方法主要用来向集合中添加元素,当添加重复元素的时候,add方法的返回值就是false。重复元素和变量的地址无关,是由hashCode和equals方法同时决定的,如果两个元素的哈希值相等只能说明二者在底层的哈希表中的位置相同,如果equals方法的比较结果为真的情况下,才能说明二者是同样的元素,这也就是说hsahCode相同的情况下,equals不一定为true,如果equals为true的话,hashCode的值一定时相同的,如果Set集合中添加的元素是自定义数据类型的话那么该引用数据类型必须重写Object类当中的hashCode和equals方法。
private String a; public Person(String a) { this.a=a; } public String getA() { return a; } public void setA(String a) { this.a = a; } @Override public String toString() { return a; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((a == null) ? 0 : a.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; Person other = (Person) obj; if (a == null) { if (other.a != null) return false; } else if (!a.equals(other.a)) return false; return true; }

向Set集合中添加元素
set1.add(new Person("10")); set1.add(new Person("10")); //set1.add(new Person("11")); //set1.add(new Person("12")); //set1.add(new Person("13")); //set1.add(new Person("14")); //set1.add(new Person("15")); Iterator iter=set1.iterator(); while(iter.hasNext()) { System.out.println(iter.next()); }//不重写输出哈希值和equals System.out.println(new Person("10").hashCode()); System.out.println(new Person("10").hashCode()); System.out.println(new Person("10").equals(new Person("10"))); System.out.println(set1);

删:使用remove方法可以进行元素的删除
改:由于Set结构没有索引,没有set方法,因此set集合不存在对元素修改的方法。
查:由于Set集合没有索引,不能通过下标来访问,对Set集合的遍历使用迭代器来操作,首先通过集合调用Iterator()获取操作这个集合的指针,然后通过访问下一个来对集合进行遍历。
Iterator iter=set1.iterator(); while(iter.hasNext()) { System.out.println(iter.next()); }

五.Map集合
5.1定义
Map属于双列集合,和Collection集合并列,存储结构为key-àvalue,是一个无序的集合,其中key是不可以重复的,Value的值是可以重复的。Map中的所有Key值组成了一个Set集合,因此Key值是唯一的,所有的Value构成了一个Collection集合,值不是唯一的,可以添加null值。在HashMap中Key和Value的都可以为null,其中Key和Value的值是一一对应的,主要实现类是:HashMap、TreeMap、LinkedMap、Proerties(HashMap使用频率最高),在实际的开发过程中Key的类型一般为String,因为String类型使用关键字final修饰,不可逆。
5.2Map各个实现类的类比
1)HashMap:键值Key只允许有一条null记录,Value值可以有多条null记录,HashMap是线程不安全的,但是相对于其它的实现类来说效率较高。
2)LinkedHashMap:作为HashMap的子类,可以按照添加元素的顺序进行遍历,底层实际上添加了一对指针,用来记录添加元素的前后顺序,对于频繁的插入和删除效率较高。
3) Hashtable:是一个比较古老的实现类,线程是安全的,但是实际开发中基本上不用,就像List集合中的Vector一样。
4) Properties:Hashtable的子类,常用于读取配置文件,通常Key和Value都是String类型的。
5) TreeMap:底层实现是红黑树的结构,可以按照添加key所在类的属性排序,要求添加元素必须是同一类。
5.3 Map中Key和Value的特性
Map中Value是无序的,并且可以重复,其中一个Key和一个Value组成了一个Entry,Entry是一个内部接口用于描述Key和Value的映射关系,Map集合中提供的entrySet方法可以获取Map集合汇总所有的映射关系,其中Entry中封装的getKey和getValue方法可以获取对应的键值对的值。所有的Key值组成一个Set集合,根据Set集合的特点我们可以知道Key值是唯一的,所有的Value组成一个Collecton集合,因此Value的值是可以重复的,其中Map集合和Collection集合是并列的关系。
5.4Map集合的底层实现原理
在java的JDK1.7之前,Map集合的主要实现类HashMap的底层使用数组+链表的方法进行存储。但是在java的JDK1.7中HashMap主要使用数组+链表+红黑树进行存储。我们一HashMap中添加元素的方法来说明底层的实现原理,刚开始当我们向集合中添加元素的时候,首先程序会通过添加元素所在类的HashCode方法获取的哈希值来计算元素在底层数组中的具体的存储位置,如果此位置上没有元素那么程序将会将这个元素添加到底层数组中的相应位置。如果通过计算,得到在底层数组的相对应的位置上已经有了元素,则需要使用equals 方法进行比较,如果equals返回的是false,则添加的元素在底层数组中不存在,在此位置上使用链表结构进行存储,如果equals返回的true说明key值有重复,则使用新的value值替换原来的value的值。其中刚开始的时候底层数组的默认长度为16。在添加的过程中会涉及几种机制:如果底层数组的长度超过了12(刚开始的默认长度*加载因子),那么底层数组会进行扩容,在这个过程中如果链表的长度超过8,数组的长度超过64,底层的存储结构将会向红黑树进行转换。目的就是提高数据的访问效率。
5.5Map中常用的方法
@Test public void test() { Map map=new HashMap(); //添加元素 map.put(123, "中国加油!"); map.put(new Person(1,"哈哈"), 123); System.out.println("添加集合:"+map); //删除 //通过指定的键值对移除相对应的元素 map.remove(123); System.out.println("移除之后:"+map); //清空 //map.clear(); //查询 //通过指定的Key来获取对应的value值 Object object=map.get(123); System.out.println("指定的key:"+object); //查询当前map中是否包含指定的一个Key值 boolean con=map.containsKey(123); System.out.println("包含指定的key:"+con); //查询当前map中是否包含指定的一个Value值 boolean cons=map.containsValue(123); System.out.println("包含指定的value:"+cons); //返回当前集合中key--value的个数 int size=map.size(); System.out.println(size); //判断当前集合是否为空 boolean empty=map.isEmpty(); System.out.println(empty); //equals用于比较两个map集合是否相同 map.equals(new HashMap());

注意:有序性是存和取的顺序是一致的,无序性不同于随机性,其具体的实现是通过添加元素的哈希值然后通过某种算法计算添加在底层数组中的一个实际位置;Set集合的不可重复性是通过重写HashCode和equals方法来判断的,缺一不可,equals如果相同的话,其HashCode值一定相同,但是反过来来说,对于HashCode值相同的情况,equals方法的返回值不一定是true。Set集合是一个无序集合但是我们可以使用TreeSet提供的有参的构造方法,可以将一个Set集合转换为一个有序的集合。
六.排序
6.1定义
分为自然排序,和定制排序,如果集合中添加的元素是自定义数据类型的话,为了使其可以排序,在自定义的类中当向集合中添加元素的时候需要重写,Compareable接口中的compareto方法,否则会发生类型转换异常。排序的只要方法有两种一种是实现Compareable接口重写compareto方法,另一种是使用TreeMap中的有参构造方法,使用Comparator的匿名实现类来实现。
6.2实现Compareable接口重写compareto方法
@Test public void testTreeMap() { //自然排序 //按照添加key元素所在类的特定属性进行排序 TreeMaptreemap=new TreeMap(); treemap.put(new Person(20,"Tom"), 456); treemap.put(new Person(30,"肉丝"), 234); treemap.put(new Person(23,"李梅"), 789); System.out.println(treemap); } //定制排序其 @Test public void testTreeMapSort() { Comparator com= new Comparator() {@Override public int compare(Object o1, Object o2) { if(o1 instanceof Person&&o2 instanceof Person) { Person p1=(Person)o1; Person p2=(Person)o2; int compare= Integer.compare(p1.getAge(), p2.getAge()); if(compare==0) { return p1.getName().compareTo(p2.getName()); }else { return compare; } } return 0; } }; TreeMaptreemap=new TreeMap(com); treemap.put(new Person(20,"Tom"), 456); treemap.put(new Person(30,"肉丝"), 234); treemap.put(new Person(20,"李梅"), 789); System.out.println(treemap); } package JiHEXu; public class Person implements Comparable{ int age; String name; public Person(int age, String name) { super(); this.age = age; this.name = name; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + age; 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; Person other = (Person) obj; if (age != other.age) 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 "Person [age=" + age + ", name=" + name + "]"; } @Override public int compareTo(Object o) { if(!(o instanceof Person)) { throw new RuntimeException("类型不匹配"); }else { Person p=(Person)o; int compare= Integer.compare(this.age, p.age); if(compare !=0) { return compare; }else { return this.name.compareTo(p.name); } } } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } }

6.3定制排序

package day05; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; public class SortListDemo02 { public static void main(String[] args) { List list=new ArrayList(); list.add("小泽老师"); list.add("孙老师"); list.add("魏老师"); MyCompareator com=new MyCompareator(); Collections.sort(list, com); System.out.println(list); }} class MyCompareator implements Comparator{ /* * 比较规则,字符多的大 */ @Override public int compare(String o1, String o2) { //从小到大的顺序 return o1.length()-o2.length(); } }

注意:重载的sort()方法要求传入一个额外的比较器,该方法不要求集合必须实现compareable接口,并且也不再使用集合元素自身的比较规则排序,而是根据这个额外的比较器的比较规则对集合元素进行排序,实际开发中推荐使用这种方式排序集合元素,若集合元素是自身定义的创建比较器的时候推荐使用匿名内部类的形式。



    推荐阅读