哈希表
哈希表是一个集合，根据值来做key，或者根据内存地址来做key。主要有HashSet和HashMap，增删改查时间按复杂度都是O（1），HashSet保存的只有key，而HashMap保存的是key-value这样一个键值对。哈希表默认去重，在key范围可控的情况下，可用数组来代替哈希表结构。
哈希表一般是根据值来作key，因此各种操作也是根据值来进行
// 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);
// true
System.out.println(set.contains("Hello"));
// true
System.out.println(set.contains(str2));
HashMap<Integer, Integer> map2 = new HashMap<>();
map2.put(56, 7285);
map2.put(34, 3671263);
map2.put(17, 716311);
map2.put(34, 1263161);// 新加入的会覆盖之前相同的
// 1263161
System.out.println(map2.get(34));
而如果是我们自己内部定义的类，会按照内存地址作key
public static class Student {
public int age;
public String name;
public Student(int a, String b) {
age = a;
name = b;
}
}
Student s1 = new Student(17, "张三");
Student s2 = new Student(17, "张三");
HashMap<Student, String> map3 = new HashMap<>();
map3.put(s1, "这是张三");
// true
System.out.println(map3.containsKey(s1));
// false
System.out.println(map3.containsKey(s2));
map3.put(s2, "这是另一个张三");
// 2
System.out.println(map3.size());
// 这是张三
System.out.println(map3.get(s1));
// 这是另一个张三
System.out.println(map3.get(s2));
有序表
与哈希表类似，不过数据加入有序表之后会根据key进行排序。有序表的底层是红黑树，因此对数据的操作时间复杂度为O（logn）
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(8, "这是8");
// 最小值 1
System.out.println(treeMap.firstKey());
// 最大值 8
System.out.println(treeMap.lastKey());
// TreeMap中，所有的key，<= 4且最近的key，3
System.out.println(treeMap.floorKey(4));
// TreeMap中，所有的key，>= 4且最近的key，5
System.out.println(treeMap.ceilingKey(4));
TreeSet<Integer> set = new TreeSet<>();
set.add(3);
set.add(3);
set.add(4);
set.add(4);
// 2
System.out.println("有序表大小 : " + set.size());
而堆结构就是不去重的，底层是优先级队列，Java中默认是小根堆，如果要构造大根堆，需要自定义比较器
PriorityQueue<Integer> heap1 = new PriorityQueue<>();
heap1.add(3);
heap1.add(3);
heap1.add(4);
heap1.add(4);
// 4
System.out.println("堆大小 : " + heap1.size());
while (!heap1.isEmpty()) {
// 每次弹出堆顶元素 3 3 4 4
System.out.println(heap1.poll());
}
比较器
有如下一个Employee类及其实例，想实现按照年龄升序排序
public static class Employee {
public int company;
public int age;
public Employee(int c, int a) {
company = c;
age = a;
}
}
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 };
// 比较器
public static class EmployeeComparator implements Comparator<Employee> {
@Override
public int compare(Employee o1, Employee o2) {
// 任何比较器都默认
// 如果返回负数认为o1的优先级更高
// 如果返回正数认为o2的优先级更高
// 任何比较器都是这样，所以利用这个设定，可以定制优先级怎么确定，也就是怎么比较
// 不再有大小的概念，就是优先级的概念
return o1.age - o2.age;
}
}
Arrays.sort(arr, new EmployeeComparator());
for (Employee e : arr) {
System.out.println(e.company + " , " + e.age);
}
输出结果为
4 , 19
3 , 23
2 , 27
1 , 35
3 , 55
1 , 60
上述比较器也可以通过lambda表达式，得到同样的效果
Arrays.sort(arr, (a, b) -> a.age - b.age);
for (Employee e : arr) {
System.out.println(e.company + " , " + e.age);
}
也可以使用lambda表达式实现更加复杂的排序
// 所有员工，先按照谁的公司编号小，谁在前；如果公司编号一样，谁年龄小谁在前
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);
}
输出结果为
1 , 35
1 , 60
2 , 27
3 , 23
3 , 55
4 , 19
由上面所知，有序表内部存储的数据是有序的，因此如果是自己内部定义的类，一定要写比较器。
