Java-数据结构(二)-Map:HashMap、TreeMap、LinkedHashMap

这篇具有很好参考价值的文章主要介绍了Java-数据结构(二)-Map:HashMap、TreeMap、LinkedHashMap。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、 引言

    Map是Java中常用的数据结构,它提供了一种键值对的存储方式,可以根据键来快速访问值。在本篇文章中,我将学习Java中的Map数据结构

    问题是最好的老师,我将从至少以下几个方面阐述,什么是map、使用Map有什么好处、Map的底层原理、map中的key和value分别是什么、以及Map的Key值为什么不能重复、Map中的key值和Hash有什么关系。

    以及对HashMap、TreeMap和LinkedHashMap三种常用的Map实现类进行了解。我将逐步解析它们的初始化、添加和获取元素、遍历和删除元素等功能,最后给出一个二维表进行结构化。

二、问题

2.1 什么是Map

    Map是Java中的一个接口,它代表了一种键值对的映射关系。它允许我们通过Key来访问Value。在Map中,每个Key都是唯一的,而且与该Key对应的Value是一一对应的关系。

2.2 使用Map的好处

    使用Map有很多好处,以下是其中几个重要的好处:

    快速访问:通过给定的Key,可以快速地访问对应的Value,无需遍历整个集合。
    灵活性:Map不仅可以存储基本数据类型的值,还可以存储自定义对象作为Value,这使得它非常灵活。
    动态增长:Map的大小可根据需要动态增长,不需要事先指定容量。
    数据分类:Map可以用于对数据进行分类、分组和存储,为后续的检索和处理提供了便利。

2.3 Map的底层原理

    在Java中,常用的Map实现类有HashMap、TreeMap和LinkedHashMap。这些实现类在底层的数据组织方式和查找算法上略有不同。

    HashMap使用散列表(Hash Table)作为底层数据结构,它通过把Key的Hash值映射到一个数组索引上,并使用链地址法解决Hash冲突。

    TreeMap使用红黑树(Red-Black Tree)作为底层数据结构,它会对Key进行排序,并且可以提供有序的遍历。

    LinkedHashMap继承自HashMap,它在HashMap的基础上通过维护一个双向链表来保证插入顺序或访问顺序。

    根据实际情况选择不同的Map实现类,可以根据需求来平衡时间复杂度和空间复杂度。

    下面将会了解这几个实现类的一些方法。

2.4 Key和Value的含义

在Map中,Key用于唯一标识一个键值对,它相当于数据的索引。Value则是与Key相关联的数据。对于同一个Key,只能有一个对应的Value,但是不同的Key可以对应不同的Value。

例如,我们可以创建一个Map,将每个人的名字作为Key,将他们的年龄作为Value。通过Key,我们可以快速地查找到对应的年龄。

2.5 Key值为什么不能重复

    Map中要求每个Key都是唯一的,这是因为Map需要通过Key来定位和访问Value。如果出现多个相同的Key,Map无法确定应该返回哪个Value。

    当我们使用put方法向Map中添加键值对时,如果Key已经存在,新的Value将会覆盖旧的Value。因此,Key的唯一性保证了在Map中定位Value的准确性。

2.6 Key值和Hash的关系

    Java中的HashMap和LinkedHashMap是通过计算Key的Hash值来确定Key在底层数组中的位置的。

    在HashMap中,当我们向其中插入一个键值对时,HashMap会首先通过Key的hashCode()方法计算Key的哈希值。然后,HashMap会根据哈希值对数组的长度取模,得到Key在底层数组中的索引位置。如果有多个Key的哈希值映射到同一个索引位置,则HashMap会使用链表或红黑树来处理冲突。

    而在LinkedHashMap中,它在HashMap的基础上通过维护一个双向链表来保证插入顺序或访问顺序。HashMap中的Key与链表节点相互关联,实现了按照插入顺序或访问顺序迭代Map的键值对。

    由此可见,Hash在Map中起到了定位Key的作用,通过计算Key的哈希值,可以快速地定位到Key在底层数组中的位置,从而提高了查找效率。同时,Hash值的唯一性也保证了Key在Map中的唯一性。

    由于Hash值是通过哈希函数计算得出的,存在一定的碰撞概率。因此,在使用自定义对象作为Key时,我们需要重写hashCode()方法来确保生成的Hash值能够准确地表示对象的唯一性,同时也要重写equals()方法来处理碰撞冲突时的比较逻辑。这样可以保证不同的Key对象即使在Hash值相同的情况下,也可以正确地进行比较和查找。

三、 HashMap

javamap和hashmap,# java相关,java,数据结构

3.1 初始化HashMap

    在Java中,我们可以使用HashMap类来创建一个HashMap对象。下面是一些常见的初始化方法:

    使用默认构造函数:

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

    指定初始容量:

HashMap<String, Integer> map = new HashMap<>(16);

指定初始容量和加载因子:

HashMap<String, Integer> map = new HashMap<>(16, 0.75f);

