集合

3-set接口

2021-07-09 276 0

简介 HashSet、LinkedHashSet、TreeSet实现类的具体介绍

1. set接口

|----Collection接口:单列集合,用来存储一个一个的对象

         |----Set接口:存储无序的、不可重复的数据   -->高中讲的集合

             |----HashSet:作为Set接口的主要实现类;线程不安全的;可以存储null

                 |----LinkedHashSet:作为HashSet的子类;遍历其内部数据时,可以按照添加的顺序遍历

                                     对于频繁的遍历操作,LinkedHashSet效率高于HashSet.

             |----TreeSet:其中的元素是同一个类的对象,可以按照对象的指定属性进行排序。

Set接口中没有额外定义新的方法,使用的都是Collection中声明过的方法。

要求:

 向Set(主要指:HashSet、LinkedHashSet)中添加的数据,其所在的类一定要重写hashCode()和equals()

 重写的hashCode()和equals()尽可能保持一致性:相等的对象必须具有相等的散列值

 重写两个方法的小技巧:对象中用作 equals() 方法比较的 Field,都应该用来计算 hashCode 值。基本上都是使用工具生成,一般不建议自己手动实现。

List存储的数据是有序的,可重复的,set存储的数据是无序的不可重复的

一、Set:存储无序的、不可重复的数据

以HashSet为例说明:

1. 无序性:不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加,而是根据数据的哈希值决定的。哈希值决定了数据存储的位置。

  list是有序的,意思是存储数据是按顺序存储的,一个挨着一个,相邻的数据元素的内存地址也是连续的。也就是逻辑上相邻,物理上也相邻。

  而HashSet存储的位置不是按顺序来的,也就是其在内存中不是按顺序存储的。

2. 不可重复性:保证添加的元素按照equals()判断时,不能跟已有的元素相同。 相同的元素,只能添加一个。

二、添加元素的过程:以HashSet为例:

   我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,

   此哈希值接着通过某种算法(散列函数、哈希函数)计算出在HashSet底层数组中的存放位置(即为:索引位置),

   判断数组此位置上是否已经有元素:

       如果此位置上没有其他元素,则元素a添加成功。 --->情况1

       如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的hash值:

           如果hash值不相同,则元素a添加成功。--->情况2

           如果hash值相同,进而需要调用元素a所在类的equals()方法:

                  equals()返回true,元素a添加失败(说明a和b是相同的)

                  equals()返回false,则元素a添加成功。--->情况3(hash值虽然相同,但是元素可能不同,哈希碰撞的情况)

   对于添加成功的情况2和情况3而言:元素a 与已经存在指定索引位置上数据以链表的方式存储。

   jdk 7 :元素a放到数组中,指向原来的元素。

   jdk 8 :原来的元素在数组中保持不动,在链表的末尾添加a

   总结:七上八下

   HashSet底层:数组+链表的结构。


  1. //SetItfTest.java

  2. package com.ylaihui.setitf;

  3. import java.util.HashSet;

  4. import java.util.Iterator;

  5. import java.util.Objects;

  6. class Order{

  7.     int id;

  8.     double price;

  9.     public Order() {

  10.     }

  11.     @Override

  12.     public String toString() {

  13.         return "Order{" +

  14.                 "id=" + id +

  15.                 ", price=" + price +

  16.                 '}';

  17.     }

  18.     public Order(int id, double price) {

  19.         this.id = id;

  20.         this.price = price;

  21.     }

  22.     @Override

  23.     public boolean equals(Object o) {

  24.         if (this == o) return true;

  25.         if (o == null || getClass() != o.getClass()) return false;

  26.         Order order = (Order) o;

  27.         return id == order.id &&

  28.                 Double.compare(order.price, price) == 0;

  29.     }

  30.     @Override

  31.     public int hashCode() {

  32.         return Objects.hash(id, price);

  33.     }

  34. }

  35. public class SetItfTest {

  36.     public static void main(String[] args) {

  37.         HashSet hashSet = new HashSet();

  38.         hashSet.add(111);

  39.         hashSet.add(222);

  40.         hashSet.add("ylaihui");

  41.         hashSet.add("ylaihui");

  42.         hashSet.add(new Order(111,100.50));

  43.         hashSet.add(new Order(111,100.50));

  44.         Iterator iterator = hashSet.iterator();

  45.         while(iterator.hasNext()){

  46.             System.out.println(iterator.next());

  47.         }

  48.     }

  49. }

  50. /*

  51. ylaihui

  52. Order{id=111, price=100.5}

  53. 222

  54. 111

  55. */



