1、哈希结构集合（HashMap，HashSet）

HashSet集合的的底层是用HashMap实现的，其中HashSet中的元素是放在HashMap的key部分的，而HashMap的底层实现数据结构是哈希表，哈希表的结构如图所示：
image.png
哈希表是数组+单向链表的集合，拥有了数组和单向链表的共同优点。较新版本的JDK会在哈希表中的单向链表达到一定数量之后，自动转化为红黑树数据结构，数量减少后，又会恢复单向链表的数据结构。
#哈希表是通过hashCode经过哈希函数算法得到一个值，来辨别是否同一个节点的，如果经过哈希函数值相同，则属于同一个节点，否则开辟一个新的节点。其中每一个创建的对象都有一个hashcode，hashcode是通过hash算法利用物理地址得到的，主要用于类似HashMap、Hashtable和HashSet等的哈希集合（散列集合），识别同一节点使用的。
###数据结构逻辑（用HashMap、0节点举例）

集合 - 图2

类型 优点 缺点
数组 随机访问性强，可以通过计算数组下标直接读取数组元素，由于元素的存放地址是连续的，所以查找速度快 插入，删除等对数组有结构性改变的操作时，效率较低，而且数组的连续内存需要开辟，所以可能造成内存浪费，对内存要求较高
链表 插入和删除速度相对较快，内存利用率高，很容易拓展 不能随机查找，要从第一个开始遍历，所以查询效率较低

在使用哈希数据结构的集合时，使用的类对象一定要重写equals和hashCode两个方法。

  • 注意：在单个节点的Entry达到75%时，就会在该节点上将Entry以红黑树的数据结构存储，以提高效率，防止单向链表过长。

    2、二叉树集合（TreeMap，TreeSet）

    二叉树集合介绍：结构图如下
    image.png
    其中，二叉树是一种排序的数据结构，遵循左小右大的排序规则
    TreeSet：

    1. public class Test {
    3.   public static void main(String[] args) {
    4.       test01 t1 = new test01("c");
    5.       test01 t2 = new test01("b");
    6.       test01 t3 = new test01("a");
    7.       Set<test01> test01s = new TreeSet<>();
    8.       test01s.add(t1);
    9.       test01s.add(t2);
    10.       test01s.add(t3);
    11.       for (test01 t :test01s){
    12.           System.out.println(t);
    13.       }
    14.   }
    15. }
    16. class test01 implements Comparable<test01>{
    17.   private String name;
    19.   public test01(String name) {
    20.       this.name = name;
    21.   }
    23.   @Override
    24.   public String toString() {
    25.       return "test01{" +
    26.               "name='" + name + '\'' +
    27.               '}';
    28.   }
    29.   @Override
    30.   public int compareTo(test01 o) {
    31.       return this.name.compareTo(o.name);
    32.   }
    33. }
    34. 结果：
    35. test01{name='a'}
    36. test01{name='b'}
    37. test01{name='c'}

    TreeMap：

    1. public class Test {
    3.   public static void main(String[] args) {
    4.       test01 t1 = new test01("c");
    5.       test01 t2 = new test01("b");
    6.       test01 t3 = new test01("a");
    7.       Map<test01,Integer> test01s = new TreeMap<>();
    8.       test01s.put(t1,2);//c
    9.       test01s.put(t2,4);//b
    10.       test01s.put(t3,5);//a
    11.       for (Map.Entry<test01,Integer> node :test01s.entrySet()){
    12.           System.out.println(node);
    13.       }
    14.   }
    15. }
    16. class test01 implements Comparable<test01>{
    17.   private String name;
    19.   public test01(String name) {
    20.       this.name = name;
    21.   }
    23.   @Override
    24.   public String toString() {
    25.       return "test01{" +
    26.               "name='" + name + '\'' +
    27.               '}';
    28.   }
    30.   @Override
    31.   public int compareTo(test01 o) {
    32.       return this.name.compareTo(o.name);
    33.   }
    34. }
    35. 结果：
    36. test01{name='a'}=5
    37. test01{name='b'}=4
    38. test01{name='c'}=2

    终极结论：使用二叉树集合时，需要在所用的类中继承Comparable接口，而且要重写CompareTo方法，this表示当前对象。

    3、最终结论：

    哈希结构的集合中，HashSet的底层实现是HashMap，HashSet中对象放在HashMap的Key部分，
    二叉结构树的集合中，TreeSet的底层实现是TreeMap，TreeSet中对象放在TreeMap的Key部分，
    HashSet和TreeSet中的对象都是放在HashMap和TreeMap的Key部分，并通过Key来排序的。

    4、继承图

    image.png

    image.png