JavaSet接口实现类（hashSet、LinkedHashSet、TreeSet），附两道常见面试题

2022-09-02 08:22:06

Collection子接口二：Set

Set接口是Collection的子接口，Set接口没有提供额外的方法，直接调用Collection的方法就可以
Set集合中不允许添加相同的元素
Set判读两个对象是否相同不是使用==运算符，而是根据equals方法
Set：元素无序、不可重复的集合
- hashSet：Set接口的主要实现类：线程不安全，可以存储null值
  - LinkedHashSet：作为HashSet的子类，遍历其内部数据时，可以按照添加的顺序遍历
- TreeSet：可以按照添加对象的指定属性，进行排序
Set无序性：不等于随机性，存储的数据在底层数组中并非按照数组索引的顺序添加，而是按照数据的哈希值决定的
Set不可重复性：保证添加的元素在按照equals()判断时，不能返回true，即：相同的元素只能添加一个
添加元素的过程：以HashSet为例
- 1.在向HashSet中添加元素a,首先调用a所在类的hashCode()方法，计算元素a的哈希值
- 2.此哈希值接着通过某种算法计算出在HashSet底层数组中的存储位置（即为索引位置），以此判断数组此位置上是否已经有元素
  - 2.1.如果此位置上没有其他元素，则直接将元素a添加到此位置上
  - 2.2.如果此位置上有其他元素b（或以链表形式存在的多个元素），则比较a与b的hash值
    - 2.2.1.如果哈希值不相同，则将元素a添加到b的下面（同一个位置，以链表的方式存储）
    - 2.2.2.如果哈希值相同，进一步调用b所在类的equals()方法
      - 2.2.2.1.equals()返回true，则两个元素相同，添加失败
      - 2.2.2.2.equals()返回false，则将元素a添加到b的下面（同一个位置，以链表的方式存储）
HashSet底层也是数组（数组+链表的结构），初始容量为16，如果使用率超过0.75（12）,就会扩大容量为原来的2倍（32,64,128…）
对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等等规则，即：相等的对象必须具有相等的散列码
对象中用作equals()方法比较的field，都应该用来计算hashCode

package www.bh.c.settest;

public class Test01 {
    private String name;
    private int age;

    public Test01() {
    }

    public Test01(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setAge(int age) {
        this.age = age;
    }
   //重写equals()
    @Override
    public boolean equals(Object o) {
        System.out.println("=================");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Test01 test01 = (Test01) o;

        if (age != test01.age) return false;
        return name != null ? name.equals(test01.name) : test01.name == null;
    }
   //重写hashCode()
    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

注：为什么以上重写hashCode()会出现31数字？
- 选择系数的时候如果选择大的，查找的效率会更高
- 31只占用了5bits，相乘造成数据溢出的概率较小
- 31可以由i*31==（i<<5）-1来表示，提高了算法效率
- 31位一个素数（底下不能再分解），也减少了冲突
LinkedHashSet
- LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，以此来记录此数据的前一个数据和后一个数据
- 对于频繁的遍历操作，LinkedHashSet效率要高于HashSet

package www.bh.c.settest;
import java.util.Iterator;
import java.util.LinkedHashSet;

public class Test02 {
    public static void main(String[] args) {
        LinkedHashSet linkedHashSet = new LinkedHashSet();
        linkedHashSet.add(123);
        linkedHashSet.add(45);
        linkedHashSet.add(0);
        linkedHashSet.add("AA");
        linkedHashSet.add("dd");
        linkedHashSet.add("DD");
        linkedHashSet.add("BB");
        //遍历，每个数据还维护了两个引用，以此来记录此数据的前一个数据和后一个数据，并不是有序的
        Iterator iterator=linkedHashSet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());/*123
45
0
AA
dd
DD
BB*/                                          
        }
    }
}

TreeSet

向TreeSet中添加数据，要求是相同类的对象
TreeSet采用的是红黑树的存储结构，元素有序，查询速度比List快

两种排序方式：自然排序（实现Comparable接口），定制排序（Comparator）

package www.bh.c.settest;
import java.util.Iterator;
import java.util.TreeSet;

public class Test03 {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Test01("张三",12));
        treeSet.add(new Test01("李四",32));
        treeSet.add(new Test01("小明",15));
        treeSet.add(new Test01("李四",13));
        treeSet.add(new Test01("华子",7));
        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());//报错：ClassCastException
        }
    }
}

自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()

//1.创建对象类，并重写Comparable接口的CompareTo方法
package www.bh.c.settest;

public class Test01 implements Comparable {
private String name;
    private int age;

    public Test01() {
    }

