java中的集合之Set接口(三)

曾经终败给现在 2022-08-18 10:59 175阅读 0赞

**Set接口**

没有扩展自己的方法，与Collection中的方法完全一致。

– HashSet

• 此类实现 Set 接口，由哈希表（实际上是一个HashMap 实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。

• 此实现不是同步的，想实现同步，需要使用Set s = Collections.synchronizedSet(new HashSet(...));

– TreeSet

• 使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的Comparator 进行排序。

**Set接口实现类**

**HashSet类**

– 此类不是同步的。

– 底层是由数组实现。且使用了哈希算法进行存储。

– 当一个对象存入HashSet集合对象中时，会先比较hashCode值，如果hashCode值不同，则直接存入集合；如果hashCode值相同，再使用equals方法比较对象，如果为true则不添加；如果为false，则添加到该集合对象中。也就是说，hashcode值相同，则equals未必相同，equals相同的两个对象，hashcode值一定相同。

– 原理：

• 当将一个对象存放入HashSet集合对象中时，会根据hashCode%n，得到数组的下标位置。数组中，如果该位置已经有元素，则根据equals方法，比较两个对象。如果返回为true，则该对象不添加到数组中。如果返回为false，则该数组位置上的元素以链表的形式存放，新加入的对象放在链表头，最先加入的元素放在链表尾。如果数组中，该位置没有元素，则直接将元素放到该位置。

学生类

package com.jcxy.demo13;
    
    public class Student
    {
        private int age;
        private String name;
        
        @Override
        public String toString()
        {
            return "age = " + age +"\tname = " + name;
        }
        //自动生成hashcode和equals方法，快捷键alt+shift+s ，谈出界面后按h     
        @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;
        }
    
        public Student(int age, String name)
        {
            super();
            this.age = age;
            this.name = name;
        }
        @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 (name == null)
            {
                if (other.name != null)
                    return false;
            }
            else if (!name.equals(other.name))
                return false;
            return true;
        }
        
        public int getAge()
        {
            return age;
        }
        
        public void setAge(int age)
        {
            this.age = age;
        }
        
    }

MySet类

package com.jcxy.demo13;
    
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class MySet
    {
        public LinkedList[] lls = new LinkedList[8];
        
        public MySet(){}
        
        public boolean add(Object obj)
        {
            int hashcode = obj.hashCode();
            //对lls.length取余的范围在[0,lls.length-1]
            int index = hashcode % lls.length;
            // 第一次向数组中存放元素。
            if (lls[index] == null)
            {
                //开辟新的内存空间存放集合
                lls[index] = new LinkedList();
                lls[index].addFirst(obj);
                return true;
            }
            else
            // 从第二次赋值开始
            {
                // 用obj对象使用equals方法与lls[index]表示的集合对象中每个元素比较属性值是否相同
                if (lls[index].contains(obj))
                {
                    return false;
                }
                //不相同则添加元素
                lls[index].addFirst(obj);
                return true;
            }     
        } 
    }

Test类

package com.jcxy.demo13;
    
    import java.util.Iterator;
    
    public class Test
    {
        public static void main(String[] args)
        {
            MySet ms = new MySet();
            // 添加学生数据
            Student s1 = new Student(21, "aa");
            ms.add(s1);// 计算出index为4，将学生信息加入索引为4的LinkedList集合中
            ms.add(new Student(22, "aa"));// 计算出index为3，将学生信息加入索引为3的LinkedList集合中
            ms.add(new Student(23, "aa"));// 计算出index为2，将学生信息加入索引为2的LinkedList集合中
            ms.add(new Student(21, "ab"));// 计算出index为5，将学生信息加入索引为5的LinkedList集合中
            ms.add(new Student(21, "aaa"));// 计算出index为5，将学生信息加入索引为5的LinkedList集合中
            ms.add(new Student(23, "bbb"));// 计算出index为4，将学生信息加入索引为4的LinkedList集合中
            ms.add(new Student(24, "aaa"));// 计算出index为2，将学生信息加入索引为2的LinkedList集合中
            ms.add(new Student(21, "aa"));// 对象存在，不添加。先调用contains方法，接着调用对象自身的equals方法比较对象是否相等
            
            // 我们在添加了学生s1的信息之后修改了他的年龄
            // 而当时添加到set集合中的数据却还在集合中无引用指向，
            // 这样造成集合中的数据一直存在，无法释放
            s1.setAge(28);
            System.out.println(s1.toString());// age = 28 name = aa
            
            //同一个对象却在集合中出现了两次,显然不符合我们的插入要求，当我们频繁操作的时候，可能会造成内存溢出
            ms.add(s1);//计算出index为5，将学生信息加入索引为5的LinkedList集合中       
            
            // 显示学生数据
            for (int i = 0; i < ms.lls.length; i++)
            {
                if (ms.lls[i] == null)
                {
                    continue;
                }
                System.out.print("index = " + i + "\tsize = " + ms.lls[i].size());
                Iterator it = ms.lls[i].iterator();
                while (it.hasNext())
                {
                    Student s = (Student)it.next();
                    System.out.print("\t" + s);
                }
                System.out.println();
            }
        }
    }

