[数据结构与算法]java之Map接口于实现类

Map集合概述

Map父接口

• 特点：存储一堆数据（Key-Value），无序，无下标，键不可重复,

值可重复

• 方法：

  • V put（K key，V value）//将对象存入到集合中，关联键值。key重复则覆盖原值
  • Object get（Object key）//根据键获取对应的值
  • Set //返回所有key
  • Collection values（）//返回包含所有值的Collection集合
  • Set<Map.Entry<K,V>> //键值匹配的Set集合

• /**
   * Map接口的使用
   * 特点：（1）存储键值对 （2）键不能重复，值可以重复 （3）无序
   */
  
  public class Demo01 {
      public static void main(String[] args) {
          //    创建Map集合
          Map<String,String> map = new HashMap<>();
  //        添加元素
          map.put("cn","中国");
          map.put("uk","英国");
          map.put("usa","美国");
  //        map.put("cn","zhongguo");
  
          System.out.println("元素个数："+map.size());
          System.out.println(map.toString());
  
  //        删除
  //        map.remove("usa");
  //        System.out.println("元素个数："+map.size());
  //    遍历
  //        1。使用keySet（）；
  
  //        Set<String> keySet = map.keySet();
  
          for (String key : map.keySet()) {
              System.out.println(key+"----"+map.get(key));
  
          }
  //        2.使用entrySet（）方法
  //        Set<Map.Entry<String, String>> entries = map.entrySet();
          for (Map.Entry<String, String> entry : map.entrySet()) {
              System.out.println(entry.getKey()+"-----"+entry.getValue());
          }
      }
  
  }
  

HashMap 使用

Map集合的实现类

• HashMap 重点

  • JDK1.2 版本，线程不安全，运行效率快；允许null 作为key或是value

• /**
   * HashMap 集合的使用
   * 存储结构：哈希表（数组+链表+红黑树）
   * 使用key可hashcode 和 equals 作为重复
   */
  public class Demo02 {
      public static void main(String[] args) {
  //        创建集合
          HashMap<Student, String> students = new HashMap<>();
  //        添加元素
          Student s1 = new Student("孙悟空",111);
          Student s2 = new Student("猪八戒",222);
          Student s3 = new Student("沙和尚",333);
          students.put(s1,"北京");
          students.put(s2,"上海");
          students.put(s3,"南京");
          students.put(new Student("沙和尚",333),"南京");
  //        students.put(s1,"杭州");
          System.out.println("元素个数："+students.size());
          System.out.println(students.toString());
  //        删除元素
  //        students.remove(s1);
  //        System.out.println("元素个数："+students.size());
  //        遍历元素
  //        1.使用keySet();
          for (Student key : students.keySet()) {
              System.out.println(
                      key.toString()+"------"+students.get(key)
              );
  
          }
  //        2.使用entrySet();
          for (Map.Entry<Student, String> entry : students.entrySet()) {
              System.out.println(entry.getKey()+"-----"+entry.getValue());
          }
  //        判断
          System.out.println(students.containsKey(s1));
          System.out.println(students.containsValue("杭州"));
          System.out.println(students.isEmpty());
      }
  }
  

• 重写方法

  package com.gather.Map;
  
  public class Student {
      private String name;
      private int stuNo;
  
      public Student(String name, int stuNo) {
          this.name = name;
          this.stuNo = stuNo;
      }
  
      public Student() {
  
      }
  
      public String getName() {
          return name;
      }
  
      public void setName(String name) {
          this.name = name;
      }
  
      public int getStuNo() {
          return stuNo;
      }
  
      public void setStuNo(int stuNo) {
          this.stuNo = stuNo;
      }
  
      @Override
      public boolean equals(Object o) {
          if (this == o) return true;
          if (o == null || getClass() != o.getClass()) return false;
  
          Student student = (Student) o;
  
          if (stuNo != student.stuNo) 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 + stuNo;
          return result;
      }
  
      @Override
      public String toString() {
          return "Student{" +
                  "name='" + name + '\'' +
                  ", stuNo=" + stuNo +
                  '}';
      }
  }
  

HsahMap 源码分析

• 初始的容量大小

  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  

• 最大的容量大小

  static final int MAXIMUM_CAPACITY = 1 << 30;
  

• 默认加载因子

  static final float DEFAULT_LOAD_FACTOR = 0.75f;
  

• 当链表长度大于8时 调整成红黑树 提升效率 jdk1.8之后

static final int TREEIFY_THRESHOLD = 8;

• 链表长度小于6 调整为列表 jdk1.8之后

  static final int UNTREEIFY_THRESHOLD = 6;
  

