学习目标

  • 排序查找算法
    • 选择排序
    • 二分查找
  • Map集合
    • Map集合的特点
    • Map集合的特点及实现类
    • Map集合的遍历方式
  • 集合嵌套
    • 单列集合嵌套单列集合
    • 单列集合嵌套双列集合
    • 双列集合嵌套双列集合
  • 集合案例-斗地

    1. ★ Map集合

    1.1 什么时使用双列集合 ?

    每个元素都有键与值两部分组成,记录的是键值对对应关系,即通过键可以找到值时使用双列集合。(键必须唯一，值可以重复)

    1.2 HashMap集合特点及使用 ?

  1. 特点：
  • HashMap底层是哈希表结构的；
  • 依赖hashCode方法和equals方法保证键的唯一；
  • 如果键存储的是自定义对象，需要重写hashCode和equals方法。
  1. JDK1.8前后变化
  • JDK1.8前：哈希表由数组＋链表组成；头插法。
  • JDK1.8后：节点个数少于等于8个，数组+链表 组成；节点数多于8个，数组+红黑树组成；尾插法。

  1. 使用

    1. HashMap<Student, String> hm = new HashMap<>();
    3.      hm.put(new Student("迪丽热巴", 18) , "新疆");
    4.      hm.put(new Student("迪丽热巴", 18) , "中国");
    6.      Set<Student> set = hm.keySet();
    7.      for (Student key : set) {
    8.          String value = hm.get(key);
    9.          System.out.println(key + "--" + value);
    10.      }

    1.3 双列集合遍历方式及区别 ?

  2. 第一种遍历方式

  • 获取所有键的集合 keySet()；
  • 遍历键的集合；
  • 通过键，来获取对应值。
  1. 第二种遍历方式
  • 键值对对象：Map.Entry；
  • 获取所有键值对对象的集合 entrySet()；
  • 遍历集合，获取每一个键值对对象；
  • 根据键值对对象获取对应的键和值。

    1.4 集合的体系及每一种集合的特点 ?

    集合的体系
  1. 单列集合（单个的存：姓名） : Collection接口
  • List接口 : 1 有序 2 索引 3 元素可以重复
    • ArrayList类 : 数据结构(数组结构) 查询快,增删慢，线程不安全。
    • LinkedList类 : 数据结构(链表结构) 查询慢,增删快
  • Set 接口 : 1 无序 2 无索引 3 元素唯一
    • HashSet类 : 数据结构(哈希表) 查询快,保证元素唯一
    • LinkedHashSet类 : 数据结构(链表+哈希表) 查询快,保证元素唯一,有序
    • TreeSet类 : 数据结构(红黑树) 查询快,可以对元素进行排序
  1. 双列集合(两个两个的存：姓名、年龄) :
  • Map接口
    • HashMap类 : 数据结构(哈希表) 查询快,保证键唯一，线程不安全。
    • LinkedHashMap类 : 数据结构(链表+哈希表) 查询快,保证键唯一,有序，线程不安全。
    • TreeMap类 : 数据结构(红黑树) 查询快,可以对键进行排序，线程不安全。

      2. 排序查找算法

      2.1 排序查找算法思想及代码实现 ?

  1. 冒泡排序( 将一组数据按照从小到大的顺序进行排序)
    原理 : 相邻元素两两作比较 , 大的元素往后放。

    1.  使用： 
    1. int [] arr={3,5,3,2,4};
    2.      //外循环 控制的轮次
    3.      //length-1:为了防止索引越界
    4.      for (int j = 1; j <arr.length-1 ; j++) {
    5.          //每轮比较
    6.          for (int i = 0; i < arr.length-j; i++) {
    7.              if (arr[i]>arr[i+1]){
    8.                  int temp=arr[i];
    9.                  arr[i]=arr[i+1];
    10.                  arr[i+1]=temp;
    11.              }
    12.          }
    13.      }

  2. 选择排序( 将一组数据按照从小到大的顺序进行排序)
    原理:每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

    1. int [] arr={3,5,3,2,4};
    2.      //length-1:最后一趟可省略
    3.      for (int i = 0; i < arr.length-1; i++) {
    4.          //定义变量记录当前排序中最小元素的索引
    5.          int index=i;
    6.          //遍历当前元素到数组末尾
    7.          for (int j = i+1; j < arr.length; j++) {
    8.              if (arr[j]<arr[index]){
    9.                  index=j;
    10.              }
    11.          }
    12.          //元素交换位置
    13.          if (i!=index){
    14.              int temp=arr[i];
    15.              arr[i]=arr[index];
    16.              arr[index]=temp;
    17.          }
    18.      }

  3. 二分查找（须是有序列表）

    1. 原理：比较一个元素与数列中的**中间位**置的元素的大小，如果比中间位置的元素**大**，则继续在**后半部分**的数列中进行二分查找；如果比中间位置的元素**小**，则在数列的**前半部分**进行比较；如果**相等**，则找到了元素的位置。
    1. int min=0;
    2.      int max=arr.length-1;
    3.      while (min<=max){
    4.          int mid=(min+max)/2;
    5.          //判断的中间索引对应的元素是否是要查找的元素
    6.          if (arr[mid]==num){
    7.              return mid;
    8.          }else if(arr[mid]>num){
    9.              max=mid-1;
    10.          }else if(arr[mid]<num){
    11.              max=mid+1;
    12.          }
    13.      }
    14.      //min>max:num在数组arr中不存在
    15.      return -1;

    3.TreeSet集合

    3.1特点

  4. 底层红黑树，可以对元素进行排序。

  5. 集合是有序，不可重复的。

    3.2排序方式

  6. 自然排序：Comparable 接口

  7. 比较器排序：Comparator接口

注：两种方式都存在，我们优先使用Comparator接口。

3. 当日问题小结
3.1 当日遇到的问题

3.2 出现问题原因

3.3 解决问题方案