Set笔记

Set

继承自Collection的一个接口，特点是：无序，不可重复。注意啊！！只有Collection实现了迭代器！也就是说Map是没有实现迭代器的，需要keySet，values，entrySet这个几个方法

HashSet实现Set接口

SortedSet继承自Set接口，无序，不可重复，但是可以存进去的元素可以自动按照大小进行排序。TreeSet是他的一个实现类。

HashSet的底层是一个HashMap。为什么？因为HashMap中的key无序，不可重复，跟HashSet有一样的特性，一个没有value的HashMap不就是一个HashSet？

public HashSet() {

        map = new HashMap<>();

    }

HashMap底层是一个哈希表

transient Node<K,V>[] table;

哈希表是什么？是数组和单向链表的结合

哈希表的本质是一个数组，只不过这个数组中的每一个元素又是单向链表。类似于现实世界中的字典。

static class Node<K,V> implements Map.Entry<K,V> {

        final int hash;

        final K key;

        V value;

        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {

            this.hash = hash;

            this.key = key;

            this.value = value;

            this.next = next;

        }

        ………

        ………

    }

代码中的hash是key通过hashCode()方法，再通过哈希算法得到的一个值。在单向链表中，每一个结点的哈希值是相同的。

所以哈希表的查找过程是：通过key来得到哈希值，得到值后定位单向链表，然后遍历该链表。哈希表的增删效率都是比较高的。

向哈希表添加元素：通过key得到一个哈希值，如何在这个表中不存在这个值，就直接添加元素。否则，继续调用equals()，如果返回false则添加该元素，否则不添加，因为返回true的话证明里面已经有这个元素了。

HashSet是HashMap的key部分。

HashSet和HashMap的初始化容量是16 ，默认加载因子是0.75。比方说：容量是100，那么在装了75个元素的时候开始扩容

注意：存储在HashSet和HashMap中key部分的元素，需要重写hashCode()和equals();

public class HashSetTest {

    public static void main(String[] args) {

        Set set = new HashSet();

        Employee e1 = new Employee("24" , "KOBE");

        Employee e2 = new Employee("21" , "TIM");

        Employee e3 = new Employee("21" , "KG");

        Employee e4 = new Employee("3" , "AI");

        Employee e5 = new Employee("3" , "DW");

        Employee e6 = new Employee("24" , "KOBE");

        set.add(e1);

        set.add(e2);

        set.add(e3);

        set.add(e4);

        set.add(e5);

        System.out.println("set.size = " + set.size()); // set.size = 5

    }

}

class Employee{

    String no;

    String name;

    public Employee(String no , String name){

        this.no = no;

        this.name = name;

    }

    @Override

    public int hashCode() {

        return no.hashCode();  //String已经重写了hashCode方法，直接用它的

    }

    @Override

    public boolean equals(Object obj) {

        if (this == obj)

            return true;

        if (obj instanceof Employee){

            Employee e = (Employee)obj;

            if ( e.no.equals(this.no) && e.name.equals(this.name))

                return true;

        }

        return false;

    }

}

SortedSet存储元素为什么可以自动排序？如何实现的？

 public class SortedSetTest {

     public static void main(String[] args) {

         User u1 = new User("kobe");

         User u2 = new User("tim duncan");

         User u3 = new User("ray allen");

         User u4 = new User("melo");

         SortedSet set = new TreeSet();

         set.add(u1);

         set.add(u2);

         set.add(u3);

         set.add(u4);

     }

 }

 class User{

     String name;

     public User(String name){

         this.name = name;

     }

     @Override

     public String toString() {

         return "[user name = " + name + "]";

     }

 }

上述代码运行时会报错：User cannot be cast to java.lang.Comparable

看下TreeSet的源码

public TreeSet() {

        this(new TreeMap<E,Object>());

    }

public boolean add(E e) {

        return m.put(e, PRESENT)==null;

    }

发现底层是一个TreeMap。（其实跟HashSet类似，TreeSet也相当于TreeMap的key）

并且add()中是调用的TreeMap的put方法。这里再看下TreeMap的put方法源码。

public V put(K key, V value) {

       ……

        ……

        else {

            if (key == null)

                throw new NullPointerException();

            @SuppressWarnings("unchecked")

                Comparable<? super K> k = (Comparable<? super K>) key; //强制转换成Compareble

            do {

                parent = t;

                cmp = k.compareTo(t.key); //转换完后调用compareTo方法

                if (cmp < 0)     //小于0表示比根结点小，放左边

                    t = t.left;

                else if (cmp > 0)  //大于则放右边

                    t = t.right;

                else

                    return t.setValue(value);

            } while (t != null);

        }

       ……

    }

那么需要去实现这个Compareble接口，并重写compareTo方法。

class User implements Comparable{

    String name;

    int age;

    public User(String name , int age){

        this.name = name;

        this.age = age;

    }

    @Override

    public String toString() {

        return "[user name = " + name + " , age = " + age + "]";

    }

    @Override //该方法程序员负责实现，sun(或者说现在要叫oracle了 :) )提供的程序调用了该方法。

    public int compareTo(Object o) {

        //编写一个比较规则

        //根据年龄排序

        int age1 = this.age;

        int age2 = ((User)o).age;

        return age1 - age2;   //这个地方要注意只有在age的范围在一个足够小的时候才能这么干，如果age1是一个较大的整数，而age2是一个较小的负整数，age1-age2可能会溢出

        /*

         * [user name = melo , age = 2]

            [user name = kobe , age = 10]

            [user name = ray allen , age = 32]

            [user name = tim duncan , age = 200]

         */

    }

}

那么也可以按照名字来排序，String本身实现了compareble接口，所以可以直接用。

//根据名字来排序

        return name.compareTo(((User)o).name);

        /*

         * [user name = kobe , age = 10]

            [user name = melo , age = 2]

            [user name = ray allen , age = 32]

            [user name = tim duncan , age = 200]

         */

SortedSet实现排序还有一种方法，TreeSet中还有一个构造函数如下：

public TreeSet(Comparator<? super E> comparator) {

        this(new TreeMap<>(comparator));

    }

通过传入Comparator的实现类的参数来进行比较。

TreeMap中的put方法源码一部分如下：

Comparator<? super K> cpr = comparator;

        if (cpr != null) {

            do {

                parent = t;

                cmp = cpr.compare(key, t.key);

                if (cmp < 0)

                    t = t.left;

                else if (cmp > 0)

                    t = t.right;

                else

                    return t.setValue(value);

            } while (t != null);

        }else{

//这个else是之前说的第一种方法，可以看到java是优先使用Comparator这种方法的

        }

那么就写一个Comparator的实现类，并删掉之前User实现的Compareble接口以及compareTo方法。如果不删的话，结果也是一样的，因为java优先使用这种方法排序。其实也是推荐这种方式的，因为这样User就是一个更加纯粹的User。这种方式也可以写成匿名内部类的方式，不过为了代码的复用，最好还是单独写出来。

class UserComparator implements Comparator{

    @Override

    public int compare(Object o1, Object o2) {

        int age1 = ((User)o1).age;

        int age2 = ((User)o2).age;

        return age1 - age2;

    }

}

[user name = melo , age = 2]
[user name = kobe , age = 10]
[user name = ray allen , age = 32]
[user name = tim duncan , age = 200]

巴特西

Set笔记

最新文章

热门文章