注意：

在使用HashSet时，如果添加对象后，对对象的属性值进行修改了，可能会造成内存泄漏。以后使用HashSet存放数据时，尽量不要修改其中对象的属性值。

存储结构分析图

![SouthEast][]

**TreeSet类**

– 对集合中的元素，默认按照自然顺序自动排列。

– TreeSet底层使用是二叉树。

– 对于TreeSet对象来说，要求存放入其元素的类型必须具有比较性。当类实现Comparable接口，并重写compareTo方法，该类的对象具有了比较性。把这种形式叫做按照自然顺序排序。

– TreeSet对象，通过compareTo对存放入其中的元素进行排序，且也是通过该方法比较两个对象是否相同。如果相同，则不会添加到TreeSet对象中。为了更精确的表示两个对象相等，当某个属性比较为0时，必须判断其他属性是否相等，当所有属性都相等时，两个对象真正相同。

TreeSet中最主要的就是其实现了Comparable接口，可以通过这个接口来实现对象的自然顺序排序，也可以实现Comparator接口，这样可以按照我们的需求不同的比较方式，定义不同的比较器。

首先来看实现Comparable接口来比较对象是否相等。

Student

package com.jcxy.demo14;
    
    public class Student implements Comparable
    {
        private int age;
        private String name;
        public Student()
        {
            super();
            // TODO Auto-generated constructor stub
        }
        public Student(int age, String name)
        {
            super();
            this.age = age;
            this.name = 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;
        }
        @Override
        public String toString()
        {
            return "Student [age=" + age + ", name=" + name + "]";
        }
        @Override
        public int compareTo(Object o) 
        {
            if(!(o instanceof Student))
            {
                throw new RuntimeException("类型不同无法比较");
    //            throw new Exception("类型不同无法比较");不能抛出比父接口更多的异常
            }
            if( this == o)
            {
                return 0;
            }
            Student s = (Student)o;
            //定义学生的年龄为第一比较顺序
            int result = this.age - s.age;
            
            if(result != 0)
            {
                return result;
            }
            //学生的姓名为第二比较顺序
            return this.name.compareTo(s.name);
        }
    }

Test类

package com.jcxy.demo14;
    
    import java.util.Iterator;
    import java.util.TreeSet;
    
    public class Test
    {
        public static void main(String[] args)
        {
            TreeSet ts = new TreeSet();
            
            Student s1 = new Student(21,"jack");
            Student s2 = new Student(22,"rose");
            Student s3 = new Student(22,"rones");
            Student s4 = new Student(21,"mars");
            Student s5 = new Student(22,"rone");
            Student s6 = new Student(24,"lurs");
            
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
            
            Iterator it = ts.iterator();
            while(it.hasNext())
            {
                Student s = (Student)it.next();
                
                System.out.println(s);
                
            }
        }
    }

打印结果：

Student \[age=21, name=jack\]  
Student \[age=21, name=mars\]  
Student \[age=22, name=rone\]  
Student \[age=22, name=rones\]  
Student \[age=22, name=rose\]  
Student \[age=24, name=lurs\]

从结果中可以看出来，对象的排序顺序是按照年龄的递增为第一排序顺序，姓名为第二自然排序顺序。

那既然有了Comparable接口，可以进行排序，那为什么还需要Comparator比较器呢？

假如有一个项目的需求是我们需要提供多种方式来对对象进行排序，以供客户选择。显然Comparable无法做到，所以java.util包中为我们提供了这样一个接口即Comparator接口，只要实现它的compare方法就可以。

– Comparator比较器，实现对象的排序：

– 创建一个类，实现Comparator接口，重写compare()方法。

– 比较器主要用于指定对象排序的规则。

– **以后，在实际排序中，最好类先实现一个Comparable，如果有其他排序规则的话，再使用Comparator.**

修改上面的学生类，添加出生日期属性

带有自然排序的方法