3.2 添加和获取元素

    向HashMap中添加元素时,我们需要使用put()方法,并提供键和值。下面是一个示例:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 10);
map.put("orange", 8);

    获取HashMap中的元素可以使用get()方法,并提供键。下面是一个示例:

int appleCount = map.get("apple");
System.out.println("苹果数量:" + appleCount);

3.3 遍历HashMap

    遍历HashMap可以使用多种方式,比如使用迭代器、for-each循环或使用Java 8的Lambda表达式。下面是一个使用迭代器遍历HashMap的示例:

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println("水果:" + entry.getKey() + ",数量:" + entry.getValue());
}

3.4 删除元素

    从HashMap中删除元素可以使用remove()方法,并提供键。下面是一个示例:

map.remove("banana");

3.5实现原理

①HashMap的put()方法

实现原理如下:

    首先,HashMap将要存储的键值对通过哈希函数进行处理,得到一个哈希码(hash code)。

    接下来,HashMap将根据哈希码找到该键值对应在内部数组中的索引位置。

    如果该位置上没有其他键值对存在,那么直接将新的键值对存储在该位置上即可。

    如果该位置上已经存在其他键值对,那么HashMap将采用链表或者红黑树的方式来处理冲突。它会在该位置上的键值对链表(或树)中依次比较存储的键的哈希码和键值是否与要存储的键值对相等。

    如果找到了相等的键,HashMap会替换该键对应的值。

    如果没有找到相等的键,HashMap会将新的键值对添加到链表(或树)的末尾。

javamap和hashmap,# java相关,java,数据结构

②HashMap的get()方法

它的实现原理如下:

    首先,HashMap通过哈希函数计算键的哈希码。

    接下来,HashMap将根据哈希码找到该键对应在内部数组中的索引位置。

    如果该位置上没有键值对,那么表示该键不存在于HashMap中,返回null。

    如果该位置上存在键值对,HashMap会遍历链表(或树),比较存储的键的哈希码和键值是否与要获取的键值对相等。

    如果找到了相等的键,HashMap返回该键对应的值。

    如果遍历完链表(或树)都没有找到相等的键,那么表示该键不存在于HashMap中,返回null。

    通过这种方式,HashMap可以高效地实现put()和get()方法,快速存储和查找键值对,提供了快速的数据访问能力。

四、 TreeMap

javamap和hashmap,# java相关,java,数据结构

4.1 初始化TreeMap

    与HashMap类似,我们可以使用TreeMap类来创建一个TreeMap对象。下面是一些常见的初始化方法:

    使用默认构造函数:

TreeMap<String, Integer> map = new TreeMap<>();

    使用Comparator初始化:

TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());

4.2 添加和获取元素

    添加和获取元素的方式与HashMap类似,使用put()方法添加元素,使用get()方法获取元素。

map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);

int value = map.get("apple");
System.out.println(value);  // 输出:1

4.3 遍历TreeMap

    遍历TreeMap的方法与HashMap类似,可以使用迭代器、for-each循环或Lambda表达式。

    以下是使用for-each循环遍历TreeMap的例子:

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    int value = entry.getValue();
    System.out.println(key + " : " + value);
}

4.4 删除元素

    从TreeMap中删除元素的方式与HashMap类似,使用remove()方法。

map.remove("banana");

五、 LinkedHashMap

javamap和hashmap,# java相关,java,数据结构

5.1 初始化LinkedHashMap

    LinkedHashMap是一个有序的Map实现类,保留了元素的插入顺序。初始化方式与HashMap类似。

    使用默认构造函数:

LinkedHashMap<String, Integer> map = new LinkedHashMap<>();

5.2 添加和获取元素

    添加和获取元素的方式与HashMap类似,使用put()方法添加元素,使用get()方法获取元素。

map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);

int value = map.get("apple");
System.out.println(value);  // 输出:1

5.3 遍历LinkedHashMap

    遍历LinkedHashMap的方法与HashMap类似,可以使用迭代器、for-each循环或Lambda表达式。

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    int value = entry.getValue();
    System.out.println(key + " : " + value);
}

5.4 删除元素

    从LinkedHashMap中删除元素的方式与HashMap类似,使用remove()方法。

map.remove("banana");

六、二维表总结

维度 HashMap TreeMap LinkedHashMap
底层实现 哈希表 红黑树 哈希表+链表
插入顺序 无序 无序(基于键的自然排序或自定义排序) 保持插入顺序
查找效率 O(1) O(log n) O(1)
迭代顺序 无序 有序(基于键的自然排序或自定义排序) 保持插入顺序或访问顺序
键的唯一性 允许null键和null值 不允许null键,可null值 允许null键和null值
性能 在大多数情况下,具有良好的性能 相比HashMap,由于排序逻辑,稍稍慢一些 相比HashMap,由于维护链表,稍稍慢一些
空间需求 相对较低(无序) 相对较高(有序) 相对较高(保持插入顺序或访问顺序)

    我们可以看到HashMap、TreeMap和LinkedHashMap都是非常有用和灵活的Map实现类,每种都适用于不同的使用场景。当我们需要一个无序、高效的Map时,可以选择HashMap;当我们需要一个有序的Map时,可以选择TreeMap;而当我们需要一个保留插入顺序、支持特殊操作的Map时,可以选择LinkedHashMap。

    因此,当我们需要使用Map数据结构时,我们可以根据具体需求选择合适的数据结构来解决问题。

