Java-Day-19

总结 - 开发中如何选择集合实现类

• 在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择

  • 先判断存储的类型 ( 一组对象或一组键值对 )

• 一组对象 ( 单列 )：Collection 接口

  • 允许重复：List

    • 增删多：LinkedList [ 底层维护了一个双向链表 ]
    • 改查多：ArrayList [ 底层维护 Object 类型的可变数组 ]

  • 不允许重复：Set

    • 无序：HashSet [ 底层是 HashMap，维护了一个哈希表 ( 数组 + 链表 + 红黑树 ) ]

    • 排序：TreeSet

    • 插入和取出顺序一致：LinkedHashSet，维护数组 + 双向链表 ( 跨索引 )

      ( LinkedHashSet 底层是 LinkedHashMap 再底层是 HashMap )

• 一组键值对 ( 双列 )：Map

  • 键无序：HashMap [ 底层是哈希表，jdk7：数组 + 链表，jdk8：数组 + 链表 + 红黑树 ]
  • 键排序：TreeSet
  • 键插入和取出顺序一致：LinkedHashMap
  • 读取文件：Properties

TreeSet

• 排序的话要注意构造器

  public class test1 {
      public static void main(String[] args) {
  //        无参构造器，创建仍无序
  //        TreeSet treeSet = new TreeSet();
  //        若是希望添加元素按字符串大小来排序，
  //        使用提供的一个构造器，可传入一个比较器(匿名内部类)，并指定排序规则
          TreeSet treeSet = new TreeSet(new Comparator() {
              @Override
              public int compare(Object o1, Object o2) {
  //                由于举例是字符串，所以这里下转String
                  return ((String) o1).compareTo((String) o2);
                  /*
                  compareTo() 循环取出每个字符，若是不相等的就得ASCII值的差
                  o1 是新加入的值，源码可知差为负(新的小)就放左边
                   */
  
  //                从大到小的话就-更换排序规则：
  //                return ((String) o2).compareTo((String) o1);
  
  //                若是想要求加入的元素按照长度大小进行排序就：从短到长(但是存在弊端，即，同长度的就不能添加了)
  //                return ((String) o1).length() - ((String) o2).length();
              }
          });
  //        添加数据
          treeSet.add("zyz");
          treeSet.add("java");
          treeSet.add("duang");
          System.out.println(treeSet);
          /*      
          1. 构造器把传入的比较对象，赋给了TreeSet的底层的TreeMap的属性this.comparator
          public TreeMap(Comparator<? super K> comparator) {
              this.comparator = comparator;
          }
          
          TreeSet 的 add()，返回的是 TreeMap 的 put()
          value 为静态空 Object：PRESENT
          public boolean add(E e) {
          	return m.put(e, PRESENT)==null;
      	}
          可知 TreeSet 的底层就是 TreeMap
  
          2. 在调用treeSet.add第二个元素时，会在底层执行：
              Comparator<? super K> cpr = comparator;
              if (cpr != null) { // cpr：传进入的匿名内部类(对象)
                  do {
                      parent = t;
                      cmp = cpr.compare(key, t.key);
                      // 动态绑定到匿名内部类的compare方法
                      // return 的差值由cmp接收
                      if (cmp < 0)
                          t = t.left;
                      else if (cmp > 0)
                          t = t.right;
                      else // 如果相等就返回的是0，即重复无法加入
                          return t.setValue(value);
                  } while (t != null);
              }
          */
      }
  }
  

TreeMap

• 实现 Map 接口

• TreeSet 的底层就是 TreeMap ( 因为 TreeSet 里 add 添加的时候，进 TreeSet 的 add 方法，返回的是 TreeMap 的 put 方法 )

  public TreeMap(Comparator<? super K> comparator) {
      this.comparator = comparator;
  }
  
  
  public class test1 {
      public static void main(String[] args) {
  //        不使用默认的构造器(虽然默认的话也是计算ASCII码的值?)
  //        TreeMap treeMap = new TreeMap();
  //        似TreeSet,要求:匿名内部类 new Comparator
          TreeMap treeMap = new TreeMap(new Comparator() {
              @Override
              public int compare(Object o1, Object o2) {
  //                按字符 ASCII值,小到大
                  return ((String) o1).compareTo((String) o2);
              }
          });
          treeMap.put("zyz", "v-duang");
          treeMap.put("java", "v-ooo");
          treeMap.put("ooo", "v-java");
          treeMap.put("duang", "v-duang");
          System.out.println(treeMap);
  
          /*
          1. 构造器:把传入了 实现了Comparator接口的匿名内部类(对象),
          即main里编写的传到了下面一行的 comparator
          public TreeMap(Comparator<? super K> comparator) {
              this.comparator = comparator;
          }
          2. 第一次直接添加,Entry封装后存进root
              Entry<K,V> t = root;
              if (t == null) {
                  compare(key, key); // type (and possibly null) check，只是为了防止为空，空就报错
  
                  root = new Entry<>(key, value, null);
                  size = 1;
                  modCount++;
                  return null;
              }
          3. 第二次进入,把新put的进行一系列操作挂在root的left或right上(或是相同不处理):
          赋给cpr实现了的匿名内部类 Comparator<? super K> cpr = comparator;
              if (cpr != null) {
                  do { // 遍历所有的key,给当前key找到适当位置
                      parent = t; // 前面 Entry<K,V> t = root;
                      cmp = cpr.compare(key, t.key); // 动态绑定到我们匿名内部类的compare方法
                      // 下面根据compare所得决定放左还是右,
                      if (cmp < 0)
                          t = t.left;
                      else if (cmp > 0)
                          t = t.right;
                      else // 相同不添加
                          return t.setValue(value);
                  // 左/右非空的话就循环再比较
                  } while (t != null);
              }
              // 处理新加入的值
              Entry<K,V> e = new Entry<>(key, value, parent);
              if (cmp < 0)
                  parent.left = e;
              else
                  parent.right = e;
              fixAfterInsertion(e);
              size++;
              modCount++;
              return null;
         */
      }
  }