通过元素自身实现比较规则
在元素自身实现比较规则时，需要实现Comparable接口中的 compareTo方法，该方法中用来定义比较规则。TreeSet通过调用 该方法来完成对元素的排序处理。
创建Users类
public class Users implements Comparable<Users>{ private String username; private int userage; public Users(String username, intuserage) { this.username = username; this.userage = userage; } public Users() { } @Override public boolean equals(Object o) { System.out.println("equals..."); if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Users users = (Users) o; if (userage != users.userage) return false; return username != null ? username.equals(users.username) : users.username == null; } @Override public int hashCode() { int result = username != null ? username.hashCode() : 0; result = 31 * result + userage; return result; } public String getUsername() { return username; } public void setUsername(String username) { this.username = username; } public int getUserage() { return userage; } public void setUserage(int userage) { this.userage = userage; } @Override public String toString() { return "Users{" + "username='" + username + '\'' + ", userage=" + userage + '}'; } //定义比较规则 //正数：大，负数：小，0：相等 @Override public int compareTo(Users o) { if(this.userage > o.getUserage()){ return 1; } if(this.userage == o.getUserage()){ return this.username.compareTo(o.getUsername()); } return -1; } }
Set<Users> set1 = new TreeSet<>(); Users u = new Users("oldlu",18); Users u1 = new Users("admin",22); Users u2 = new Users("sxt",22); set1.add(u); set1.add(u1); set1.add(u2); for(Users users:set1){ System.out.println(users); }
通过比较器实现比较规则
通过比较器定义比较规则时，我们需要单独创建一个比较器，比较 器需要实现Comparator接口中的compare方法来定义比较规则。 在实例化TreeSet时将比较器对象交给TreeSet来完成元素的排序处 理。此时元素自身就不需要实现比较规则了。
创建Student类
public class Student { private String name; private int age; public Student(String name, int age) { this.name = name; this.age = age; } public Student() { } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; if (age != student.age) return false; return name != null ? name.equals(student.name) : student.name == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } }
创建比较器
public class StudentComparator implements Comparator<Student> { //定义比较规则 @Override public int compare(Student o1, Student o2) { if(o1.getAge() > o2.getAge()){ return 1; } if(o1.getAge() == o2.getAge()){ return o1.getName().compareTo(o2.getName()); } return -1; } }
public class TreeSetTest3 { public static void main(String[] args) { //创建TreeSet容器，并给定比较器对象 Set<Student> set = new TreeSet<>(new StudentComparator()); Student s = new Student("oldlu",18); Student s1 = new Student("admin",22); Student s2 = new Student("sxt",22); set.add(s); set.add(s1); set.add(s2); for(Student student:set){ System.out.println(student); } } }
TreeSet底层源码分析
成员变量
/** * The backing map. */ private transient NavigableMap<E,Object> m; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object();
构造方法
public TreeSet() { this(new TreeMap<E,Object>()); }
添加元素
/** * Adds the specified element to this set if it is not already present. * More formally, adds the specified element <tt>e</tt> to this set if * this set contains no element <tt>e2</tt> such that * <tt>(e==null ? e2==null : e.equals(e2))</tt>. * If this set already contains the element, the call leaves the set * unchanged and returns <tt>false</tt>. * * @param e element to be added to this set * @return <tt>true</tt> if this set did not already contain the specified * element */ public boolean add(E e) { return map.put(e, PRESENT)==null; }
单例集合使用案例
需求： 产生1-10之间的随机数([1,10]闭区间)，将不重复的10个随机数放到 容器中。
使用List类型容器实现
public class ListDemo { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); while(true){ //产生随机数 int num = (int) (Math.random()*10+1); //判断当前元素在容器中是否存在 if(!list.contains(num)){ list.add(num); } //结束循环 if(list.size() == 10){ break; } } for(Integer i:list){ System.out.println(i); } } }
使用Set类型容器实现
public class SetDemo { public static void main(String[] args) { Set<Integer> set = new HashSet<>(); while(true){ int num = (int)(Math.random()*10+1); //将元素添加容器中，由于Set类型容器是、不允许有重复元素的，所以不需要判断。 set.add(num); //结束循环 if(set.size() == 10){ break; } } for(Integer i:set){ System.out.println(i); } } }
双例集合
Map接口介绍
Map接口定义了双例集合的存储特征，它并不是Collection接口的 子接口。双例集合的存储特征是以key与value结构为单位进行存 储。体现的是数学中的函数 y=f(x)感念。
Map与Collecton的区别：
1、Collection中的容器，元素是孤立存在的（理解为单身），向集 合中存储元素采用一个个元素的方式存储。
2、Map中的容器，元素是成对存在的(理解为现代社会的夫妻)。每 个元素由键与值两部分组成，通过键可以找对所对应的值。
3、Collection中的容器称为单列集合，Map中的容器称为双列集 合。
4、Map中的集合不能包含重复的键，值可以重复；每个键只能对应 一个值。
5、Map中常用的容器为HashMap，TreeMap等。
Map接口中常用的方法表
HashMap容器的使用
HashMap采用哈希算法实现，是Map接口最常用的实现类。 由于 底层采用了哈希表存储数据，我们要求键不能重复，如果发生重 复，新的键值对会替换旧的键值对。 HashMap在查找、删除、修 改方面都有非常高的效率。
public class HashMapTest { public static void main(String[] args) { //实例化HashMap容器 Map<String,String> map = new HashMap<>(); //添加元素 map.put("a","A"); map.put("b","B"); map.put("c","C"); map.put("a","D"); //获取容器中元素数量 int size = map.size(); System.out.println(size); System.out.println("---------------"); //获取元素 //方式一 String v = map.get("a"); System.out.println(v); System.out.println("---------------"); //方式二 Set<String> keys = map.keySet(); for(String key:keys){ String v1 = map.get(key); System.out.println(key+" ----"+v1); } System.out.println("-------------------"); //方式三 Set<Map.Entry<String,String>> entrySet = map.entrySet(); for(Map.Entry<String,String> entry:entrySet){ String key = entry.getKey(); String v2 = entry.getValue(); System.out.println(key+" ---------- "+v2); } System.out.println("--------------------"); //Map容器的并集操作 Map<String,String> map2 = new HashMap<>(); map2.put("f","F"); map2.put("c","CC"); map.putAll(map2); Set<String> keys2 = map.keySet(); for(String key:keys2){ System.out.println("key: "+key+" Value: "+map.get(key)); } System.out.println("---------------"); //删除元素 String v3 = map.remove("a"); System.out.println(v3); Set<String> keys3 = map.keySet(); for(String key:keys3){ System.out.println("key: "+key+" Value: "+map.get(key)); } System.out.println("-------------------"); //判断Key是否存在 boolean b = map.containsKey("b"); System.out.println(b); //判断Value是否存在 boolean cc = map.containsValue("CC"); System.out.println(cc); } }
HashTable类和HashMap用法几乎一样，底层实现几乎一样，只不 过HashTable的方法添加了synchronized关键字确保线程同步检 查，效率较低。
HashMap与HashTable的区别
1 HashMap: 线程不安全，效率高。允许key或value为null
2 HashTable: 线程安全，效率低。不允许key或value为null
HashMap的底层源码分析
底层存储介绍
HashMap底层实现采用了哈希表，这是一种非常重要的数据结构。 对于我们以后理解很多技术都非常有帮助。 数据结构中由数组和链表来实现对数据的存储，他们各有特点。
(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和 删除效率非常低。
(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加 和删除效率非常高。 那么，我们能不能结合数组和链表的优点（即查询快，增删效率也 高）呢？ 答案就是“哈希表”。 哈希表的本质就是“数组+链表”。
Oldlu建议
对于本章中频繁出现的“底层实现”讲解，建议学有余力的童鞋将 它搞通。刚入门的童鞋如果觉得有难度，可以暂时跳过。入门 期间，掌握如何使用即可，底层原理是扎实内功，便于大家应 对一些大型企业的笔试面试。
HashMap中的成员变量
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64; /** * The number of key-value mappings contained in this map. */ transient int size; /** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K,V>[] table;
容器【双例集合、TreeMap容器的使用、 Iterator接口、Collections工具类】(四)-全面详解（学习总结---从入门到深化）（中）：https://developer.aliyun.com/article/1419934
