java HashMap与TreeMap总结-阿南达文事网

java HashMap与TreeMap总结

1、HashMap vs TreeMap

2、HashMap简介

3、Java HashMap 与TreeMap方法

4、HashMap例题 2019蓝桥杯B组JAVA 试题G: 外卖店优先级

5、TreeMap例题统计词频

6、java面试题之HashMap和TreeMap

1、HashMap vs TreeMap

Map：在数组中是通过数组下标来对其内容进行索引的，而Map是通过对象来对对象进行索引的，用来索引的对象叫键key，其对应的对象叫值value；

1、HashMap是通过hashcode()对其内容进行快速查找的；HashMap中的元素是没有顺序的；

TreeMap中所有的元素都是有某一固定顺序的，如果需要得到一个有序的结果，就应该使用TreeMap；

2、HashMap和TreeMap都不是线程安全的；

3、HashMap继承AbstractMap类；覆盖了hashcode() 和equals() 方法，以确保两个相等的映射返回相同的哈希值；

TreeMap继承SortedMap类；他保持键的有序顺序；

4、HashMap：基于hash表实现的；使用HashMap要求添加的键类明确定义了hashcode() 和equals() （可以重写该方法）；为了优化HashMap的空间使用，可以调优初始容量和负载因子；

TreeMap：基于红黑树实现的；TreeMap就没有调优选项，因为红黑树总是处于平衡的状态；

5、HashMap：适用于Map插入，删除，定位元素；

TreeMap：适用于按自然顺序或自定义顺序遍历键（key）；

2、HashMap简介

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。
HashMap 是无序的，即不会记录插入的顺序。
HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。

HashMap 类位于 java.util 包中，使用前需要引入它，语法格式如下：

import java.util.HashMap; // 引入 HashMap 类

创建一个 HashMap 对象 Sites，整型（Integer）的 key 和字符串（String）类型的 value：

HashMap<Integer, String> Sites = new HashMap<Integer, String>();

创建一个 HashMap 对象的数组a

		HashMap<Integer, Integer> a[]=new HashMap[t+1];for(int i=0;i<=t;i++) {a[i]=new HashMap<Integer, Integer>();}

3、Java HashMap 与TreeMap方法

Java HashMap 常用方法列表如下：（TreeMap方法与HashMap 方法大致一样）

方法	描述
clear()	删除 hashMap 中的所有键/值对
clone()	复制一份 hashMap
isEmpty()	判断 hashMap 是否为空
size()	计算 hashMap 中键/值对的数量
put()	将键/值对添加到 hashMap 中
putAll()	将所有键/值对添加到 hashMap 中
putIfAbsent()	如果 hashMap 中不存在指定的键，则将指定的键/值对插入到 hashMap 中。
remove()	删除 hashMap 中指定键 key 的映射关系
containsKey()	检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsValue()	检查 hashMap 中是否存在指定的 value 对应的映射关系。
replace()	替换 hashMap 中是指定的 key 对应的 value。
replaceAll()	将 hashMap 中的所有映射关系替换成给定的函数所执行的结果。
get()	获取指定 key 对应对 value
getOrDefault()	获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
forEach()	对 hashMap 中的每个映射执行指定的操作。
entrySet()	返回 hashMap 中所有映射项的集合集合视图。
keySet()	返回 hashMap 中所有 key 组成的集合视图。
values()	返回 hashMap 中存在的所有 value 值。
merge()	添加键值对到 hashMap 中
compute()	对 hashMap 中指定 key 的值进行重新计算
computeIfAbsent()	对 hashMap 中指定 key 的值进行重新计算，如果不存在这个 key，则添加到 hasMap 中
computeIfPresent()	对 hashMap 中指定 key 的值进行重新计算，前提是该 key 存在于 hashMap 中。

4、HashMap例题 2019蓝桥杯B组JAVA 试题G: 外卖店优先级

oj：.php?id=1458

“饱了么”外卖系统中维护着N 家外卖店，编号1 N。每家外卖店都有一个优先级，初始时(0 时刻) 优先级都为0。每经过1 个时间单位，如果外卖店没有订单，则优先级会减少1，最低减
到0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加2。如果某家外卖店某时刻优先级大于5，则会被系统加入优先缓存中；如果优先级小于等于3，则会被清除出优先缓存。给定T 时刻以内的M 条订单信息，请你计算T 时刻时有多少外卖店在优
先缓存中。

【输入格式】
第一行包含3 个整数N、M 和T。以下M 行每行包含两个整数ts 和id，表示ts 时刻编号id 的外卖店收到一个订单。
【输出格式】输出一个整数代表答案。
【样例输入】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

【样例输出】
1

【样例解释】6 时刻时，1 号店优先级降到3，被移除出优先缓存；2 号店优先级升到6，加入优先缓存。所以是有1 家店(2 号) 在优先缓存中。