如果本篇博客对您有一定的帮助,请您留下宝贵的三连:留言+点赞+收藏哦。文章来源地址https://www.toymoban.com/news/detail-736343.html

到了这里,关于Java-数据结构(二)-Map:HashMap、TreeMap、LinkedHashMap的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【java数据结构】HashMap和HashSet

    目录 一.认识哈希表: 1.1什么是哈希表? 1.2哈希表的表示:  1.3常见哈希函数:  二.认识HashMap和HashSet: 2.1关于Map.Entry的说明:, 2.2Map常用方法说明: 2.3HashMap的使用案例: 2.4Set常见方法说明:  2.5HashSet使用案例: 源码: 之前的学习中,如果我们要查找一个元素,肯定是要经

    2024年03月14日
    浏览(83)
  • 【Java 数据结构】HashMap和HashSet

    目录 1、认识 HashMap 和 HashSet 2、哈希表 2.1 什么是哈希表 2.2 哈希冲突 2.2.1 概念 2.2.2 设计合理哈希函数 - 避免冲突 2.2.3 调节负载因子 - 避免冲突 2.2.4 Java中解决哈希冲突 - 开散列/哈希桶 3、HashMap 的部分源码解读 3.1 HashMap 的构造方法 3.2 HashMap 是如何插入元素的? 3.3 哈希表

    2024年02月01日
    浏览(43)
  • java八股文面试[数据结构]——HashMap扩容优化

         知识来源: 【2023年面试】HashMap在扩容上做了哪些优化_哔哩哔哩_bilibili  

    2024年02月11日
    浏览(39)
  • java数据结构(哈希表—HashMap)含LeetCode例题讲解

      目录 1、HashMap的基本方法 1.1、基础方法(增删改查) 1.2、其他方法  2、HashMap的相关例题 2.1、题目介绍 2.2、解题 2.2.1、解题思路 2.2.2、解题图解 2.3、解题代码 HashMap 是一个散列表,它存储的内容是键值(key-value)映射。 HashMap 的 key 与 value 类型可以相同也可以不同,根据定

    2024年02月05日
    浏览(52)
  • Java----Hashmap,LinkedMap和TreeMap三者的区别

            其中map表示的意思为“映射”,HashMap,LinkedMap和TreeMap这三中类都是对Map接口的实现类,在数据插入方面,HashMap是无序插入,LinkedMap是有序插入,而TreeMap会根据键的值进行排序后再进行插入。在运行方面,前两个的运行速度较快,针对Map对象的存储会选择前两者,

    2024年02月13日
    浏览(44)
  • 【数据结构】 | java中 map和set 详解

    🎗️ 博客新人,希望大家一起加油进步 🎗️ 乾坤未定,你我皆黑马 我们首先来看一下集合的框架结构: Set实现了Collection接口,Map是一个单独存在的接口。 而下面又分别各有两个类,分别是TreeSet(HashSet)和 HashSet(HashMap) Map和Set的作用是用来查找和搜索的;以后涉及到

    2023年04月10日
    浏览(37)
  • 【数据结构】搜索树 与 Java集合框架中的Set,Map

    作者主页:paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏:《

    2024年02月08日
    浏览(37)
  • Java02-迭代器,数据结构,List,Set ,Map,Collections工具类

    目录 什么是遍历? 一、Collection集合的遍历方式 1.迭代器遍历 方法 流程 案例 2. foreach(增强for循环)遍历 案例 3.Lamdba表达式遍历 案例 二、数据结构 数据结构介绍 常见数据结构 栈(Stack) 队列(Queue) 链表(Link) 散列表(Hash Table) 树(Tree) List接口 ArraysList集合 Linked

    2024年02月14日
    浏览(50)
  • 《HashMap的数据结构》

    目录 HashMap概述:  数据结构的组成: 一个键值对是如何存入该结构中: HashMap中链表和红黑树的用途和转换方式 :                     HashMap是基于哈希表的Map接口实现的,它存储的内容是键值对key,value映射。 该类无序。         在JDK1.7及以前,HashMap的数据结构是有

    2024年02月07日
    浏览(40)
  • HashMap的数据结构

    HashMap基于哈希表的Map接口实现,是以key-value存储形式存在,即主要用来存放键值对。HashMap的实现不是同步的,这意味着它不是线程安全的。它的key、value都可以为null。此外,HashMap中的映射不是有序的。 JDK1.8之前的HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包