JavaSet接口实现类(hashSet、LinkedHashSet、TreeSet),附两道常见面试题

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}]
*/
//注:主要要先考虑哈希值
上一篇:Java8集合框架——LinkedHashSet源码分析


下一篇:题目集7-9的总结性Blog