Java中Map接口的解析

Java中Map接口的解析Map详解:先看图,便于宏观了解Map的地位。Map接口中键和值一一映射.可以通过键来获取值。给定一个键和一个值,你可以将该值存储在一个Map对象.之后,你可以通过键来访问对应的值。 当访问的值不存在的时候,方法就会抛出一个NoSuchElementException异常. 当对象的类型和Map里元素类型不兼容的时候,就会抛出一个ClassCastException异常。…

大家好,又见面了,我是你们的朋友全栈君。

Map详解:

先看图,便于宏观了解Map的地位。

Java中Map接口的解析

Map接口中键和值一一映射. 可以通过键来获取值。

  • 给定一个键和一个值,你可以将该值存储在一个Map对象. 之后,你可以通过键来访问对应的值。
  • 当访问的值不存在的时候,方法就会抛出一个NoSuchElementException异常.
  • 当对象的类型和Map里元素类型不兼容的时候,就会抛出一个 ClassCastException异常。
  • 当在不允许使用Null对象的Map中使用Null对象,会抛出一个NullPointerException 异常。
  • 当尝试修改一个只读的Map时,会抛出一个UnsupportedOperationException异常。

Map基本操作:

Map 初始化

Map<String, String> map = new HashMap<String, String>();

插入元素

map.put(“key1”, “value1”);

获取元素

map.get(“key1”)

移除元素

map.remove(“key1”);

清空map

map.clear();

hashMap原理:

hashMap是由数组和链表这两个结构来存储数据。

数组:存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);寻址容易,插入和删除困难;

链表:存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N);寻址困难,插入和删除容易。

hashMap则结合了两者的优点,既满足了寻址,又满足了操作,为什么呢?关键在于它的存储结构。

它底层是一个数组,数组元素就是一个链表形式,见下图:

Java中Map接口的解析

Entry: 存储键值对。

Map类在设计时提供了一个静态修饰接口Entry。Entry将键值对的对应关系封装成了键值对对象,这样我们在遍历Map集合时,就可以从每一个键值对对象中获取相应的键与值。之所以被修饰成静态是为了可以用类名直接调用。

Java中Map接口的解析

每次初始化HashMap都会构造一个table数组,而table数组的元素为Entry节点,它里面包含了键key,值value,下一个节点next,以及hash

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}

查看hashMap的API发现,它有4个构造函数:

Java中Map接口的解析

1、构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

2、指定初始容量和默认加载因子 (0.75) 的空 HashMap。

3、指定初始容量和默认加载因子的空HashMap。

4、构造一个映射关系与指定Map相同的新HashMap。

注意:HashMap使用的是懒加载,构造完HashMap对象后,只要不进行put方法插入元素之前,HashMap并不会去初始化或者扩容table

Put方法:

首先判断是否是空数组(table == EMPTY_TABLE),如果是,开始初始化HashMap的table数据结构,然后执行扩容函数,如果未指定容量,默认是大小为16的表,然后根据加载因子计算临界值。什么是加载因子呢?hashMap的大小是一定的,如果不够存储了肯定要扩容,那么扩容的依据是什么呢,什么时候确定要扩容了呢?这个时候就需要引入加载因子这个概念,我们假使依旧使用默认大小16,加载因子0.75,那么当hashMap的size大于12(16*0.75=12)的时候,那么就会进行扩容。

回来说put方法,如果key是null,调用putForNullKey方法,保存null与key,这是HashMap允许为null的原因。然后计算hash值和用indexFor计算数据存在的位置,然后从i出开始迭代e,找到 key 保存的位置。

Java中Map接口的解析

Java中Map接口的解析

上面说到如果数组扩容,那么每次要怎么扩容呢?

Java中Map接口的解析

Java中Map接口的解析

当size大于等于某一个阈值thresholdde时候且该table并不是一个空table,因为size 已经大于等于阈值了,说明Entry数量较多,哈希冲突严重,那么若该Entry对应的桶不是一个空桶,这个Entry的加入必然会把原来的链表拉得更长,因此需要扩容;若对应的桶是一个空桶,那么此时没有必要扩容。如果扩容,table会扩容为原来的两倍,直到达到数组的最大长度1<<30(2的30次方),如果size大于这个值,那么就直接修改为Integer.MAX_VALUE。扩容后的元素hash值对应的新的桶位置,然后在指定的桶位置上,创建一个新的Entry。

这里需要说明的是,hashmap是可以存放key和value均为null的,存放在table[0]的位置,此时使用put方法在添加元素的时候,如果在table[0]中已经存入key为null的元素则给null赋上新的value值并返回后面的值,否则则初始化null的元素,存入put里面存放的值。

