Android中需要了解的数据结构（四）

public interface Set<E> extends Collection<E> {}
Set是一个继承于Collection的接口，Set是一种不包括重复元素的Collection。它维持它自己的内部排序，所以随机访问没有任何意义。它允许null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同。

• HashSet

  public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
        private transient HashMap<E,Object> map;
        private static final Object PRESENT = new Object();
     
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    }
  复制代码

  HashSet实现Set接口，基于HashMap实现，底层使用HashMap保存数据。 非线程安全。

  HashSet是将数据存放到HashMap的Key中，再以PRESENT来作为值，来保证来唯一性。

  HashSet查找效率很高，它内部元素的顺序是由hashcode来决定的，所以它不保证set的迭代顺序。

  ArrayList中的两个元素是否相同，需要重写equals方法。而对于HashSet，除了要重写存入对象的equals方法外，还需要重写hashCode方法，保证HashSet中没有相同的两个对象，这点是和HashMap一样的。

• LinkedHashSet

  public class LinkedHashSet<E> extends HashSet<E>
            implements Set<E>, Cloneable, java.io.Serializable
  复制代码

  LinkedHashSet是HashSet的子类，LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的。

  LinkedHashSet内部使用LinkedHashMap实现，所以它和HashSet的关系就相当于HashMap和LinkedHashMap的关系。当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。

• TreeSet:

  public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable{}
  复制代码

  TreeSet是二叉树实现的，基于TreeMap，生成一个总是处于 排序 状态的set，内部以TreeMap来实现，不允许放入null值。它是使用元素的自然顺序对元素进行排序，或者根据创建Set时提供的 Comparator 进行排序，具体取决于使用的构造方法。

HashSet、LinkedHashSet与TreeSet的区别，应用场景是什么？

• HashSet:基于hashMap实现，非线程安全，允许插入null，查找效率高。适合查找操作频繁的场景。
• LinkedHashSet：基于hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的。
• TreeSet:基于二叉树实现，非线程安全，可以按照自然顺序或者自定义顺序自动排序，不允许插入null值。适合需要排序的场景。