package javaB省赛2019;/*有个坑：
虽然优先级的减少和增加貌似是一起进行的，但是，容易出现一种特殊情况。
店家本来优先级为6…就是说店家在优先级内
如果第四天接到1个订单…店家此时优先级为4，但是不在优先队列内。
所以优先级的减少和增加应该分开操作，并且每次操作后都应该进行判断，此时是否应该存在于优先队列*/
import java.util.HashMap;
import java.util.Scanner;
public class G外卖店优先级 {@SuppressWarnings("unchecked")public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();int t=in.nextInt();//hashMap记录编号和订单数HashMap<Integer, Integer> a[]=new HashMap[t+1];for(int i=0;i<=t;i++) {a[i]=new HashMap<Integer, Integer>();}int ts,id;for(int i=0;i<m;i++) {//将m条订单添加到HashMapts=in.nextInt();id=in.nextInt();if(a[ts].containsKey(id)) {//订单数+1a[ts].put(id, a[ts].get(id)+1);}else {a[ts].put(id,1);}}int[] pri=new int[n+1];int[] last=new int[n+1];int[] score=new int[n+1];for(int i=0;i<=t;i++) {//枚举时间for(int j:a[i].keySet()) {//枚举外卖店score[j]=Math.max(score[j]-(i-last[j]-1), 0);//减去无订单的失分,但最小值为0//增减优先级分开判断的目的：防止当6->3->5时变成6->5而仍在队中if(score[j]>5&&pri[j]==0)pri[j]=1;  //判断是否入队else if(score[j]<4&&pri[j]==1)pri[j]=0;score[j]+=2*a[i].get(j);//加上当前外卖店的订单对应得分if(score[j]>5&&pri[j]==0)pri[j]=1;//判断是否入队last[j]=i;//记录最后一次有订单时间				}}for(int i=0;i<=n;i++){//最后时间t，需要再处理分数！！再判断一次是否会出队！score[i]=Math.max(score[i]-(t-last[i]),0);if(score[i]<4&&pri[i]==1){pri[i]=0;}}int ans=0;for(int i=0;i<=n;i++)ans+=pri[i];System.out.println(ans);}
}

5、TreeMap例题统计词频

package demo1;
import java.util.Scanner;
import java.util.TreeMap;
//题目：统计最多的词频，按字典序输出最多的单词和次数
//Five Little Monkeys Jumping on the Bed. It was bedtime. So five little monkeys took a bath. Five little Monkeys put on their pajamas.
//len<=1000
//output: five 3
public class Test2 {public static void main(String[] args) {Scanner in = new Scanner(System.in);String s=in.nextLine();String[] s1=s.split(" ");char last_ch;TreeMap<String,Integer> m=new TreeMap<>();for(int i=0;i<s1.length;i++) {s1[i]=s1[i].toLowerCase();last_ch=s1[i].toCharArray()[s1[i].length()-1];if(last_ch<'a'||last_ch>'z') {//非字符就去掉s1[i]=s1[i].substring(0, s1[i].length()-1);}}for(int i=0;i<s1.length;i++) {if(!m.containsKey(s1[i])) { //如果不存在，则存进去 比如   five:1m.put(s1[i],1);}else {  //如果存在 ，先找到 此key对应的 value值int value=m.get(s1[i]);m.put(s1[i], value+1);//覆盖前者的的key值，并且比前者多加一次}}for(String ss:m.keySet()) {System.out.println(ss+":"+m.get(ss));}int max=0;for(String ss:m.keySet()) {//查找最高频次max=Math.max(m.get(ss), max);}	for(String ss:m.keySet()) {//查找最高频次对应的单词if(m.get(ss)==max) {System.out.println(ss);System.out.println(max);break;}}}
}

6、java面试题之HashMap和TreeMap

1.HashMap和TreeMap的异同点？

相同点：

都是以key和value的形式存储；
key不可以重复；
都是线程不安全的；

不同点：

HashMap的key可以为空
TreeMap的key值是有序的（使用了红黑树的二叉树结构存储的Entry）

2.如何决定使用HashMap还是TreeMap？

HashMap基于散列桶（数组和链表）实现；TreeMap基于红黑树实现。
HashMap不支持排序；TreeMap默认是按照Key值升序排序的，可指定排序的比较器，主要用于存入元素时对元素进行自动排序。
HashMap大多数情况下有更好的性能，尤其是读数据。在没有排序要求的情况下，使用HashMap。

我的妈呀！服了！改了n遍，审核老是不让过啊啊啊啊，所以我决定文章末尾加上一些一些不相干的内容，大伙勿在意。。。可自行跳过

I love you so much，I just don’t like you any more.”。意为：“我还是很爱你，只是已经不再喜欢你了。
你最初爱的那个人并不是你最终爱的那个人，爱不是最终目标，而是一个过程，借助这个过程，一个人想去了解另一个人。——约翰·威廉斯《斯通纳》
无论谁离开了你，别忘了，他没来之前，你本就是一个人生活。
真正坚持到最后的人靠的不是激情，而是恰到好处的喜欢和投入。
你的善良，要有点锋芒。
此地不留爷，自有留爷处。
人要往前看。
不勉强，不强求，不欺骗，不将就，一个人，向前走，天涯共此生，明月诚相待，若是无所求，天地仍光明。
痛苦不是成本，失去机会才是。
真的是有压力才有动力，deadline是第一生产力。
不要追求对人都无差别的热情，没有亲疏之别，怎么对得起你生命中那些重要的人。——蔡康永

我嘞个去，终于过了。。

java HashMap与TreeMap总结