    public Test01(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("=================");
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Test01 test01 = (Test01) o;

        if (age != test01.age) return false;
        return name != null ? name.equals(test01.name) : test01.name == null;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }

    //重写Comparable接口的CompareTo方法，按照姓名从小到大排序
    @Override
    public int compareTo(Object o) {
        if (o instanceof Test01){
            Test01 test01=(Test01)o;
            return this.name.compareTo(test01.name);
        }else {
            throw new RuntimeException("类型不匹配");
        }
    }

    @Override
    public String toString() {
        return "Test01{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

//2.将treeSet中的元素按照写好的compareTo()遍历
package www.bh.c.settest;
import java.util.Iterator;
import java.util.TreeSet;

public class Test03 {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Test01("张三",12));
        treeSet.add(new Test01("李四",32));
        treeSet.add(new Test01("小明",15));
        treeSet.add(new Test01("李四",13));
        treeSet.add(new Test01("华子",7));
        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
            /*
            Test01{name='华子', age=7}
            Test01{name='小明', age=15}
            Test01{name='张三', age=12}
            Test01{name='李四', age=32}
            */
            //TreeSet中存的元素为不重复的，如果名字重复则存储失败，所以按方法遍历不到
        }
    }
}

//3.优化compareTo()方法
//按照姓名从大到小排序,年龄从小到大排序
    @Override
    public int compareTo(Object o) {
        if(o instanceof Test01){
            Test01 test01=(Test01) o;
            int i = -this.name.compareTo(test01.name);
            if (i!=0){
                return i;
            }else {
                return Integer.compare(this.age,test01.age);
            }
        }else {
            throw new RuntimeException("类型不匹配");
        }
    }

package www.bh.c.settest;
import java.util.Iterator;
import java.util.TreeSet;

public class Test03 {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Test01("张三",12));
        treeSet.add(new Test01("李四",32));
        treeSet.add(new Test01("小明",15));
        treeSet.add(new Test01("李四",13));
        treeSet.add(new Test01("华子",7));
        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
            /*
            Test01{name='李四', age=13}
            Test01{name='李四', age=32}
            Test01{name='张三', age=12}
            Test01{name='小明', age=15}
            Test01{name='华子', age=7} 
            */
        }
    }
}

定制排序中：比较两个对象是否相同的标准为：compare()返回0，不再是equals()

package www.bh.c.settest;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

public class Test04 {
    public static void main(String[] args) {
        Comparator comparator=new Comparator(){
            //年龄从小到大排列
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Test01&&o2 instanceof Test01){
                    Test01 test01=(Test01)o1;
                    Test01 test02=(Test01)o2;
                    return Integer.compare(test01.getAge(),test02.getAge());
                }else {
                    throw new RuntimeException("输入类型有误");
                }
            }
        };
        TreeSet treeSet = new TreeSet(comparator);

        treeSet.add(new Test01("张三",12));
        treeSet.add(new Test01("李四",32));
        treeSet.add(new Test01("小明",15));
        treeSet.add(new Test01("李四",13));
        treeSet.add(new Test01("华子",7));
        Iterator iterator = treeSet.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

面试题：
1.在List内去除重复数字值，要求尽量简单

package www.bh.c.settest;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class Test05 {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(new Integer(1));
        list.add(new Integer(2));
        list.add(new Integer(2));
        list.add(new Integer(3));
        List list1 = duplicateList(list);
        Iterator iterator=list1.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());//[1,2,3]
        }
    }
    //将list先放到HashSet中，再返回一个新的List
    public static List duplicateList(List list){
        HashSet hashSet = new HashSet();
        hashSet.addAll(list);
        return new ArrayList(hashSet);
    }
}

2.以下代码输出的结果是什么？

package www.bh.c.settest;
import java.util.HashSet;

public class Test06 {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        Test01 p1=new Test01("A",10);
        Test01 p2=new Test01("B",10);
        hashSet.add(p1);
        hashSet.add(p2);
        System.out.println(hashSet);//
        p1.name="C";
        hashSet.remove(p1);
        System.out.println(hashSet);//
        hashSet.add(new Test01("C",10));
        System.out.println(hashSet);//
        hashSet.add(new Test01("A",10));
        System.out.println(hashSet);//
    }
}
/*
答案：
[Test01{name='B', age=10}, Test01{name='A', age=10}]，
[Test01{name='B', age=10}, Test01{name='C', age=10}]，
[Test01{name='C', age=10}, Test01{name='B', age=10}, Test01{name='C', age=10}]，
[Test01{name='C', age=10}, Test01{name='B', age=10}, Test01{name='C', age=10}, Test01{name='A', age=10}]
*/
//注：主要要先考虑哈希值

码农公寓

Collection子接口二：Set

相关文章