• 当链表长度大于8时，并且集合元素个数大于等于64时，调整成红黑树

  static final int MIN_TREEIFY_CAPACITY = 64;
  

• 哈希表中的数组

  transient Node<K,V>[] table;
  

• 元素个数

  transient int size;
  

• 总结：

  • 刚创建hashmap之后没有添加元素table = 0 ，size = 0 目的 ：节省空间
  • HashMap刚创建时，table是null，为了节省空间，当添加第一个元素时，table容量调整为16
  • 当元素个数大于阈值（16*0.75 = 12）时，会进行扩容，扩容后大小为原来的2倍，目的是减少调整元素的个数
  • jdk1.8 当每个链表长度大于8，并且元素个数大于等于64时，会调整为红黑树，目的是提高执行效率
  • jdk1.8 当链表长度小于6时，调整成链表
  • jdk1.8 之前，链表是头插入，jdk1.8以后是尾插入

Hashtable 和 Properties

• Hashtable：

  • JDK1.0版本，线程安全，运行效率慢；不允许null作为key或是value。

  • 初始容量11，加载因子0.75。

    这个集合在开发过程中已经不用了，稍微了解即可

• Propertise：

  • Hashtable的子类，要求key和value都是String。通常用于配置文件的读取。
  • 它继承了Hashtable的方法，与流关系密切，此处不详解。

TreeMap 的使用

• 实现了SortedMap接口（是Map的子接口），可以对key自动排序

• /**
   * TreeMap的使用
   *存储结构：红黑树
   */
  
  public class Demo03 {
      public static void main(String[] args) {
          TreeMap<Student, String> treeMap = new TreeMap<>();
          //        添加元素
          Student s1 = new Student("孙悟空",111);
          Student s2 = new Student("猪八戒",222);
          Student s3 = new Student("沙和尚",333);
          treeMap.put(s1,"北京");
          treeMap.put(s2,"上海");
          treeMap.put(s3,"深圳");
          treeMap.put(new Student("沙和尚",333),"南京");
          System.out.println(treeMap.size());
          System.out.println(treeMap.toString());
  //        删除
  //        treeMap.remove(new Student("沙和尚",333));
  //        System.out.println(treeMap.size());
  //        遍历
  //        1.使用KetSet
          for (Student key : treeMap.keySet()) {
              System.out.println(key+"------"+treeMap.get(key));
  
          }
          for (Map.Entry<Student, String> entry : treeMap.entrySet()) {
              System.out.println(entry.getKey()+"-----------"+entry.getValue());
  
          }
  //        判断
          System.out.println(treeMap.containsKey(new Student("沙和尚",333)));
  
      }
  }
  

•     @Override
      public int compareTo(Student o) {
          int n2 = this.stuNo-o.getStuNo();
          return n2;
      }
  

Collections 工具类

• 概念：集合工具类，定义了除了存取以外的集合常用方法。

• 方法：

  • public static void reverse(List<?> list)//反转集合中元素的顺序
  • public static void shuffle(List<?> list)//随机重置集合元素的顺序
  • public static void sort(List<T> list)//升序排序（元素类型必须实现Comparable接口）

• /**
   * 演示Collections工具类的使用
   */
  
  public class Demo04 {
      public static void main(String[] args) {
          ArrayList<Integer> list = new ArrayList<>();
          list.add(20);
          list.add(5);
          list.add(12);
          list.add(30);
          list.add(6);
  //        排序
          System.out.println("排序之前："+list.toString());
          Collections.sort(list);
          System.out.println("排序之后："+list.toString());
  
  //        binarySearch 二分查找
          int i = Collections.binarySearch(list, 20);
          System.out.println(i);
  
  //        copy 复制
          ArrayList<Integer> dest = new ArrayList<>();
          for (int k = 0;k<list.size();k++){
              dest.add(0);
          }
          Collections.copy(dest,list);
          System.out.println(dest.toString());
  //        reverse 反转
          Collections.reverse(list);
          System.out.println("反转之后："+list);
  //        shuffle 打乱
          Collections.shuffle(list);
          System.out.println("打乱之后："+list);
  
  //        补充：list转成数组
          Integer[] arr = list.toArray(new Integer[0]);
          System.out.println(arr.length);
          System.out.println(Arrays.toString(arr));
  
  //        数组转成集合
          String[] names = {"张三","李四","王五"};
  //        受限集合 不能添加或者删除
          List<String> list2 = Arrays.asList(names);
          System.out.println(list2);
  //        把基本类型数组转成集合时，需要修改类型为包装类
          Integer[] nums = {100,200,300,400,500};
          List<Integer> list3 = Arrays.asList(nums);
          System.out.println(list3);
  
  
      }
  }