2. 为什么在hashCode方法中会出现31这个数?

以Eclipse/IDEA为例,在自定义类中可以调用工具自动重写equals和hashCode。

问题: 为什么用Eclipse/IDEA复写hashCode方法,有31这个数字?


  1. public static int hashCode(Object a[]) {

  2.     if (a == null)

  3.         return 0;

  4.     int result = 1;

  5.     for (Object element : a)

  6.         result = 31 * result + (element == null ? 0 : element.hashCode());

  7.     return result;

  8. }


 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的“冲突”就越少,查找起来效率也会提高。(减少冲突)

 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。 (提高算法效率,2的多少次方,这样的计算,效率高)

 并且31只占用5bits,相乘造成数据溢出的概率较小。

 31是一个质数,质数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结果只能被素数本身和被乘数还有1来整除! (减少冲突)

最终选择了31这个数


3. LinkedHashSet的使用

LinkedHashSet作为HashSet的子类,在添加数据的同时,每个数据还维护了两个引用,记录此数据前一个数据和后一个数据,对于频繁的遍历操作,LinkedHashSet效率高于HashSet

upfile


  1. //LinkedHashSetTest.java

  2. package com.ylaihui.setitf;

  3. import java.util.LinkedHashSet;

  4. import java.util.Objects;

  5. class Book{

  6.     int id;

  7.     double price;

  8.     public Book() {

  9.     }

  10.     @Override

  11.     public String toString() {

  12.         return "Book{" +

  13.                 "id=" + id +

  14.                 ", price=" + price +

  15.                 '}';

  16.     }

  17.     public Book(int id, double price) {

  18.         this.id = id;

  19.         this.price = price;

  20.     }

  21.     @Override

  22.     public boolean equals(Object o) {

  23.         if (this == o) return true;

  24.         if (o == null || getClass() != o.getClass()) return false;

  25.         Book book = (Book) o;

  26.         return id == book.id &&

  27.                 Double.compare(book.price, price) == 0;

  28.     }

  29.     @Override

  30.     public int hashCode() {

  31.         return Objects.hash(id, price);

  32.     }

  33. }

  34. public class LinkedHashSetTest {

  35.     public static void main(String[] args) {

  36.         LinkedHashSet set = new LinkedHashSet();

  37.         set.add(111);

  38.         set.add(222);

  39.         set.add("ylaihui");

  40.         set.add("ylaihui");

  41.         set.add(new Order(111,100.50));

  42.         set.add(new Order(111,100.50));

  43.         for (Object o : set) {

  44.             System.out.println(o);

  45.         }

  46.     }

  47. }

  48. /*

  49. 111

  50. 222

  51. ylaihui

  52. Order{id=111, price=100.5}

  53. 添加的顺序与遍历的顺序一致,因为底层加了一个双向的链表

  54. */


4. TreeSet的使用

TreeSet 是 SortedSet 接口的实现类, TreeSet 可以确保集合元素处于排序状态。

TreeSet底层使用红黑树结构存储数据

TreeSet 两种排序方法: 自然排序定制排序。默认情况下, TreeSet 采用自然排序

 TreeSet和TreeMap采用红黑树的存储结构

 特点:有序,查询速度比List快 


5. TreeSet的自然排序

自然排序: TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系,然后将集合元素按升序(默认情况)排列

如果试图把一个对象添加到 TreeSet 时,则该对象的类必须实现 Comparable接口。

实现 Comparable 的类必须实现 compareTo(Object obj) 方法,两个对象即通过compareTo(Object obj) 方法的返回值来比较大小。

 Comparable 的典型实现:

BigDecimal、 BigInteger 以及所有的数值型对应的包装类:按它们对应的数值大小进行比较

Character:按字符的 unicode值来进行比较

