Map、HashMap、TreeMap、LinkedHashMap

Map
与Set接口一样，Map也是一个接口不能实例化
Map是一种键（key）-值（value）对集合，Map中的每个元素都是一个键值对，其中key只能有一个为null且key不能重复(唯一)，而value可以有多个为null且value可以重复(不唯一)，当key值重复写入时，新写入的value值会覆盖原有的值。
Map提供的是一种映射关系，能够实现通过key快速的查找value

HashMap

• 底层数据结构：数组+链表+红黑树实现(JDK1.8之后,JDK1.8之前是数组+链表):具体实现见底部:-)（哈希表）
• 是否有序：无序
• 是否排序：否
• 是否允许存入null：允许：且null作为key时，总是存储在hashtable第一个节点上,但最好不要这样用，出现问题的话，排查比较麻烦。
• 是否线程安全：线程不安全
• 如何解决线程不安全的问题：（1）.多线程环境中推荐使用ConcurrentHashMap （2）.在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合
  来，上个代码

public static void main(String[] args) {HashMap<String, Integer> hm=new HashMap<>();hm.put("张三丰", 1);hm.put("张三丰", 12);hm.put(null, 123);hm.put("张无忌", null);hm.put("张捕头", null);//注意注意，开始输出啦//1.直接输出System.out.println("直接输出：");System.out.println(hm);//2.使用迭代器输出Iterator<Entry<String, Integer>> iter=hm.entrySet().iterator();System.out.println("使用迭代器输出:");while(iter.hasNext()) {Map.Entry<String, Integer> entry=iter.next();System.out.print("key:"+entry.getKey()+" "+"value:"+entry.getValue()+"--");}System.out.println();//3.使用keySet遍历key,在通过key去除valueSystem.out.println("keySet遍历key:");for (String key : hm.keySet()) {System.out.print("key:"+key+" "+"value:"+hm.get(key)+"--");}System.out.println();//4.不使用迭代器，直接使用Entry输出System.out.println("不使用迭代器，直接使用Entry输出：");for (Entry<String, Integer> entry : hm.entrySet()) {System.out.print("key:"+entry.getKey()+" "+"value:"+entry.getValue()+"--");}}

测试结果

直接输出： {null=123, 张三丰=12, 张无忌=null, 张捕头=null} 使用迭代器输出: key:null value:123--key:张三丰 value:12--key:张无忌 value:null--key:张捕头 value:null-- keySet遍历key: key:null value:123--key:张三丰 value:12--key:张无忌 value:null--key:张捕头 value:null-- 不使用迭代器，直接使用Entry输出： key:null value:123--key:张三丰 value:12--key:张无忌 value:null--key:张捕头 value:null--

TreeMap

• 底层数据结构：红黑树
• 是否有序：无序
• 是否排序：是,按照key排序
• key能否为null:不能，因为没有null的比较方法，但value可以为null
• 是否线程安全：线程不安全
  基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。
  基于红黑二叉树的NavigableMap的实现，存入TreeMap的元素应当实现Comparable接口或者实现Comparator接口，会按照排序后的顺序迭代元素，两个相比较的key不得抛出classCastException。主要用于存入元素的时候对元素进行自动排序，迭代输出的时候就按排序顺序输出
  来个代码

/*这段代码是牛客网上的一道编程题，百度“牛牛找工作”即可看到原题*/ package other_demo;import java.util.Scanner; import java.util.TreeMap;public class test_demo {public static void main(String[] args) {int N=0,M=0;Scanner sc=new Scanner(System.in);M=sc.nextInt();//获取小伙伴的人数N=sc.nextInt();//获取工作数量int[] Ai=new int[M];//用于存储小伙伴的能力值TreeMap<Integer, Integer> job=new TreeMap<>();int key=0,value=0;for (int i = 0; i < N; i++) {key=sc.nextInt();value=sc.nextInt();if(job.containsKey(key)) {//保证在key相同时，value一直是最大的value=job.get(key)>value?job.get(key):value;}job.put(key, value);}key=job.firstKey();//获取第一个keyint lastkey=job.lastKey();//获取最大的keyint temp1,temp2;//分别用来保存两个相邻key的value用于比较大小int inter;//中间人，用来取下一个key值//因为是在能力值范围内取最大报酬，所以把报酬重排序while (key!=lastkey) {inter=job.higherKey(key);//获取key的下一个keytemp1=job.get(key);temp2=job.get(inter);value=temp1>temp2?temp1:temp2;job.put(inter, value);key=inter;}//获取能力值 // Iterator<Integer> iter=job.keySet().iterator();for (int i = 0; i < M; i++) {Ai[i]=sc.nextInt();System.out.println(job.floorEntry(Ai[i]).getValue());}} }

再加盘代码吧

public static void main(String[] args) {TreeMap<Integer, String> tm=new TreeMap<>();tm.put(3, "王");tm.put(1, "孟");tm.put(2, "李");System.out.println("直接输出"+tm);System.out.println("firstKey():"+"key="+tm.firstKey()+" value="+tm.get(tm.firstKey()));System.out.println("higherKey():"+"key="+tm.higherKey(tm.firstKey())+" value="+tm.get(tm.higherKey(tm.firstKey())));System.out.println("subMap():"+tm.subMap(1, 3));System.out.println("subMap():"+tm.subMap(1, false, 3, true));System.out.println("ceilingKey():"+tm.ceilingKey(2));System.out.println("ceilingEntry():"+tm.ceilingEntry(2));System.out.println("higherEntry():"+tm.higherEntry(2));System.out.println("headMap():"+tm.headMap(2));//排序后，输出从firstkey开始到secondkey之间的所有key-value对，不包括secondkey;System.out.println("headMap():"+tm.headMap(2,true));System.out.println("tailMap():"+tm.tailMap(2));System.out.println("tailMap():"+tm.tailMap(2, false));//若不加第二个参数，默认为true;System.out.println("descendingKeySet():"+tm.descendingKeySet());//倒序输出TreeMap的key值System.out.println("descendingMap()："+tm.descendingMap());//倒序输出TreeMap的key-valueSystem.out.println("containsKey():"+tm.containsKey(2));System.out.println("containsValue():"+tm.containsValue("李"));} 直接输出{1=孟, 2=李, 3=王} firstKey():key=1 value=孟 higherKey():key=2 value=李 subMap():{1=孟, 2=李} subMap():{2=李, 3=王} ceilingKey():2 ceilingEntry():2=李 higherEntry():3=王 headMap():{1=孟} headMap():{1=孟, 2=李} tailMap():{2=李, 3=王} tailMap():{3=王} descendingKeySet():[3, 2, 1] descendingMap()：{3=王, 2=李, 1=孟} containsKey():true containsValue()true

key=iter.next();可以获取key的值
分析：虽然使用keyset及entryset来进行遍历能取得相同的结果，
但两者的遍历速度是有差别的。
keySet():迭代后只能通过get()取key；再根据key值取value。
entrySet()：迭代后可以e.getKey()，e.getValue()取key和value。

说明：keySet()的速度比entrySet()慢了很多，也就是keySet方式遍历Map的性能不如entrySet性能好
为了提高性能，以后多考虑用entrySet()方式来进行遍历。

LinkedHashMap

• 底层数据结构：双向链表
• 是否有序：有序
• 是否排序：不排序
• 是否允许键值对为空：允许有一个键为空，多个值为空
• 是否线程安全：线程不安全
• 是否允许重复的key值：不允许，会覆盖掉原key的value

上个线程代码吧

public static void main(String[] args) {LinkedHashMap<String, String> lhm=new LinkedHashMap<>();for (int i = 0; i <=30; i++) {new Thread(()->{lhm.put(Thread.currentThread().getName(),UUID.randomUUID().toString().substring(0, 8));System.out.println(lhm);},String.valueOf(i)).start();}}

测试结果

java.util.ConcurrentModificationException

HashTable

• 底层数据结构：JDK1.8之前是数组+链表，JDK1.8之后是数组+链表+红黑树
• 是否有序：无序
• 是否排序：否
• 是否线程安全：是
• 是否允许键值对为null:不允许
• 是否允许有重复的元素：不允许，重复的key所对应的value会覆盖原本的value。

从源码上看：
HashTable继承Dictionary，实现了Map接口

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {

照例来盘代码：
又好像没什么必要吧，毕竟用法和HashMap一样，多了个线程安全

public static void main(String[] args) {Hashtable<String, String> ht=new Hashtable<>();for (int i = 0; i <=30; i++) {new Thread (()->{ht.put(Thread.currentThread().getName(),UUID.randomUUID().toString().substring(0, 8));System.out.println(ht);},String.valueOf(i)).start();}}

数组+链表+红黑树：
如下图所示，就是这样滴：

写一些大致过程吧：以HashMap<String,Integer>为例:首先，你开始了put("张"，1)；
而put的源码是：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

这里要注意hash(key)是计算你传入的key的哈希值，然后调用putVal()函数开始存储。
进入putVal()后会经过一系列判断；比如新加入的key的HashCode值所对应的位置在Entry数组中是否已经存储了别的值。如果没有，直接写入。如果有，则判断key是否相等，不相等的话再继续判断next是否有值，有值的话，还需要知道是红黑树还是链表，然后再根据各自的方法判断添加。如果是链表，还需要在添加完成后判断是否需要转成红黑树。如果上面这些都没有，而是直接添加在Entry数组中的话，需要判断一下是否要扩容。
具体源码分析可以看这篇博客：href="https://blog.csdn.net/m0_37914588/article/details/82287191

总结

以上是生活随笔为你收集整理的Map、HashMap、TreeMap、LinkedHashMap的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。