知识文档站

Appearance

哈希表、有序表、比较器

哈希表 ​

HashSet、HashMap 二者取值都是 O（1）的操作 ​

HashSet：存储无序、不重复的元素，可以存放空值，且只能有一个 null ​

HashMap：key - value 的存储结构，key 不能重复，且 key 允许为空，当添加元素的 key 在 map 中已存在，则会新的 value 覆盖原来的 value ​

key -value 的结构在一定程度上可以采用数组实现 ​

java
package class026;

import java.util.HashMap;
import java.util.HashSet;

public class Code01_HashSetAndHashMap {

	public static void main(String[] args) {
		// Integer、Long、Double、Float
		// Byte、Short、Character、Boolean
		// String等都有这个特征
		String str1 = new String("Hello");
		String str2 = new String("Hello");
		// false，因为不同的内存地址
		System.out.println(str1 == str2);
		// true，因为它们的值是相同的
		System.out.println(str1.equals(str2));

		HashSet<String> set = new HashSet<>();
		set.add(str1);
		System.out.println(set.contains("Hello"));
		System.out.println(set.contains(str2));
		set.add(str2);
		System.out.println(set.size());
		set.remove(str1);
		set.clear();
		System.out.println(set.isEmpty());

		System.out.println("===========");

		HashMap<String, String> map1 = new HashMap<>();
		map1.put(str1, "World");
		System.out.println(map1.containsKey("Hello"));
		System.out.println(map1.containsKey(str2));
		System.out.println(map1.get(str2));
		System.out.println(map1.get("你好") == null);
		map1.remove("Hello");
		System.out.println(map1.size());
		map1.clear();
		System.out.println(map1.isEmpty());

		System.out.println("===========");

		// 一般在笔试中，未必需要申请哈希表
		HashMap<Integer, Integer> map2 = new HashMap<>();
		map2.put(56, 7285);
		map2.put(34, 3671263);
		map2.put(17, 716311);
		map2.put(24, 1263161);
		// 上面的map2行为，可以被如下数组的行为替代
		int[] arr = new int[100];
		arr[56] = 7285;
		arr[34] = 3671263;
		arr[17] = 716311;
		arr[24] = 1263161;
		// 哈希表的增、删、改、查，都可以被数组替代，前提是key的范围是固定的、可控的
		System.out.println("在笔试场合中哈希表往往会被数组替代");

		System.out.println("===========");
		Student s1 = new Student(17, "张三");
		Student s2 = new Student(17, "张三");
		HashMap<Student, String> map3 = new HashMap<>();
		map3.put(s1, "这是张三");
		System.out.println(map3.containsKey(s1));
		System.out.println(map3.containsKey(s2));
		map3.put(s2, "这是另一个张三");
		System.out.println(map3.size());
		System.out.println(map3.get(s1));
		System.out.println(map3.get(s2));
	}

	public static class Student {
		public int age;
		public String name;

		public Student(int a, String b) {
			age = a;
			name = b;
		}
	}

}

有序表 ​

TreeSet 和 TreeMap 原理一样，有无伴随数据的区别，元素是有序的，可以在创建对象的时候可以传入比较器，指定元素的有序规则 ​

增、删、改、查 + 很多和有序相关的操作（floor、ceilling 等），时间为 O（log n） ​

有序表比较相同的东西会去重，如果不想去重就加入更多的比较策略（比较器定制） ​

堆不会去重，PriorityQueue 默认小根堆，如果要大根堆，传入定制的比较器即可 ​

有序表在 Java 里是用红黑树实现的，AVL 树、SB 树、替罪羊树、Treap、Splay、跳表等等很多结构都可实现同样功能 ​

java
package class026;

import java.util.PriorityQueue;
import java.util.TreeMap;
import java.util.TreeSet;

public class Code02_TreeSetAndTreeMap {

	public static void main(String[] args) {
		// 底层红黑树
		TreeMap<Integer, String> treeMap = new TreeMap<>();
		treeMap.put(5, "这是5");
		treeMap.put(7, "这是7");
		treeMap.put(1, "这是1");
		treeMap.put(2, "这是2");
		treeMap.put(3, "这是3");
		treeMap.put(4, "这是4");
		treeMap.put(8, "这是8");

		System.out.println(treeMap.containsKey(1));
		System.out.println(treeMap.containsKey(10));
		System.out.println(treeMap.get(4));
		treeMap.put(4, "张三是4");
		System.out.println(treeMap.get(4));

		treeMap.remove(4);
		System.out.println(treeMap.get(4) == null);

		System.out.println(treeMap.firstKey());
		System.out.println(treeMap.lastKey());
		// TreeMap中，所有的key，<= 4且最近的key是什么
		System.out.println(treeMap.floorKey(4));
		// TreeMap中，所有的key，>= 4且最近的key是什么
		System.out.println(treeMap.ceilingKey(4));

		System.out.println("========");

		TreeSet<Integer> set = new TreeSet<>();
		set.add(3);
		set.add(3);
		set.add(4);
		set.add(4);
		System.out.println("有序表大小 : " + set.size());
		while (!set.isEmpty()) {
			System.out.println(set.pollFirst());
			// System.out.println(set.pollLast());
		}

		// 堆，默认小根堆、如果要大根堆，定制比较器！
		PriorityQueue<Integer> heap1 = new PriorityQueue<>();
		heap1.add(3);
		heap1.add(3);
		heap1.add(4);
		heap1.add(4);
		System.out.println("堆大小 : " + heap1.size());
		while (!heap1.isEmpty()) {
			System.out.println(heap1.poll());
		}

		// 定制的大根堆，用比较器！
		PriorityQueue<Integer> heap2 = new PriorityQueue<>((a, b) -> b - a);
		heap2.add(3);
		heap2.add(3);
		heap2.add(4);
		heap2.add(4);
		System.out.println("堆大小 : " + heap2.size());
		while (!heap2.isEmpty()) {
			System.out.println(heap2.poll());
		}

	}

}

