`
aawty
  • 浏览: 32614 次
  • 性别: Icon_minigender_2
  • 来自: 上海
社区版块
存档分类
最新评论

HashMap 结构学习

阅读更多

http://beyond99.blog.51cto.com/1469451/429789/

HashMap通过链地址法(拉链法)解决hash冲突,按照存储结构来讲是数组(散列桶)与链表的组合体。

Entry就是数组中的元素,每个 Map.Entry 其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表。

当我们往HashMap中put元素的时候,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标),如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上。

从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。
 
 HashMap的resize(rehash):
当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,加载因子loadFactor的默认值为0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为16,那么当HashMap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
 
HashMap 的实例有两个参数影响其性能:“初始容量” 和 “加载因子”。
容量 是哈希表中桶的数量,初始容量 只是哈希表在创建时的容量。
加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。loadFactor:加载因子 loadFactor定义为:散列表的实际元素数目(n)/ 散列表的容量(m)。
分享到:
评论

相关推荐

    马士兵老师HashMap学习笔记

    《马士兵老师HashMap学习笔记详解》 HashMap是Java编程语言中常用的一种数据结构,它提供了键值对(key-value pair)的存储功能,是基于哈希表实现的。马士兵老师的HashMap学习笔记深入剖析了这一核心组件的工作...

    深入解读大厂java面试必考点之HashMap全套学习资料

    HashMap是Java编程语言中最常用的集合类之一,尤其在面试中,HashMap的相关知识是考察...这套学习资料应该包含了HashMap的实例分析、源码解读、常见面试题以及实战演练等内容,确保你全面掌握这一核心Java数据结构。

    深入Java集合学习系列:HashMap的实现原理

    在Java编程语言中,集合框架是开发者日常工作中不可或缺的一部分,HashMap作为其中的重要成员,它的实现原理对于理解Java性能优化和数据结构有深远的意义。HashMap是一个基于哈希表的数据结构,它实现了Map接口,...

    HashMap类.rar

    通过分析源码,开发者可以深入理解哈希表的工作原理,学习如何在易语言中实现高效的数据结构,这对于提升程序性能和优化内存管理至关重要。同时,这也为自定义数据结构或实现其他哈希表相关的功能提供了基础。

    Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结

    Java集合专题总结:HashMap和HashTable源码...本文总结了HashMap和HashTable的源码学习和面试总结,涵盖了它们的存储结构、构造方法、get和put方法的源码分析、Hash表的特点和缺点、HashTable和HashMap的区别等内容。

    学习笔记:三数组实现的HashMap

    "学习笔记:三数组实现的HashMap"这篇博客文章可能讨论了一种非标准但有趣的HashMap实现,使用了三个数组来代替标准的哈希表结构。这里我们将深入探讨这种三数组实现HashMap的原理和可能的优势。 1. **基本概念**:...

    HashMap详解(通俗易懂)

    这个文档“ HashMap详解(通俗易懂)”很好的阐述了hashmap的底层数据结构示意,希望对学习java的人有帮助

    asp hashmap,arraylist实现

    标题中的“asp hashmap,arraylist实现”指的是在ASP(Active Server Pages)编程中使用HashMap和ArrayList这两种数据结构的具体应用。HashMap和ArrayList是.NET框架中常用的数据集合类,它们在处理和组织数据方面各...

    全手写HashMap精简版Demo 可直接允许查看效果

    在学习过程中,可以重点关注哈希函数的设计、链表的插入与查找以及扩容的实现,这些都是HashMap性能的关键因素。同时,它也可以作为进一步研究和优化哈希表的基础,例如探索更高效的哈希算法或者优化扩容策略。

    易语言HashMap类

    易语言HashMap类是一种在易语言编程环境中实现的高效数据结构,它主要用于存储键值对(key-value pairs),提供快速的数据存取。HashMap类基于哈希表(Hash Table)原理,通过计算键的散列值来确定数据在内存中的...

    hashMap1.8源码

    HashMap是Java编程语言中最常用的集合类之一,它提供了一种基于键值对(key-value pair)的数据存储方式,具有高效查找、插入和删除操作。...对于学习者来说,阅读源码并结合实践是掌握HashMap的最好方式。

    一个delphi的hashmap源代码

    在IT行业中,哈希表(HashMap)是一种高效的数据结构,它使用哈希函数将键(Key)映射到数组的特定位置,以便快速存取数据。Delphi是一种强大的Object Pascal编程语言,它提供了多种实现哈希表的方式。在这个特定的...

    hashMap利用iterator迭代器迭代元素方法

    在Java编程语言中,`HashMap`是一个非常常用的数据结构,它实现了`Map`接口,用于存储键值对。`HashMap`使用哈希表实现,提供快速的插入、删除和查找操作。当我们需要遍历`HashMap`中的所有元素时,通常会使用`...

    Java-HashMap.rar_hashmap_java hashmap

    在Java编程语言中,`HashMap`是`java.util`包中的一个核心类,它属于集合框架的一部分,主要用于存储键值对的数据结构。`HashMap`基于哈希表(散列表)实现,提供了快速的插入、删除和查找操作,平均时间复杂度为O(1...

    Java版数据结构学习资料

    这份"Java版数据结构学习资料"提供了丰富的学习资源,包括PPT和实践代码,旨在帮助学习者深入理解数据结构并提升编程能力。下面将详细阐述其中涉及的主要知识点。 一、数据结构基本概念 数据结构是指在计算机中存储...

    前端开源库-hashmap

    开发者可以通过阅读源代码,学习其内部实现机制,提升对数据结构和算法的理解。 在压缩包`hashmap-master`中,可能包含的文件有源代码文件(如`index.js`)、测试用例(`test`目录)、文档(`docs`目录)、示例(`...

    HashMap CRUD操作

    在`Javase_product_HashMap`这个压缩包中,可能包含了实现以上操作的Java源代码示例,供学习者参考和实践。通过这个例子,初学者可以更好地理解HashMap的基本操作以及在实际问题中的应用。同时,了解并掌握HashMap的...

    易语言源码易语言HashMap类源码.rar

    通过分析和学习易语言HashMap类的源码,开发者可以深入理解哈希表的工作原理,以及易语言如何实现高效的数据结构。这对于提升编程技能,尤其是理解和优化数据结构的性能,具有很大的帮助。同时,源码也可以作为参考...

    hashmap.zip

    在这个压缩包文件"hashmap.zip"中,包含了关于HashMap的案例、资料、讲义等资源,是深入学习HashMap的好材料。 首先,我们需要了解HashMap的基本概念。HashMap是一个散列容器,内部通过数组加链表的方式实现。每个...

    面试必考之HashMap源码分析与实现

    在Java编程语言中,HashMap是集合框架中一个重要的类,用于存储键值对的数据结构。面试中,HashMap的源码分析与实现是一个常见的考察点,...深入学习和实践HashMap源码,能够帮助我们更好地理解和优化Java应用程序。

Global site tag (gtag.js) - Google Analytics