package com.jcxy.demo15;
    
    import java.util.Date;
    
    public class Student implements Comparable
    {
        private int age;
        
        private String name;
        
        private Date birth;
        
        public Student()
        {
            super();
            // TODO Auto-generated constructor stub
        }
        
        public Student(int age, String name, Date birth)
        {
            super();
            this.age = age;
            this.name = name;
            this.birth = birth;
        }
        
        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;
        }
        
        public Date getBirth()
        {
            return birth;
        }
        
        public void setBirth(Date birth)
        {
            this.birth = birth;
        }
        
        @Override
        public String toString()
        {
            return "Student [age=" + age + ", name=" + name + ", birth=" + birth + "]";
        }
        
        @Override
        public int compareTo(Object o)
        {
            if (!(o instanceof Student))
            {
                throw new RuntimeException("类型不同无法比较");
                // throw new Exception("类型不同无法比较");不能抛出比父接口更多的异常
            }
            if (this == o)
            {
                return 0;
            }
            Student s = (Student)o;
            // 定义学生的年龄为第一比较顺序
            int result = this.age - s.age;
            
            if (result != 0)
            {
                return result;
            }
            // 学生的姓名为第二比较顺序
            int result1 =  this.name.compareTo(s.name);
            
            if(result1 != 0)
            {
                return result1;
            }
            //出生日期为第三排序顺序
            return this.getBirth().compareTo(s.getBirth());
        }
    }

按照姓名排序的Comparator实现类

package com.jcxy.demo15;
    
    import java.util.Comparator;
    
    public class OrderByName implements Comparator
    {
        
        @Override
        public int compare(Object o1, Object o2)
        {
            if(!(o1 instanceof Student) || !(o2 instanceof Student))
            {
                throw new RuntimeException("类型不是学生类型，无法比较");
            }
            if(o1 == o2)
            {
                return 0;
            }
            Student s1 = (Student)o1;
            Student s2 = (Student)o2;
            
            //按照姓名为第一排序顺序
            int result = s1.getName().compareTo(s2.getName());
            if(result != 0)
            {
                return result;
            }
            
            return s1.getAge() - s2.getAge();
        }
        
    }

按照生日排序的Comparator实现类

package com.jcxy.demo15;
    
    import java.util.Comparator;
    
    public final class OrderByDate implements Comparator
    {
        @Override
        public int compare(Object o1, Object o2)
        {
            if(!(o1 instanceof Student) || !(o2 instanceof Student))
            {
                throw new RuntimeException("类型不是学生类型，无法比较");
            }
            if(o1 == o2)
            {
                return 0;
            }
            Student s1 = (Student)o1;
            Student s2 = (Student)o2;
            //按照生日为第一排序顺序
            int result = s1.getBirth().compareTo(s2.getBirth());
            if(result != 0)
            {
                return result;
            }
            //年龄为第二排序顺序
            return s1.getAge() - s2.getAge();
        }    
    }

Test类

package com.jcxy.demo15;
    
    import java.text.ParseException;
    import java.text.SimpleDateFormat;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Iterator;
    import java.util.List;
    import java.util.Set;
    import java.util.TreeSet;
    
    public class Test
    {
        /**
         * TreeSet中有一个构造函数可以传入一个构造器对象
         * 构造一个新的空 TreeSet，它根据指定比较器进行排序
         * <一句话功能简述>
         * <功能详细描述>
         * @param args
         * @throws ParseException
         * @see [类、类#方法、类#成员]
         */
        public static void main(String[] args) throws ParseException
        {
    //        Set ts = new TreeSet();//自然排序
    //        Set ts = new TreeSet(new OrderByName());//按照姓名排序
            Set ts = new TreeSet(new OrderByDate());//按照生日排序
            
            SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
            
            Student s1 = new Student(21,"jack",sdf.parse("1995-11-8"));
            Student s2 = new Student(19,"rose",sdf.parse("1999-1-18"));
            Student s3 = new Student(23,"andy",sdf.parse("1996-1-16"));
            Student s4 = new Student(20,"jack",sdf.parse("1992-5-9"));
            Student s5 = new Student(24,"dandy",sdf.parse("1991-6-26"));
            Student s6 = new Student(21,"jaco",sdf.parse("1992-11-8"));
            
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
            
            for(Object obj : ts)
            {
                System.out.println(obj);
            }  
        }
    }

通过传入TreeSet构造器中的不同的比较器对象，我们可以实现不同的排序需求。

在List集合中，我们可以用工具类Collections中的sort方法的重载形式传入我们的比较器对List集合中的对象进行比较。

**如何判断集合中的元素与某个对象是否相同？**

List体系：使用存放入该集合中对象所属类的equals方法

ArrayList/ Vector：底层可变数组， 查询快，删除和插入慢

LinkedList：底层链表，查询慢，删除和插入快

Set体系：不重复且无序

HashSet：底层哈希表（本质上数组），增删改查都比较快。

先判断hashcode值，hashcode相同，再使用equals判断。

TreeSet：底层二叉树，对存入其中的对象默认按照自然顺序排序

通过实现Comparable接口，并重写compareTo方法，此方法返回0，表示对象相同。

**Comparable与Comparator区别？**