public static void main(String[] args) {

        HashMap hashMap = new HashMap();
        hashMap.put(null, null);
        System.out.println(hashMap.get(null));
        Integer a = (Integer) hashMap.put(null, 1);
        System.out.println(a);
        System.out.println(hashMap.get(null));
}

/*

输出为:
null
null
1

*/

Get方法:

Java中Map接口的解析

Get比较好理解,判断key是不是null,如果是,返回getForNullKey的函数返回值,如果不是,则在table中去找。

Remove方法:

判断,如果hashMap的size是0,返回null;找到需要移除的元素的前一个节点,然后把前驱节点的next指向删除节点的next节点,此时当前节点没有任何引用指向,它在程序结束之后就会被gc回收。

final Entry<K,V> removeEntryForKey(Object key) {
    		if (size == 0) {
    		    return null;
    		}
   		 int hash = (key == null) ? 0 : hash(key);
   		 int i = indexFor(hash, table.length);
    		Entry<K,V> prev = table[i];
    		Entry<K,V> e = prev;
		 while (e != null) {
        		Entry<K,V> next = e.next;
       		 Object k;
       		 if (e.hash == hash &&
        		    ((k = e.key) == key || (key != null && key.equals(k)))) {
        		    modCount++;
         		   size--;
         		   if (prev == e)
          		      table[i] = next;
         		   else
          		      prev.next = next;
          		  e.recordRemoval(this);
         		   return e;
        		}
        		prev = e;
        		e = next;
   		 }
		 return e;
	}

Map的遍历:

map这里可以用增强for和迭代器两种方式遍历:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class MapDemo {
    public static void main(String[] args) {
        HashMap<String, String> sets = new HashMap<>();
        sets.put("username", "value1");
        sets.put("password", "value2");
        sets.put("key3", "value3");
        sets.put("key4", "value4");
        sets.put(null,null);
        // 增强for循环 =========== keySet ===================
        for (String s : sets.keySet()) {
            System.out.println(s + ".." + sets.get(s));
        }
        //================== entrySet ======================
        for (Map.Entry<String, String> m : sets.entrySet()) {
            System.out.println(m.getKey() + ".." + m.getValue());
        }
        // 迭代器 ================ keySet ===================
        Iterator it = sets.keySet().iterator();
        while (it.hasNext()) {
            String key = (String) it.next();
            System.out.println(key + ".." + sets.get(key));
        }
        //================== entrySet ======================
        Iterator<Map.Entry<String, String>> iterator = sets.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, String> m = iterator.next();
            System.out.println(m.getKey() + ".." + m.getValue());
        }
    }
}

TreeMap

这里简要介绍下:TreeMap 是一个有序的key-value集合,继承于AbstractMap,它是通过红黑树实现的。TreeMap 实现了NavigableMap接口,实现了Cloneable接口,实现了java.io.Serializable接口。

TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。另外,TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它有五个特点如下:

性质1:节点是红色或黑色。

性质2:根节点是黑色。

性质3:每个叶节点(NIL节点,空节点)是黑色的。

性质4:每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)。

性质5:从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

详细了解请点击

LinkedHashMap:

HashMap是无序的,只要不涉及线程安全问题,Map基本都可以使用HashMap。如果我们期待一个有序的Map,这个时候,LinkedHashMap就派上用场了,它虽然增加了时间和空间上的开销,但是通过维护一个运行于所有条目的双向链表,LinkedHashMap保证了元素迭代的顺序,该迭代顺序可以是插入顺序或者是访问顺序。那么是如何维护的呢,首先参考HashMap的存储结构,将其中的Entry元素增加一个pre指针和一个next指针,这样,根据插入元素的顺序将各个元素依次连接起来,这样LinkedHashMap就保证了元素的顺序。

Java中Map接口的解析

继承自HashMap,实现了Map接口,LinkedHashMap重写了父类HashMap的get方法,实际在调用父类getEntry()方法取得查找的元素后,再判断当排序模式accessOrder为true时(即按访问顺序排序),先将当前节点从链表中移除,然后再将当前节点插入到链表尾部。

实现LRU缓存:

LinkedHashMap和HashMap+LinkedList的操作都是类似的,LRU缓存是我最近看到一个很巧妙的东西,所以推荐大家看一下这篇文章

对比下Hashmap、Hashtable和ConcurrentHashmap:

第一、Hashmap是线程不安全的,Hashtable和ConcurrentHashMap是线程安全的,在Hashtable中使用了关键字synchronized修饰,加上了同步锁;ConcurrentHashMap在JDK1.7中采用了锁分离的技术,每一个Segment都独立上锁,保证了并发的安全性;每一个Segment元素存储的是HashEntry数组+ 链表,Segment的大小是一开始就确定的,后期不能再进行扩容,但是单个Segment里面的数组是可以扩容的。

Java中Map接口的解析

但是在JDK1.8上则摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,如下图所示,并发控制使用Synchronized和CAS来操作,每一个Node节点都是用volatile修饰的,整个看起来就像是优化过且线程安全的HashMap。

Java中Map接口的解析

第二、Hashmap是可以存放key和value均为null的,存放在table[0]的位置,此时使用put方法在添加元素的时候,如果在table[0]中已经存入key为null的元素则给null赋上新的value值并返回后面的值,否则则初始化null的元素,存入put里面存放的值。Hashtable和ConcurrentHashMap是不可以存放null的key或者value的,原因和并发状态下的操作有关,当在并发状态下执行无法分辨是key没找到的null还是有key值为null,这在多线程里面是模糊不清的,所以不允许put、get为null的元素,如果强行操作就会报空指针异常。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/157004.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux环境变量文件介绍[通俗易懂]

    Linux环境变量文件介绍[通俗易懂]在Linux系统中,环境变量按照其作用范围不同大致可以分为系统级环境变量和用户级环境变量。      系统级环境变量:每一个登录到系统的用户都能够读取到系统级的环境变量      用户级环境变量:每一个登录到系统的用户只能够读取属于自己的用户级的环境变量 自然而然地,环境变量的配置文件也相应的被分成了系统级和用户级两种。系统级/etc/profile在…

  • id门禁卡复制到手机_门禁卡复制到手机苹果

    id门禁卡复制到手机_门禁卡复制到手机苹果大家好,我是时间财富网智能客服时间君,上述问题将由我为大家进行解答。门禁卡复制到苹果手机的步骤如下:1、首先读取卡的ID,并安装“NFCTagInfo”,打开手机的NFC设置,门禁卡贴到手机后盖NFC部分,“NFCTagInfo”读取校园卡ID。可以看到“我的卡”ID号码。2、其次修改手机NFC的ID。随即打开R.E.管理器,根目录etc,找到etc文件夹中的“libnfc-nxp.conf”…

  • 关于numpy的astype(bool)和astype(int)等等[通俗易懂]

    关于numpy的astype(bool)和astype(int)等等[通俗易懂]关于numpy的astype(bool)和astype(int)等等importnumpyasnpa=[[1,2,1],[2,3,5]]b=[[0,0,0],[2,3,5]]c=np.array(a)d=np.array(b)print(c)print(d)就是简单的把list列表转化为数组然后看看加了.astype(bool)是什么意思?正如astype的中文意思,…

  • 移动端App开发流程管理

    移动端App开发流程管理前言刚刚做完一个项目,值得总结,在此记录一下。   欢迎加入学习小组QQ群: 156958554。项目流程一款应用的开发大体流程如下:1、项目立项:产品经理2、需求确认:产品经理(业务逻辑说明文档)3、业务确认:产品经理,技术经理,架构师4、业务架构:技术经理,架构师(业务流程文档)5、UI确认:产品经理,设计人员,开发人员全体6、

  • 数据库连接池怎么实现_java数据库连接池原理

    数据库连接池怎么实现_java数据库连接池原理数据库连接池1.数据库连接池是干什么的假如我们有个应用程序需要每隔10秒查询一次数据库,我们可以用以下方式方法1:每次查询的时候都新建一个数据库连接,查询结束关闭数据库连接。由于数据库连接的建立是一个非常耗费资源的过程,所以这种每次都新建连接的方式非常浪费资源,不可取。方法2:在最开始的新建一个数据库连接,后续过程中一直使用这个数据库连接进行查询,直到最后关

  • 服务器seo优化,SEO诊断之网站服务器优化「建议收藏」

    服务器seo优化,SEO诊断之网站服务器优化「建议收藏」前一章节子凡已经通过网站域名检查做过最基础的SEO诊断,接下来也是网站SEO诊断中最基础,也是较为重要的要素,没有域名,没有服务器,网站就无处容身,也就不会存在子凡分享的SEO话题了。一、网站服务器速度的重要性在网站速度方面我们要求自己的网站速度当然是越快越好,如果网站打开速度在5~40毫秒是为最佳效果。假设你的网站打开速度基本都在100ms左右,对于个人博客或者网站算是比较给力…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号