Boolean: true 对应的包装类实例大于 false 对应的包装类实例

String:按字符串中字符的 unicode 值进行比较

Date、 Time:后边的时间、日期比前面的时间、日期大

向 TreeSet 中添加元素时,只有第一个元素无须比较compareTo()方法,后面添加的所有元素都会调用compareTo()方法进行比较,也就是向TreeSet中添加的第一个元素决定了后续可添加的每个元素的类型。

因为只有相同类的两个实例才会比较大小,所以向 TreeSet 中添加的应该是同一个类的对象。

对于 TreeSet 集合而言,它判断两个对象是否相等的唯一标准是:两个对象通过 compareTo(Object obj) 方法比较返回值。

当需要把一个对象放入 TreeSet 中,重写该对象对应的 equals() 方法时,应保证该方法与 compareTo(Object obj) 方法有一致的结果:如果两个对象通过equals() 方法比较返回 true,则通过 compareTo(Object obj) 方法比较应返回 0。否则,让人难以理解。

如果自定义类不实现Comparable接口那么该类的对象无法放入TreeSet中: java.lang.ClassCastException: com.ylaihui.setitf.Person cannot be cast to java.lang.Comparable

  1. //TreeSetTest1.java

  2. package com.ylaihui.setitf;

  3. import java.util.TreeSet;

  4. public class TreeSetTest1 {

  5.     public static void main(String[] args) {

  6.         TreeSet set = new TreeSet();

  7.         // error: 只能添加相同类的对象

  8.         //set.add(111);

  9.         //set.add(222);

  10.         //set.add("aa");

  11.         set.add("y");

  12.         set.add("lai");

  13.         set.add("hui");

  14.         for (Object obj : set) {

  15.             System.out.println(obj);

  16.         }

  17.     }

  18. }


  1. //TreeSetTest2.java

  2. package com.ylaihui.setitf;

  3. import java.util.Objects;

  4. import java.util.TreeSet;

  5. class Person{

  6.     String name;

  7.     int age;

  8.     public Person() {

  9.     }

  10.     public Person(String name, int age) {

  11.         this.name = name;

  12.         this.age = age;

  13.     }

  14.     @Override

  15.     public String toString() {

  16.         return "Person{" +

  17.                 "name='" + name + '\'' +

  18.                 ", age=" + age +

  19.                 '}';

  20.     }

  21.     @Override

  22.     public boolean equals(Object o) {

  23.         if (this == o) return true;

  24.         if (o == null || getClass() != o.getClass()) return false;

  25.         Person person = (Person) o;

  26.         return age == person.age &&

  27.                 Objects.equals(name, person.name);

  28.     }

  29.     @Override

  30.     public int hashCode() {

  31.         return Objects.hash(name, age);

  32.     }

  33. }

  34. public class TreeSetTest2 {

  35.     public static void main(String[] args) {

  36.         // java.lang.ClassCastException: com.ylaihui.setitf.Person cannot be cast to java.lang.Comparable

  37.         // 放入TreeSet中的对象要求是可比较的,需要实现Comparable接口

  38.         TreeSet set = new TreeSet();

  39.         set.add(new Person("Andy",6));

  40.         set.add(new Person("Caddy",12));

  41.         set.add(new Person("ylaihui",33));

  42.         set.add(new Person("Jim",22));

  43.     }

  44. }