比较器 ​

实现 Comparator 接口，重写 compare 方法实现自定义排序规则，这里可以用 lamda 表达式优化代码，避免冗余 ​

java
package class026;

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;

public class Code03_Comparator {

	public static class Employee {
		public int company;
		public int age;

		public Employee(int c, int a) {
			company = c;
			age = a;
		}
	}

	public static class EmployeeComparator implements Comparator<Employee> {
		@Override
		public int compare(Employee o1, Employee o2) {
			// 任何比较器都默认
			// 如果返回 <负数> 认为 o1 的优先级更高
			// 如果返回 <正数> 认为 o2 的优先级更高
			// 任何比较器都是这样，所以利用这个设定，可以定制优先级怎么确定，也就是怎么比较
			// 不再有大小的概念，就是优先级的概念
			return o1.age - o2.age;
		}
	}

	public static void main(String[] args) {
		Employee s1 = new Employee(2, 27);
		Employee s2 = new Employee(1, 60);
		Employee s3 = new Employee(4, 19);
		Employee s4 = new Employee(3, 23);
		Employee s5 = new Employee(1, 35);
		Employee s6 = new Employee(3, 55);
		Employee[] arr = { s1, s2, s3, s4, s5, s6 };
		Arrays.sort(arr, new EmployeeComparator());
		for (Employee e : arr) {
			System.out.println(e.company + " , " + e.age);
		}

		System.out.println("=====");

        // 年龄降序排序（从大到小）
		Arrays.sort(arr, (a, b) -> b.age - a.age);
		for (Employee e : arr) {
			System.out.println(e.company + " , " + e.age);
		}

		System.out.println("=====");
		// 所有员工，先按照谁的公司编号小，谁在前；如果公司编号一样，谁年龄小谁在前
		Arrays.sort(arr, (a, b) -> a.company != b.company ? (a.company - b.company) : (a.age - b.age));
		for (Employee e : arr) {
			System.out.println(e.company + " , " + e.age);
		}

        // 新添加的员工按照年龄升序的排序规则排列在 TreeSet 中
		TreeSet<Employee> treeSet1 = new TreeSet<>(new EmployeeComparator());
		for (Employee e : arr) {
			treeSet1.add(e);
		}
		System.out.println(treeSet1.size());

		// 前面已经添加过了 Employee(2, 27) 这个对象，这里会去重
		treeSet1.add(new Employee(2, 27));
		System.out.println(treeSet1.size());

		System.out.println("===");

		// 如果不想去重，就需要增加更多的比较
		// 比如对象的内存地址、或者如果对象有数组下标之类的独特信息
		TreeSet<Employee> treeSet2 = new TreeSet<>((a, b) -> a.company != b.company ? (a.company - b.company)
				: a.age != b.age ? (a.age - b.age) : a.toString().compareTo(b.toString()));
		for (Employee e : arr) {
			treeSet2.add(e);
		}
		System.out.println(treeSet2.size());

		// 不会去重
		treeSet2.add(new Employee(2, 27));
		System.out.println(treeSet2.size());

		System.out.println("===");

		// PriorityQueue 不会去重，不再展示了

		// 字典序
		String str1 = "abcde";
		String str2 = "ks";
		System.out.println(str1.compareTo(str2));
		System.out.println(str2.compareTo(str1));
	}

}

字典序 ​

基本介绍 ​

compareTo 方法，返回字典序的差值 ​

当长度相同时候，以第一个字母的相对位置比较 ​

当长度不同时，可以先对短的补长度（可以先补 0，这是一种方法，并不是真的需要补），当二者长度相同时候，以第一个字母的相对位置比较 ​

Tip

（1）str1.compareTo(str2) < 0：说明 str1 的字典序 < str2 的字典序 ​

（2）str2.compareTo(str1) > 0：说明 str2 的字典序 > str1 的字典序 ​

java
String str1 = "abcde";
String str2 = "ks";
// 长度不同 --> 补 0
// abcde ， ks000
// a k 的字典序相差 10
System.out.println(str1.compareTo(str2)); // -10
System.out.println(str2.compareTo(str1)); // 10

比较规则 ​

（1） 如果长度相同，并且每个个字符也相同，就返回 0 ​

java
String str1 = "java";
String str2 = "java";
System.out.println(str1.compareTo(str2));

// 输出结果
0

（2）如果长度相同或者不相同，但是在比较时，可以区分大小 ​

java
String str1 = "javahahaha";
String str2 = "haha";
System.out.println(str1.compareTo(str2));

// 输出结果：2

解释：j 和 h 在字母表中的顺序相差 2

（3） 如果前面的部分都相同，就返回长度之差（ str1 . len - str2 . len ） ​

java
String str1 = "javaha";
String str2 = "java";
System.out.println(str1.compareTo(str2));

// 输出结果
2

解释：多了两个字符 ha

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1