《Java 核心技术 卷1》 笔记 第13章 集合（6）优先队列[堆] 与哈希映射

 13.2.7 优先级排列（堆）

插入时进行顺序调整的队列

[3,2,1,5,4]插入过程：

它的特征是：上方元素小，下方元素大，左右元素无顺序规律，每次插入过程只挪动一条没有分叉的自下而上的路径

再看看[3,2,1,5,4]删除过程：

它的特征是：上方元素小，下方元素大，左右元素无顺序规律，每次选择下方元素中较小的那个进行补位，每次只移动一条没有分叉的自下而上的路径

所以堆插入时的时间复杂度是O(logn)，删除时的时间复杂度也是O(logn)

作者例子：

❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤

import java.util.*; public class Main {    public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); pq.add(new GregorianCalendar(1906,Calendar.DECEMBER,9)); pq.add(new GregorianCalendar(1815,Calendar.DECEMBER,10)); pq.add(new GregorianCalendar(1903,Calendar.DECEMBER,3)); pq.add(new GregorianCalendar(1910,Calendar.JUNE,22));  System.out.println("Iterating over elements..."); for(GregorianCalendar date:pq) System.out.println(date.get(Calendar.YEAR)); System.out.println("Removing elements..."); while (!pq.isEmpty())     System.out.println(pq.remove().get(Calendar.YEAR));    } }

❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤

运行结果：

🚗🚓🚕🛺🚙🚌🚐🚎🚑🚒🚚🚛🚜🚘🚔🚖🚍🦽🦼🛹🚲🛴🛵🏍

🚗🚓🚕🛺🚙🚌🚐🚎🚑🚒🚚🚛🚜🚘🚔🚖🚍🦽🦼🛹🚲🛴🛵🏍

小总结：

优先队列和普通队列的对比：

相同点：优先队列添加移除的代码书写方式和普通队列相同

不同点：优先队列添加过程中会有一个排序，每次移除的都是比较中的最小/大值，普通队列添加时是在队尾，移除时在队头不存在值的比较。

 13.2.8 哈希映射

注意：原标题为【映射表】，但是个人觉得使用“映射表”会让人很容易忽略 HashMap 和 TreeMap 的键不能重复的问题

啥是哈希映射呢？

（1）有键值对。 比如 姓名：张三，姓名 就是键，张三 就是值

（2）可通过键来查找对应的值，比如你在表里记录下了 姓名：张三，就可以通过姓名这个键去找对应的值

（3）哈希键值对的键不可重复，重复时会进行覆盖。比如 姓名：张三，结果张三改名了，就把张三改成张五了，那就进行覆盖 姓名：张五

操作：

（1）添加：map.put(key,value);

（2）移除：map.remove(key);

（3）获取键对应的值：map.get(key);

（4）获取键集合：map.keySet();

（5）获取值集合：map.values();

（6）获取所有元素(TreeMap按键有序，HashMap无序)：

for(Map.Entry keyValue:map.entrySet()){

    K key = keyValue.getKey();//键

    V value = keyValue.getValue();//值

}

作者示例：

MapTest.java

❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤

public class MapTest {    public static void main(String[] args) { Map staff = new HashMap(); staff.put("144-25-5464", new Employee("Amy Lee")); staff.put("567-24-2546", new Employee("Harry Hacker")); staff.put("157-62-7935", new Employee("Gary Cooper")); staff.put("456-62-5527", new Employee("Francesca Cruz")); System.out.println(staff);  staff.remove("567-24-2546", new Employee("Francesca Miller"));   System.out.println(staff.get("157-62-7935"));  for(Map.Entry entry:staff.entrySet()){     String key = entry.getKey();     Employee value = entry.getValue();     System.out.println("key="+key+",value="+value); }     }}

❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤

Employee.java

❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤

public class Employee {    private String name;    private double salary;     public Employee(String name){ this.name = name; salary  =0;    }    public String getName() { return name;    }     public void setName(String name) { this.name = name;    }     public double getSalary() { return salary;    }     public void setSalary(double salary) { this.salary = salary;    }     @Override    public String toString() { return "{"+name+","+salary+"}";    }}

❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤❤🧡💛💚💙💜🤎🖤

运行结果：

🚗🚓🚕🛺🚙🚌🚐🚎🚑🚒🚚🚛🚜🚘🚔🚖🚍🦽🦼🛹🚲🛴🛵🏍

🚗🚓🚕🛺🚙🚌🚐🚎🚑🚒🚚🚛🚜🚘🚔🚖🚍🦽🦼🛹🚲🛴🛵🏍

小总结：

（1）哈希保存的是键值对

（2）哈希可进行键来获取值，移除，添加键值对，遍历等操作

（3）哈希的键值不能重复

总结：

（1）优先队列内部程树形排列，可通过和普通队列一样的方式进行添加删除

（2）优先队列插入过程中会产生元素移动，造成顶端为最大/最小值，从而产生移除时按照顺序的效果

（3）哈希表可用于保存键值对

（4）哈希表中保留的键值对中键不能重复

（5）哈希可进行键值对添加，获取键的值，移除键，遍历循环操作

相关内容：选择 《Java核心技术 卷1》查找相关笔记

评论🌹点赞👍收藏✨关注👀，是送给作者最好的礼物，愿我们共同学习，一起进步

如果对作者发布的内容感兴趣，可点击下方关注公众号 钰娘娘知识汇总 查看更多作者文章哦！