java基础 之 集合与栈的使用（三）

前文回顾：
戳这里 → java基础 之 集合与栈的使用（一）
戳这里 → java基础 之 集合与栈的使用（二）

阅读指南：第一遍可以先忽略代码~
代码可以直接复制粘贴~

Map接口

（一）实现类：HashMap

特点

• HashMap底层是链表+数组，jdk8以加入了红黑树
• HashMap存储是key-valuel类型的数据
• key不允许重复（重复时会被覆盖），value值允许重复
• 数据存储无序
• key和value都允许为空，但是只能有一个空的key
• 线程不安全

HashMap集合的一些方法

import java.util.HashMap;public class TestHashMap {public static void main(String[] args) {HashMap hashMap = new HashMap<>();HashMap newHashMap = new HashMap<>();// .put(K V value) 将键（key）/值（value）映射存放到Map集合中,无返回值hashMap.put("hello",123);hashMap.put("world",234);hashMap.put("Hello",123);hashMap.put("hello",123);newHashMap.put("aaa","111111");newHashMap.put("bbb","222222");newHashMap.put("ccc","3333333");// .get(Object key) 返回指定键所映射的值，没有该key对应的值则返回null，即获取key对应的value。System.out.println(hashMap.get("hello"));  // 输出：123System.out.println(hashMap.get("hello1"));  // 输出：null// . size() 返回Map集合中数据数量，准确说是返回key-value的组数。System.out.println(hashMap.size());     // 输出：3// isEmpty () 判断Map集合中是否有数据，如果没有则返回true，否则返回falseSystem.out.println(hashMap.isEmpty());     // 输出：false// remove(Object key) 删除Map集合中键为key的数据并返回其所对应value值。hashMap.remove("hello");  // 无返回值System.out.println("------");// containsKey(Object key) Hashmap判断是否含有keySystem.out.println(hashMap.containsKey("hello"));  // 输出：false// containsValue(Object value) Hashmap判断是否含有value：System.out.println(hashMap.containsValue(123));  // 输出：true// Hashmap添加另一个同一类型的map下的所有数据hashMap.putAll(newHashMap);  // 无返回数System.out.println(hashMap);// Hashmap替换这个key的valueSystem.out.println(hashMap.put("aaa","aaa0000"));  // 替换后返回被替换的值System.out.println(hashMap);// clear() 清空Map集合'hashMap.clear();  // 无返回值}
}

多说几句：

1、key只能使用基本数据类型（int，char…）的封装类（Integer，String…）
2、jdk1.8 之前 HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突。
3、jdk1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（一般为 8 ）并且当前数组的长度大于 64 时，此时此索引位置上的所有数据改为使用红黑树存储。
4、插入、查找和删除操作的平均时间复杂度是O(1)，但在最坏情况下可能会达到O(n)。

（二）实现类： TreeMap

特点

• TreeMap是有序的key-value集合，是通过红黑树来实现的

• 无序（元素顺序与添加顺序不一致），且不允许重复

• TreeMap的key是有序的

• 默认会对键进行排序，所以必须实现自然排序和定制排序中的一种

  自然排序：TreeMap的所有key必须实现Comparable接口，且所有的key应该是同一类的对象，否则会抛出ClassCastException（类转换异常）

  定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。此时不需要key实现Comparable接口

• 若使用自定义类作为key，所属的类需重写equals()和hashCode()，当equals()的返回为true时，compareTo()返回应为0

• 同一个TreeMap对象中添加的key必须是相同的类型（因为要求key是具有可比性的对象）

【自然排序】代码

// 创建一个Student类，包含name（姓名）、age（年龄）和sno（学号）三个属性
public class Student implements Comparable{String name;  // 姓名Integer age;  // 年龄String sno;   // 学号// 构造函数public Student(String name, Integer age, String sno) {this.name = name;this.age = age;this.sno = sno;}// 重写compareto方法。@Overridepublic int compareTo(Object o) {if(o instanceof Student){Student s = (Student) o;int c_name= this.name.compareTo(s.name);int c_sno = this.sno.compareTo(s.sno);if(c_name!=0){  // 先按照名称排序return this.sno.compareTo(s.name);}else if(c_sno!=0){  // 名称相同按照学号排序return this.sno.compareTo(s.sno);}else { // 名称、学号相同，按照年龄排序return this.age.compareTo(s.age);}}return 0;}// 方便打印显示@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +", sno='" + sno + '\'' +'}';}
}

import java.util.TreeMap;
public class TestHashMap {public static void main(String[] args) {TreeMap treeMap = new TreeMap();treeMap.put(new Student("xiaoming",23,"1233456"),1234);treeMap.put(new Student("xiaoming",23,"1233451"),1234);treeMap.put(new Student("xiaoa",12,"1233451"),1234);System.out.println(treeMap);}
}
-------------打印结果----------------
{Student{name='xiaoa', age=12, sno='1233451'}=1234, Student{name='xiaoming', age=23, sno='1233451'}=1234, Student{name='xiaoming', age=23, sno='1233456'}=1234}

【定制排序】代码

// 创建一个Person类，注意该类不需要实现Comperator接口
import java.util.Comparator;public class Person{String name;  // 姓名Integer age;  // 年龄String phone; // 性别public String getName() {return name;}public void setName(String name) {this.name = name;}public Integer getAge() {return age;}public void setAge(Integer age) {this.age = age;}public String getPhone() {return phone;}public void setPhone(String sex) {this.phone = phone;}public static final Comparator<Person> COMPARATOR = new Comparator<Person>() {@Overridepublic int compare(Person o1, Person o2) {int p_name= o1.getName().compareTo(o2.getName());  // 按姓名比较int p_age = o1.getAge().compareTo(o2.getAge());   // 按年龄int p_phone = o1.getPhone().compareTo(o2.getPhone());   // 按手机号比较if(p_name!=0){  // 先按照名称排序return p_name;}else if(p_age!=0){  // 名称相同按照年龄return p_age;}else { // 名称、年龄相同，按照手机号码排序return p_phone;}}};public Person(String name, Integer age, String phone) {this.name = name;this.age = age;this.phone = phone;}@Overridepublic String toString() {return "Person{" +"name='" + name + '\'' +", age=" + age +", phone='" + phone + '\'' +'}';}
}

import java.util.TreeMap;public class TestHashMap {public static void main(String[] args) {TreeMap treeMap = new TreeMap(Person.COMPARATOR);treeMap.put(new Person("xiaoming",23,"1233456"),1234);treeMap.put(new Person("xiaoming",23,"1233451"),1234);treeMap.put(new Person("xiaoa",12,"1233451"),1234);System.out.println(treeMap);}
}
-------打印结果？自己敲或者复制代码自己运行吧，在此偷个懒了.....

1、自然排序需要实现Comparable接口并重写compareTo方法，不需要写get()和set()方法
2、定制排序不需要实现Comparable接口，需要通过匿名内部类生成一个静态常量COMPARATOR、getter()、setter()方法。同时在生成TreeMap对象时，需要使用创建的
COMPARATOR。

TreeMap集合的一些方法

public class TestHashMap {public static void main(String[] args) {TreeMap treeMap = new TreeMap(Person.COMPARATOR);Person p1 = new Person("xiaoming",23,"1233455");Person p2 = new Person("xiaoming",23,"1233451");treeMap.put(p1,1234);treeMap.put(p2,1234);treeMap.put(new Person("xiaoa",12,"1233454"),1234);Person p4 = new Person("xiaoz",12,"1233452");treeMap.put(p4,1234);treeMap.put(new Person("xiaoy",22,"1233453"),1234);Person example = new Person("xiaon",23,"1233456");// 返回指定的Key大于或等于的最小值的元素，如果没有，则返回nullEntry K = treeMap.ceilingEntry(example);// 返回小于等于key的最大Key的元素Entry big = treeMap.floorEntry(example);// 返回指定的Key大于或等于的最小值的Key，如果没有，则返回nullObject obj = treeMap.ceilingKey(example);// 返回小于等于key的最大Key的keyPerson bkey = (Person) treeMap.floorKey(example);// 返回集合的副本TreeMap cloneMap = (TreeMap) treeMap.clone();cloneMap.put(p1,"p1-6666");// 返回集合的全部Key，并且是逆序的NavigableSet navigableSet = treeMap.navigableKeySet();// 把集合逆序返回NavigableMap maps = treeMap.descendingMap();// 返回集合中最小的值、最大的值Entry thLittle = treeMap.firstEntry();Entry thBig = treeMap.lastEntry();// 返回集合中最小的key、最大的keyPerson littleKey = (Person) treeMap.firstKey();Person bigKey = (Person) treeMap.lastKey();// 返回Key小于参数的所有元素SortedMap map = treeMap.headMap(example);// 当inclusive为true时，就是返回Key小于等于toKey的所有元素NavigableMap mapTrue = treeMap.headMap(example,true);//返回Key大于key的所有元素、keyEntry entry = treeMap.higherEntry(example);Person person = (Person) treeMap.higherKey(example);// 截取集合中Key从fromKey到toKey的元素，否是截取他们本身，取决于true或者falseNavigableMap subs = treeMap.subMap(example,false,p4,false);// 截取集合中Key从fromKey到toKey的元素，包括fromKey，不包括toKeySortedMap sortedMap = treeMap.subMap(p1,p4);// 截取Key大于等于fromKey的所有元素SortedMap mp = treeMap.tailMap(p1);// 当inclusive为true时，截取Key大于等于fromKey的所有元素，否则截取Key大于fromKey的所有元素SortedMap s1 = treeMap.tailMap(p1,false);// 删除key最小的元素、最大元素Entry delLest = treeMap.pollFirstEntry();Entry delLast = treeMap.pollLastEntry();}
}

key因为是自定义变量的，所以上边用example或者p1，p2等来代替了
结果就自己打印出来看看吧

HashMap 和 TreeMap的区别

• 排序

  • HashMap不保证元素的顺序，迭代顺序也是不确定的
  • TreeMap 基于红黑树的实现，会根据键的自然排序或自定义的比较器对键进行排序。TreeMap保证了元素的顺序，可以按照键的升序进行遍历。

• 时间复杂度：

  • HashMap的查找、插入和删除操作的平均时间复杂度为O(1)
  • TreeMap的查找、插入和删除操作的时间复杂度为O(log n)，其中n为元素的数量

• 性能

  • HashMap提供了常数时间的性能（基于哈希表）
  • TreeMap提供了对数时间的性能（基于红黑树）