【Java编程的逻辑】Map和Set

2024-09-07 15:18
文章标签 java 逻辑 编程 set map

本文主要是介绍【Java编程的逻辑】Map和Set,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HashMap

Map有键和值的概念。一个键映射到一个值,Map按照键存储和访问值,键不能重复。

HashMap实现了Map接口。

基本原理

HashMap的基本实现原理:内部有一个哈希表,即数组table,每个元素table[i]指向一个单向链表,根据键存取值,用键算出hash值,取模得到数组中的索引位置index,然后操作table[index]指向的单向链表。
存取的时候依据键的hash值,只在对应的链表中操作,不会访问别的链表,在对应链表操作时也是先比较hash值,如果相同再用equals方法比较。这就要求,相同的对象其hashCode返回值必须相同,如果键是自定的类,就特别需要注意。

HashMap扩容策略:

  1. 什么时候扩容? 当添加第一个元素时,默认分配的大小为16,不过,并不是size大于16时再进行扩展,下次什么时候扩展与threshold(阈值)有关。threshold表示阈值,当键值对个数size大于等于threshold的时候考虑进行扩容。threshold一般情况下,等于table.length乘以loadFactor(负载因子,默认0.75)。
  2. 怎么扩容? table的长度总是2的倍数,所以扩容就是先将table长度x2,然后再进行转换。转换的主要工作是重新计算键值对的数组下标。

注意: Java8对HashMap的实现进行了优化,在哈希冲突比较严重的情况下,即大量元素映射到同一个链表的情况下(具体是至少8个元素,且总的键值队个数至少是64),Java8会将该链表转换为一个平衡的排序二叉树。

小结

HashMap实现了Map接口,可以方便地按照键存取值,内部使用数组链表和哈希的方式进行实现
1. 根据键保存和获取值的效率都很高,为O(1),每个单向链表往往只有一个或少数几个节点,根据hash值可以直接快速定位。
2. HashMap支持key为null,key为null的时候,放在table[0]
3. HashMap中的键值对没有顺序,因为hash值是随机的
4. HashMap不是线程安全的,多线程环境下可以使用Hashtable或ConcurrentHashMap。

HashSet

HashSet实现了Set接口。 Set表示的是没有重复元素、且不保证顺序的容器接口,它扩展了Collection,但没有定义任何新的方法。

原理

HashSet内部是用HashMap实现的,它内部有一个HashMap实例变量

private transient HashMap<E,Object> map;

Map是有键和值的,HashSet相当于只有键,值都是相同的固定值,这个值是:

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

相应的add,get等方法都是间接的调用HashMap的方法了

小结

  1. 没有重复元素
  2. 可以高效地添加、删除元素、判断元素是否存在,效率都为O(1)
  3. 没有顺序
  4. 非线程安全

TreeMap

TreeMap中,键值对之间按键有序,TreeMap的实现基础是排序二叉树。

基本用法

TreeMap有两个常用构造方法

public TreeMap();
public TreeMap(Comparator<? super K> comparator)

第一个为默认构造方法,要求Map中的键实现Comparabe接口,TreeMap内部进行各种比较时会调用键的Comparabe接口中的compareTo方法。
第二个接口一个比较器对象comparator,如果comparator不为null,在TreeMap内部进行比较时会调用这个comparator的方法,而不再调用键的compareTo方法。

原理

TreeMap内部是用红黑树实现的,红黑树是一种大致平衡的排序二叉树。
内部主要有如下成员:

// 比较器
private final Comparator<? super K> comparator;  
// 树的根节点, Entry是节点类型
private transient Entry<K,V> root; 
// 当前键值对个数
private transient int size = 0;static final class Entry<K,V> implements Map.Entry<K,V> {// 键K key;// 值V value;// 左孩子Entry<K,V> left;// 右孩子Entry<K,V> right;// 父节点Entry<K,V> parent;// 节点颜色,非黑即红boolean color = BLACK;
}

保存键值对

public V put(K key, V value) {Entry<K,V> t = root;// 1. 第一次添加if (t == null) {// 判断key是否为nullcompare(key, key); // type (and possibly null) check// 直接将root指向该节点root = new Entry<>(key, value, null);size = 1;modCount++;return null;}// ...
}
// 当root为null的时候,主要是判断key是否为null
final int compare(Object k1, Object k2) {return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2): comparator.compare((K)k1, (K)k2);
}
  1. 当添加第一个节点时,root为null,主要就是新建一个节点,设置root指向它。并判断key是否为null
public V put(K key, V value) {// ... // 如果不是第一次添加  int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;// 如果设置了 comparator  if (cpr != null) {do {// 一开始指向跟节点parent = t;            cmp = cpr.compare(key, t.key);// 如果小于根节点,就将t设为左孩子,继续比较if (cmp < 0)t = t.left;// 如果大于,就将t设为右孩子,继续比较    else if (cmp > 0)t = t.right;else// 如果有值,表示已经有这个键了return t.setValue(value);// 如果t为null,则退出循环,parent就指向待插入节点的父节点    } while (t != null);}else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;modCount++;return null;
}
  1. 如果不是第一次添加, 先寻找父节点。寻找父节点根据是否设置了comparator分为两种情况。两种情况查找父节点的逻辑基本相同,只是如果没有设置comparator,则假设key一定实现了Comparable接口,同时key不能为null。如果自己设置了comparator,则可以为null。
  2. fixAfterInsertion(e):在调整数的结构,使之符合红黑树的约束,保持大致平衡。

小结

TreeMap同样实现了Map接口,但内部使用红黑树实现,红黑树是统计效率比较高的大致平衡的二叉树
1. 按键有序,TreeMap同样实现了SortedMap和NavigableMap接口,可以方便地根据键的顺序进行查找,如第一个、最后一个、某一范围的键等
2. 为了按键有序,TreeMap要求键实现Comparable接口或通过构造方法提供一个Comparator对象
3. 根据键保存、查找、删除的效率比较高,为O(h),h为树的高度,在树平衡的情况下,h为log2(N),N为节点数

TreeSet

TreeSet它实现了Set接口,在内部实现上,它基于TreeMap实现。
1. 没有重复元素
2. 添加、删除元素、判断元素是否存在,效率比较高,为O(log2N) ,N为元素个数
3. 有序 , 要求元素实现Comparable接口或通过构造方法提供Comparator对象

LinkedHashMap

LinkedHashMap是HashMap的子类,内部还有一个双向链表维护键值对的顺序。LinkedHashMap可以保持元素按插入或访问有序,这与TreeMap按键排序不同。

  • 按插入排序容易理解,先添加的在前面,后添加的在后面,修改操作不影响排序。
  • 访问排序:所谓访问就是指get/put操作,对一个键执行get/put操作后,其对应的键值对会移动链表末尾,所以,最末尾的是最近访问的,最开始的是最久没有被访问的。

基本使用

默认情况下,LinkedHashMap是按照插入排序的,想要按照访问排序得使用如下的构造方法:

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;
}

其中参数accessOrder就是用来指定是否按访问顺序,如果为true,就是访问顺序。

什么时候希望保持插入顺序呢?
当接收一些键值对输入,处理,然后输出,输出时希望保持原来的顺序。

什么时候希望按访问有序呢?
一种典型的应用是LRU缓存。 一般而言,缓存容量有限,不能无限存储所有数据,如果缓存满了,当需要存储数据时,就需要一定的策略将一些老的数据清理出去,这个策略一般称为替换算法。LRU是一种流行的替换算法,它的全称是Least Recently Used,即最近最少使用。它的思路是,最近刚被使用的很快再次被用的可能性最高,而最久没被访问的很快再被访问的可能性最低,所以被有限清理。
使用LinkedHashMap,可以非常容易地实现LRU缓存,默认情况下,LinkedHashMap没有对容量做限制,但它可以容易地做的,它有一个方法:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;
}

在添加元素到LinkedHashMap后,会调用这个方法,传递的参数是最久没有被访问的键值对,如果这个方法返回true,则这个最久的键值对就会被删除。因为LinkedHashMap是没有容量限制的,所以默认总是返回false。

实现原理

LinkedHashMap是HashMap的子类,内部增加了如下的变量:

// 双向链表的头
private transient Entry<K,V> header;
// 表示按访问排序还是按插入排序
private final boolean accessOrder;

LinkedHashSet

LinkedHashSet是HashSet的子类,内部的Map实现类是LinkedHashMap

这篇关于【Java编程的逻辑】Map和Set的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1145410

相关文章

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

Spring Security中用户名和密码的验证完整流程

《SpringSecurity中用户名和密码的验证完整流程》本文给大家介绍SpringSecurity中用户名和密码的验证完整流程,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 首先创建了一个UsernamePasswordAuthenticationTChina编程oken对象,这是S

java实现docker镜像上传到harbor仓库的方式

《java实现docker镜像上传到harbor仓库的方式》:本文主要介绍java实现docker镜像上传到harbor仓库的方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 前 言2. 编写工具类2.1 引入依赖包2.2 使用当前服务器的docker环境推送镜像2.2

Java easyExcel实现导入多sheet的Excel

《JavaeasyExcel实现导入多sheet的Excel》这篇文章主要为大家详细介绍了如何使用JavaeasyExcel实现导入多sheet的Excel,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录1.官网2.Excel样式3.代码1.官网easyExcel官网2.Excel样式3.代码

Java MQTT实战应用

《JavaMQTT实战应用》本文详解MQTT协议,涵盖其发布/订阅机制、低功耗高效特性、三种服务质量等级(QoS0/1/2),以及客户端、代理、主题的核心概念,最后提供Linux部署教程、Sprin... 目录一、MQTT协议二、MQTT优点三、三种服务质量等级四、客户端、代理、主题1. 客户端(Clien

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Go语言数据库编程GORM 的基本使用详解

《Go语言数据库编程GORM的基本使用详解》GORM是Go语言流行的ORM框架,封装database/sql,支持自动迁移、关联、事务等,提供CRUD、条件查询、钩子函数、日志等功能,简化数据库操作... 目录一、安装与初始化1. 安装 GORM 及数据库驱动2. 建立数据库连接二、定义模型结构体三、自动迁

Spring 框架之Springfox使用详解

《Spring框架之Springfox使用详解》Springfox是Spring框架的API文档工具,集成Swagger规范,自动生成文档并支持多语言/版本,模块化设计便于扩展,但存在版本兼容性、性... 目录核心功能工作原理模块化设计使用示例注意事项优缺点优点缺点总结适用场景建议总结Springfox 是

在Spring Boot中集成RabbitMQ的实战记录

《在SpringBoot中集成RabbitMQ的实战记录》本文介绍SpringBoot集成RabbitMQ的步骤,涵盖配置连接、消息发送与接收,并对比两种定义Exchange与队列的方式:手动声明(... 目录前言准备工作1. 安装 RabbitMQ2. 消息发送者(Producer)配置1. 创建 Spr