哈希表、有序表和比较器的用法

哈希表

哈希表是一个集合,根据值来做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

由上面所知,有序表内部存储的数据是有序的,因此如果是自己内部定义的类,一定要写比较器。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容