云谷 网站建设,百度一下你就知道百度一下,青岛海川建设集团网站,wordpress 文章不显示1、Map集合概述 在Java的集合框架中#xff0c;Map为双列集合#xff0c;在Map中的元素是成对以K,V键值对的形式存在的#xff0c;通过键可以找对所对应的值。Map接口有许多的实现类#xff0c;各自都具有不同的性能和用途。常用的Map接口实现类有HashMap、Hashtab…1、Map集合概述 在Java的集合框架中Map为双列集合在Map中的元素是成对以K,V键值对的形式存在的通过键可以找对所对应的值。Map接口有许多的实现类各自都具有不同的性能和用途。常用的Map接口实现类有HashMap、Hashtable、TreeMap、LinkedHashMap和ConcurrentHashMap。
2、Map集合主要特点
Map中的元素都是以K,V键值对的形式存在Map中每个键最多映射到一个值也就是说通过一个key最多只能获取到一个值Map中的key是无序的、不可重复的Map中的value是无序的、可重复的
3、HashMap
3.1、HashMap简介 HashMap 是 Java 中一个非常常用的集合类可以通过key的 HashCode 值来快速访问值具有很快的访问速度并且由于存储的键值对是无序的插入的顺序并不会影响到查询的结果。 在 HashMap 中允许存储的键为 nullvalue也可以为null但只能有一个key 为 null。键值对是通过键的 HashCode 值来存储的如果多个键的 HashCode 值相同它们就会被存储在同一个桶中也就是所谓的哈希桶。每个桶是一个单向链表或双向链表存储了所有哈希值相同的键值对。当我们向 HashMap 中添加一个键值对时它会根据键的 HashCode 值计算出一个哈希桶的索引然后将键值对存储在对应的哈希桶中并将哈希桶中的链表或双向链表更新为当前节点后面的节点。 HashMap 继承自 AbstractMap实现了 Map、Cloneable、java.io.Serializable 接口。HashMap 的 key 与 value 类型可以相同也可以不同可以是字符串String类型的 key 和 value也可以是整型Integer的 key 和字符串String类型的 value。
3.2、HashMap底层数据结构
Java 中的 HashMap 底层数据结构主要由数组、链表、红黑树三部分组成jdk 1.8之前采用数组链表jdk 1.8 采用数组链表红黑树的方式。
数组ArrayHashMap 内部维护了一个 Entry 数组用于存储键值对。每个 Entry 包含了一个键对象和一个值对象它们都是通过哈希函数计算得到的哈希码值作为索引存放在数组中。链表Linked List当多个键的哈希码值相同时它们会被存储在同一个桶中也就是所谓的哈希桶。每个桶是一个单向链表或双向链表存储了所有哈希值相同的键值对链表是为了解决hash冲突的。红黑树Tree当链表的长度超过阈值时在JDK 1.8 之后这个阈值默认为 8链表会转换成红黑树。红黑树是一种自平衡的二叉查找树可以快速查找元素。
3.3、HashMap常见问题
3.3.1、哈希码是什么 哈希码Hash Code是用于计算键的哈希值以便在存储和查询时使用的。哈希码的计算方式是通过将键的哈希值存储在数组中的一个位置上这个位置称为哈希码值。当我们向 HashMap 中添加键值对时HashMap 会使用键的哈希值来计算哈希码值并将键值对存储在对应的哈希码值的位置上。当我们查询 HashMap 中的键值对时HashMap 会使用键的哈希码值来计算哈希码值的位置并在该位置上遍历所有的键值对直到找到对应的键值对。
3.3.2、为什么哈希码在HashMap中很重要 哈希码的重要性在于它可以帮助我们快速地定位键值对在数组中的位置从而提高 HashMap 的存储和查询效率。如果两个键的哈希码不同它们会被分配到不同的桶中如果哈希码相同就会发生哈希冲突需要进一步处理。
3.3.3、HashMap中如何处理哈希冲突 为了解决哈希冲突HashMap 使用了链地址法即将哈希桶转换成一个链表或红黑树存储所有哈希值相同的键值对。当多个键的哈希码值相同时HashMap 会将它们存储在同一个桶中并将它们转换成链表或红黑树的形式。当我们查询键值对时HashMap 会遍历该桶中的所有键值对直到找到对应的键值对。如果该桶中没有对应的键值对则说明该键值对不存在HashMap 会返回 null。
3.3.4、为什么HashMap不是线程安全的 HashMap 内部使用了数组和链表或红黑树来存储键值对当多个线程同时访问 HashMap 时可能会出现以下问题
多线程修改元素出现的不安全线程 A 和线程 B 同时修改同一个 HashMap 中的键值对由于 HashMap 是线程不安全的当线程 A 修改键值对时线程 B 也可能在同时修改键值对导致数据不一致或丢失。多线程并发扩容出现的不安全HashMap在达到阈值时需要进行扩容扩容时需要重新计算Hash值重新分配存储位置。如果在扩容过程中有多个线程同时进行插入或删除操作就可能会导致数据结构混乱还可能会导致Map中链表的尾结点指向头结点造成死循环。
3.3.5、HashMap初始化容量是多少 在创建 HashMap 对象时需要传入一个整数参数表示 HashMap 中桶的数量默认情况下该参数为 16。初始化容量的大小会直接影响到 HashMap 的空间利用率和性能。如果初始化容量太小可能会导致频繁的扩容操作从而降低性能如果初始化容量太大则会导致空间浪费并且当需要进行扩容时需要重新计算数组大小并重新分配内存等也会消耗一定的系统资源。
3.3.6、HashMap 为什么需要动态扩容 为了提高 HashMap 的查询效率。当桶中链表或红黑树的长度超过一定阈值时该阈值默认为初始容量的两倍加上负载因子的值即 2 * initialCapacity 0.5f。超过这个阈值会自动进行扩容到之前容量的2倍阈值也为原来的2倍。扩容时HashMap 会重新分配一个新的桶数组并将原来的键值对数据复制到新的桶数组中。新的桶数组的大小通常是原来的两倍以便容纳更多的键值对数据。由于 HashMap 的扩容操作需要重新计算哈希值因此在扩容时会导致性能下降。为了尽可能减少扩容带来的性能损失建议在创建 HashMap 实例时根据实际需要设置合适的容量大小。
3.3.7、HashMap的加载因子是什么 在 Java 中的 HashMap 中加载因子是一个重要的参数它决定了 HashMap 在初始化时所分配的桶的数量。加载因子的取值范围是 0.75 到 1.0 之间通常情况下默认的加载因子是 0.75。 加载因子的作用是控制 HashMap 中桶的数量当桶的数量达到了加载因子所指定的最大值时就需要进行扩容操作。加载因子的取值会直接影响到 HashMap 的空间利用率和性能如果加载因子的取值过小则会导致频繁的扩容操作从而降低性能如果加载因子的取值过大则会导致空间浪费并且当需要进行扩容时需要重新计算数组大小并重新分配内存等也会消耗一定的系统资源。
3.3.8、HashMap如何保证key的唯一性 当存储键值对时先对key的hashCode值进行比较如果不同则认为两个key不相等会直接插入集合中。如果两个key的hashCode值相同则会调用equals()方法进行比较如果equals()方法返回true则认为两个key相等则会覆盖掉原来的键值对否则认为两个key不相等会两个key会放入到同一个哈希桶中。
3.3.9、HashMap中为什么重写equals方法要重写hashcode方法 在 Java 中HashMap 类使用键的哈希值和键对象的equals方法来实现键的唯一性。equals方法用于比较两个对象是否相等而hashCode方法用于生成键对象的哈希码。当两个对象通过equals方法比较相等时它们的hashCode方法应该返回相同的值。如果两个对象的equals()方法返回true但是它们的hashCode()方法返回的哈希码不同那么它们就会被存在HashMap的不同桶里导致HashMap无法正确获取对象。
3.3.10、HashMap一般用什么作为key 在 Java 中的 HashMap 类中键可以是任何实现了 Comparable 接口的对象。最常用的键类型是字符串。这是因为字符串类型的键可以方便地进行比较和排序并且可以轻松地进行字符串转换。另外字符串类型的键还可以方便地进行序列化和反序列化操作从而方便进行数据传输和存储。其他比较常用的类型如Integer、Long、String、Object等都可以作为key。
4、Hashtable
4.1、Hashtable 简介 Hashtable 是 Java 中的一个同步的键值对存储容器它实现了 Map 接口。与 HashMap 不同Hashtable 是线程安全的它使用 synchronized 关键字将整张散列表加锁的方式来保证多线程访问时的线程安全性因此它的运行效率非常低。 Hashtable 的key和value都不能为 null否则会抛出NullPointerException。
4.2、Hashtable 数据结构组成
HashTable 内部的数据结构主要包括以下几个部分
桶数组使用一个数组来存储键值对这个数组长度由初始容量和负载因子决定。当有新的键值对插入时会通过哈希算法计算出键的索引位置然后将键值对存储在相应的桶中。synchronized 块由于 HashTable 是线程安全的因此在多线程环境下使用时需要进行同步操作以防止不同线程对 HashTable 进行修改操作时发生冲突。为了保证同步操作的有效性HashTable 使用了 synchronized 块来进行同步控制。链表/红黑树当 HashTable 中有多个键值对的哈希值相同时这些键值对会被存储在同一个桶中形成一个链表或红黑树。当链表的节点数量超过一定阈值时会将链表转化为红黑树以提高查找效率。
4.3、Hashtable 底层原理
初始大小为11加载因子为0.75 阈值threshold initialCapacity * loadFactor 扩容机制为大于阈值threshold就进行扩容
5、TreeMap
5.1、TreeMap简介 TreeMap 是 Java 中的一个基于红黑树的排序 Map 实现它实现了 NavigableMap 接口用于存储有序的键值对。由于红黑树的查找效率比链表要慢一些因此在键值对数量较多的情况下使用 TreeMap 可能会影响性能。但是由于 TreeMap 可以保证键值对的有序性因此在一些需要按照键进行排序的场景下使用 TreeMap 是比较合适的。 TreeMap的key不能为 nullvalue可以为null。
5.2、TreeMap 数据结构组成
TreeMap 内部的数据结构主要包括以下几个部分
红黑树使用红黑树来实现有序的键值对存储红黑树是一种自平衡的二叉搜索树可以保证节点之间的排序关系。排序规则内部维护了一个比较器用于定义键的排序规则。当插入键值对时TreeMap 会根据比较器的返回值来确定键的排序顺序。导航操作提供了一些导航操作如 subMap、navigate、climbUp、climbDown 等用于查找、遍历、上翻、下翻等操作。
6、LinkedHashMap
6.1、LinkedHashMap简介 LinkedHashMap 是 Java 中的一个基于双向链表的 Map 实现它实现了 Map 接口用于存储键值对并支持按照插入顺序和访问顺序进行访问。由于 LinkedHashMap 是基于双向链表实现的因此它的插入、删除、查找等操作的时间复杂度都是 O(1)性能比较优秀。但是由于双向链表的数据结构比较简单因此 LinkedHashMap 的可扩展性比一些基于哈希表实现的集合要好。LinkedHashMap 不支持并发访问如果需要在多线程环境下使用需要进行同步控制。 LinkedHashMap 的key可以为 nullvalue可以为null。
6.2、LinkedHashMap 数据结构组成
LinkedHashMap 内部的数据结构主要包括以下几个部分
双向链表使用双向链表来存储键值对每个节点包含前一个节点和后一个节点以及对应的键值对。迭代器提供了一个迭代器用于遍历链表中的所有键值对。当迭代器遍历时会按照插入的顺序来遍历链表。访问顺序 能够记录键值对的访问顺序当访问键值对时LinkedHashMap 会根据访问顺序来返回对应的键值对从而实现有序的访问。
7、ConcurrentHashMap
7.1、ConcurrentHashMap简介 ConcurrentHashMap 是 Java 中常用的一种并发安全的Map实现它实现了 Map 接口内部和 HashMap 一样都是采用了数组 链表 红黑树的方式来实现。与hashtable不同该类不依赖于synchronization去保证线程操作的安全而是利用分段锁CAS 锁来保证数据的安全支持的并发量相对更高。ConcurrentHashMap 插入、删除、查找等操作的时间复杂度都是 O(1)性能也是比较优秀。但是由于哈希表的数据结构比较复杂因此 ConcurrentHashMap 的可扩展性相对一些基于链表的实现集合要差。 ConcurrentHashMap 的key和value都不可以为null。
7.2、ConcurrentHashMap 数据结构组成
ConcurrentHashMap 内部的数据结构主要包括以下几个部分
桶HashTable使用桶来存储键值对桶是一个哈希表每个桶都包含若干个链表用于存储键值对。缓存区Segment使用缓存区来管理桶缓存区是一个分段的数组每个缓存区都包含若干个桶用于提高并发访问时的性能。分段锁CAS 锁使用 CAS 锁来实现并发访问CAS 锁是一种无锁不需要占用额外的 CPU 资源可以提高并发访问时的性能。
7.3、ConcurrentHashMap 主要特点
并发安全支持并发访问能够保证线程安全即使在多线程环境下也能够正确地访问键值对。高性能使用缓存区来管理桶能够提高并发访问时的性能同时使用 CAS 锁来实现并发访问能够避免锁竞争提高并发访问时的性能。可定制的大小支持可定制的大小可以根据实际需要来调整大小从而达到最佳的性能和空间利用率。