6. TreeSet的自然排序

  1. //TreeSetTest3.java

  2. package com.ylaihui.setitf;

  3. import java.util.Objects;

  4. import java.util.TreeSet;

  5. class Phone implements Comparable{

  6.     String name;

  7.     double price;

  8.     public Phone(String name, double price) {

  9.         this.name = name;

  10.         this.price = price;

  11.     }

  12.     @Override

  13.     public String toString() {

  14.         return "Phone{" +

  15.                 "name='" + name + '\'' +

  16.                 ", price=" + price +

  17.                 '}';

  18.     }

  19.     @Override

  20.     public boolean equals(Object o) {

  21.         if (this == o) return true;

  22.         if (o == null || getClass() != o.getClass()) return false;

  23.         Phone phone = (Phone) o;

  24.         return Double.compare(phone.price, price) == 0 &&

  25.                 Objects.equals(name, phone.name);

  26.     }

  27.     @Override

  28.     public int hashCode() {

  29.         return Objects.hash(name, price);

  30.     }

  31.     public Phone() {

  32.     }

  33.     @Override

  34.     public int compareTo(Object o) {

  35.         if(o instanceof Phone){

  36.             Phone p = (Phone) o;

  37.             // name 从大到小排序

  38.             int ret = -this.name.compareTo(((Phone) o).name);

  39.             if(ret == 0)

  40.                 // price 从小到大排序

  41.                 return Double.compare(this.price,((Phone) o).price);

  42.             else

  43.                 return ret;

  44.         }else

  45.             throw new RuntimeException("无法比较的类型");

  46.     }

  47. }

  48. public class TreeSetTest3 {

  49.     public static void main(String[] args) {

  50.         TreeSet set = new TreeSet();

  51.         set.add(new Phone("huawei",4288));

  52.         set.add(new Phone("huawei",1288));

  53.         set.add(new Phone("iPhone",5288));

  54.         set.add(new Phone("mi",1288));

  55.         // 如果重写的compareTo 方法只比较的name

  56.         // 那么下面的两条数据只能插入第一条,因为name相等,

  57.         // TreeSet底层判断这两个对象是相等的 compareTo 返回0

  58.         set.add(new Phone("vivo",1288));

  59.         set.add(new Phone("vivo",2288));

  60.         for (Object obj : set) {

  61.             System.out.println(obj);

  62.         }

  63.     }

  64. }

  65. /*

  66. Phone{name='vivo', price=1288.0}

  67. Phone{name='vivo', price=2288.0}

  68. Phone{name='mi', price=1288.0}

  69. Phone{name='iPhone', price=5288.0}

  70. Phone{name='huawei', price=1288.0}

  71. Phone{name='huawei', price=4288.0}

  72.  */


7. TreeSet的定制排序

  1. //TreeSetTest4.java

  2. package com.ylaihui.setitf;

  3. import java.util.Comparator;

  4. import java.util.Objects;

  5. import java.util.TreeSet;

  6. class User{

  7.     int id;

  8.     String name;

  9.     public User() {

  10.     }

  11.     public User(int id, String name) {

  12.         this.id = id;

  13.         this.name = name;

  14.     }

  15.     @Override

  16.     public String toString() {

  17.         return "User{" +

  18.                 "id=" + id +

  19.                 ", name='" + name + '\'' +

  20.                 '}';

  21.     }

  22.     @Override

  23.     public boolean equals(Object o) {

  24.         if (this == o) return true;

  25.         if (o == null || getClass() != o.getClass()) return false;

  26.         User user = (User) o;

  27.         return id == user.id &&

  28.                 Objects.equals(name, user.name);

  29.     }

  30.     @Override

  31.     public int hashCode() {

  32.         return Objects.hash(id, name);

  33.     }

  34. }

  35. public class TreeSetTest4 {

  36.     public static void main(String[] args) {

  37.         Comparator comparator = new Comparator() {

  38.             @Override

  39.             public int compare(Object o1, Object o2) {

  40.                 if(o1 instanceof User && o2 instanceof User){

  41.                     User u1 = (User) o1;

  42.                     User u2 = (User) o2;

  43.                     return Integer.compare(u1.id,u2.id);

  44.                 }

  45.                 else

  46.                     throw new RuntimeException("无法比较的数据类型");

  47.             }

  48.         };

  49.         TreeSet set = new TreeSet(comparator);

  50.         set.add(new User(111,"Andy"));

  51.         set.add(new User(111,"Jimmy"));

  52.         set.add(new User(333,"Caddy"));

  53.         set.add(new User(444,"lisimmy"));

  54.         set.add(new User(555,"ylaihui"));

  55.         set.add(new User(555,"hahaha"));

  56.         for (Object obj : set) {

  57.             System.out.println(obj);

  58.         }

  59.     }

  60. }

  61. /*

  62. User{id=111, name='Andy'}

  63. User{id=333, name='Caddy'}

  64. User{id=444, name='lisimmy'}

  65. User{id=555, name='ylaihui'}

  66.  */


点赞 0

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 38820 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: