Java集合 HashSet 和 TreeSet的理解

HashSet

HashSet实现了 Set 接口，底层是一个HashMap。源码如下：

public class HashSet<E>
    {
        private transient HashMap<E,Object> map;

        public HashSet() {
            map = new HashMap<>();
        }
    }

通过以上源码可以发现，创建一个HashSet对象实际上是创建了一个HashMap对象。

HashSet中的元素是无序的。这里的无序指的是进出集合的顺序。如下：

public class HashSetTest {
    public static void main(String[] args) {
        HashSet<String> hashSet = new HashSet<>();

        hashSet.add("1.Java");
        hashSet.add("2.HashSet");
        hashSet.add("3.元素");
        hashSet.add("4.进出");
        hashSet.add("5.无序");

        // 使用增强for循环变量元素
        for(String str : hashSet){
            System.out.println(str);
        }
    }
}

遍历结果为：

4.进出
2.HashSet
3.元素
1.Java
5.无序

从遍历的结果来看，元素遍历时的顺序和添加时的顺序不同。

HashSet中的元素是唯一的。多次添加相同的元素，只会有一个元素加入HashSet。通过查看HashSet中add方法的源码发现，这依赖于底层的hashCode方法和equals方法。如下：

// HashSet中的add方法，其中又调用了HashMap中的put方法
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

从以上可以看出： add方法只是作了一个判断，添加元素真正起作用的还是HashMap中的put方法，元素是作为key存储的。

// HashMap中的put方法，这里的key是HashSet中的元素
 public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e =  e.next) {
        Object k;
        if (e.hash==hash && ((k=e.key)==key||key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
         }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

// put方法中调用的hash方法，返回值与key（即元素）的hashCode方法有关
final int hash(Object k) {
    int h = hashSeed;
    if ( != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();
    h ^= (h >>> ) ^ (h >>> );
    return h ^ (h >>> ) ^ (h >>> );
}

从put方法的源码中可以知道，判断元素是否唯一，取决于表达式e.hash==hash && ((k=e.key)==key||key.equals(k))的值。其中hash值的计算与元素的hashCode方法有关；而((k=e.key)==key||key.equals(k)) 与元素的equals方法有关。如果元素的hash值相同，且元素相等（对于基础数据类型而言）或内容相同（对于引用类型而言），表达式结果为true，说明HashSet中已有这个元素，则不会继续添加该元素。综上，说明HashSet中元素的唯一性与元素中的hashCode方法和equals方法有关。要保证HashSet中元素的唯一性，就需要保证这两个方法正常判断。因此，当HashSet中的元素为自定义类的对象时，自定义类就需要重写hashCode方法和equals方法。如下：

public class Student {
    private String name;
    private int age;
    private String sex;

    Student(){
    }

    Student(String name, int age, String sex){
        this.name = name;
        this.age = age;
        this.sex = sex;
    }

    public int hashCode() {
        final int prime = ;
        int result = ;
        result = prime * result + age;
        result = prime * result + 
                 ((name == null) ?  : name.hashCode());
        result = prime * result + 
                 ((sex == null) ?  : sex.hashCode());
        return result;
    }

    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;
        if (sex == null) {
            if (other.sex != null)
                return false;
        } else if (!sex.equals(other.sex))
            return false;
        return true;
    }
}

TreeSet

TreeSet的底层是TreeMap。如下：

public class TreeSet<E> 
{
    private transient NavigableMap<E,Object> m;

    // 这里的NavigableMap是接口
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    //TreeMap实现了NavigableMap接口
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
}

TreeSet的元素很有特点，元素是唯一的，而且集合会根据元素的自然顺序对元素排序，但元素的进出仍然是无序的。如下：

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet();

        // 添加元素
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();
        treeSet.add();

        // 遍历元素
        for(Integer number : treeSet){
            System.out.print(number + );
        }
    }
}

遍历结果为：

1 3 4 5 7

这说明TreeSet中的元素不重复，按自然顺序排序，且进出无序。实际上，TreeSet中元素的自然排序和元素的唯一性依赖于compareTo或compare方法。如下：

//TreeSet 中的add方法，元素仍然是作为key 存储的
public boolean add(E e) {
        return m.put(e, PRESENT)==null;
}

// TreeMap 中的put方法
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); 
        root = new Entry<>(key, value, null);
        size = ;
        modCount++;
        return null;
    }

    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    // TreeSet中的构造TreeSet(Comparator<? super E> comparator)
    // 实际上是调用了TreeMap中的同参构造方法，即：
    // TreeMap(Comparator<? super K> comparator)
    // 此时，指定了comparator（排序比较器），就按比较器的规则进行比较
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < )
                t = t.left;
            else if (cmp > )
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }

    // TreeSet中的无参构造方法，实际上是调用TreeMap的空参构造方法
    // 此时没有指定comparator(排序比较器)，comparator 为null，
    // 比较时调用元素中的compareTo方法
    else {
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < )
                t = t.left;
            else if (cmp > )
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < )
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

从以上源码可知：TreeSet在添加元素时，会对元素进行自然顺序的比较。如果TreeSet的构造方法中指定了排序比较器comparator，元素的比较就使用排序比较器中的compare方法；如果没有指定，元素的比较就使用元素中的compareTo方法。因此，要在TreeSet 中添加自定义类的对象作为元素时，要么在TreeSet的构造方法中指定排序比较器；要么在自定义类中实现Comparable接口，重写compareTo方法。如下：

// 重写compareTo方法
public class Person implements Comparable<Person>
{
    private String name;
    private String sex;
    private int age;

    Person(String name, String sex, int age){
        this.name = name;
        this.sex = sex;
        this.age = age;
    }

    public int compareTo(Person p) {
        int result1 = this.name.compareTo(p.name);
        int result2 = this.sex.compareTo(p.sex);
        int result3 = this.age - p.age;

        return result1== ?
              (result2== ? 
              (result3== ? result3 : result3)
              : result2 ) : result1;
    }
}

或者指定比较器comparator

public class TreeSetTest {
    public static void main(String[] args) {
    // 创建TreeSet对象时，在构造方法中使用匿名类的方式指定comparator
        TreeSet<Person> treeSet = 
            new TreeSet<>(new Comparator<Person>(){
            public int compare(Person p1, Person p2) {
               int result1 =   p1.getName().compareTo(
                               p2.getName());
                int result2 = p1.getSex().compareTo(p2.getSex());
                int result3 = p1.getAge() - p2.getAge();

                return result1== ?
                      (result2== ? 
                      (result3== ? result3 : result3)
                      : result2 ) : result1;
            }
        });

        treeSet.add(new Person("John","male",));
        treeSet.add(new Person("Michle","male",));
        treeSet.add(new Person("Lucy","female",));
        treeSet.add(new Person("John","male",));
        treeSet.add(new Person("Lucy","female",));
        treeSet.add(new Person("Adam","male",));

        for(Person person : treeSet){
            System.out.println(person + " ");
        }
    }
}

Java集合 HashSet 和 TreeSet的理解

HashSet

TreeSet

继续阅读

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

Spring整合JMS(二)——三种消息监听器一、消息监听器MessageListener

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method