`

???Java容器分析--Map

    博客分类:
  • j2se
阅读更多

 作者:Flyingis

标准的Java类库中包含了几种类型的Map,它们都拥有同样的基本接口Map,但是行为特性各不相同,主要表现在效率、键值对的保存、元素呈现次序、对象的保存周期和判定键是否等价的策略等方面。

1.Map的功能方法

Map(interface): 维护labelvalue的关联性,使得可以通过label查找value

HashMap: Map基于散列表的实现,取代了Hashtable。插入和查询label/value的开销是固定的,并且可以通过构造器设置容量和负载因子,以调整容器的性能。

LinkedHashMap: HashMap的基础上做了一些改进,在迭代遍历它时,取得label/value的顺序是其插入的次序,或者是最近最少使用(LRU)的次序,速度上比HashMap要慢一点,但在迭代访问时速度会更快,主要原因是它使用了链表维护内部次序。

TreeMap: 查看labellabel/value时,元素会被排序,其次序由ComparableComparator决定,因此查询所得到的结果是经过排序的。另外,它是唯一带有subMap()方法的Map具体类,即返回一个子树。它也是SortedMap接口的唯一实现,subMap()方法也是从该接口继承的。

WeakHashMap: Weak Key映射,允许释放映射所指向的对象。当映射之外没有引用指向某个label时,此label可以被垃圾收集器回收。

IdentityHashMap: 使用==代替equals()label进行比较的散列映射。

2.hashCode()

         当使用标准库中的类Integer作为HashMaplabel时,程序能够正常运行,但是使用自己创建的类作为HashMaplabel时,通常犯一个错误。

         HashMap中通过label查找value时,实际上是计算label对象地址的散列码来确定value的。一般情况下,我们是使用基类Object的方法hashCode()来生成散列码,它默认是使用对象的地址来计算的,因此由第一个对象new Apple(5)和第二个对象new Apple(5)生成的散列码是不同的,不能完成正确的查找。通常,我们可以编写自己的hashCode()方法来覆盖基类的原始方法,但与此同时,我们必须同时实现equals()方法来判断当前的label是否与表中存在的label相同。正确的equals()方法满足五个条件:

(1)     自反性。对于任意的xx.equals(x)一定返回true

(2)     对称性。对于任意的xy,如果y.equals(x)返回true,则x.equals(y)也返回true

(3)     传递性。对于任意的xyz,如果有x.equals(y)返回truey.equals(z)返回true,则x.equals(z)一定返回true

(4)     一致性。对于任意的xy,如果对象中用于等价比较的信息没有改变,那么无论调用x.equals(y)多少次,返回的结果应该保持一致,要么一直是true,要么一直是false

(5)     对任何不是nullxx.equals(null)一定返回false

equals()比较的是对象的地址,如果要使用自己的类作为HashMaplabel,必须同时重载hashCode()equals()方法。

使用散列的目的:想要使用一个对象来查找另一个对象。使用TreeSetTreeMap也能实现此目的。另外,还可以自己实现一个Map,此时,必须提供Map.entrySet()方法来生成Map.Entry对象的Set

使用散列的价值:速度,散列使得查询可以快速进行。散列将label保存载数组中方便快速查询,因为存储一组元素最快的数据结构是数组,用它来表示label的信息(后面有信息的描述),而不是label本身。通过label对象计算得到一个数字,作为数组的下标,这个数字就是散列码(即前面所述的信息)。该散列码具体是通过定义在基类Object中,可能由程序员自定义的类覆盖的hashCode()方法,即散列函数生成。为了解决数组容量带来的限制,可以使不同的label生成相同的下标,保存在一个链表list中,每一个链表就是数组的一个元素。查询label时就可以通过对list中的信息进行查找,当散列函数比较好,数组的每个位置中的list长度较短,则可以快速查找到数组元素list中的某个位置,提高了整体速度。

散列表中的slot通常称为bucket,为了使散列分步均匀,bucket的值一般取质数。但事实证明,质数实际上并不是散列bucket的理想容量,近来Java散列实现都使用2的幂,具体如何验证以后再续。

3.HashMap的性能因子

容量(capacity): 散列表中bucket的数量。

初始化容量(initial capacity): 创建散列表时bucket的数量。可以在构造方法中指定HashMapHashSet的初始化容量。

尺寸(size): 散列表中记录的数量。(数组的元素个数,非list中元素总和)

负载因子(load factor): 尺寸/容量。负载因子为0,表示空的散列表,0.5表示半满的散列表。轻负载的散列表具有冲突少,适宜插入与查询的特点,但是使用迭代器遍历会比较慢。较高的负载会减少所需空间大小。当负载达到指定值时,容器会自动成倍地增加容量,并将原有的对象重新分配,存入新的bucket中,这个过程称为“重散列”。

4.重写hashCode()的关键

(1)     对同一个对象调用hashCode()都应该生成同样的值。

(2)     hashCode()方法不要依赖于对象中易变的数据,当数据发生变化时,hashCode()就会生成一个不同的散列码,即产生了一个不同的label

(3)     hashCode()不应依赖于具有唯一性的对象信息,例如对象地址。

(4)     散列码应该更关心速度,而不是唯一性,因为散列码不必是唯一的。

(5)     好的hashCode()应该产生分步均匀的散列码。在Effective Java(Addison-Wesley 2001)中,Joshua BlochhashCode()给出了设计指导,可以参考。

编写正确高效的hashCode()equals()可以参考ApacheJakarta Commons项目中的工具。

分享到:
评论

相关推荐

    Java容器学习笔记:容器概览,容器中的设计模式,容器源码分析 - List,容器源码分析 - Map,容器源码分析 - 并发容

    Java容器学习笔记: 容器概览, 容器中的设计模式, 容器源码分析 - List, 容器源码分析 - Map, 容器源码分析 - 并发容 Java是一种面向对象的编程语言,由Sun Microsystems于1995年推出。它是一种跨平台的语言,...

    Crazy-JAVA-mind-map.zip_Crazy JAVA mind map_crazy_java-mindmap_m

    此外,容器和集合框架是Java编程中不可或缺的部分。ArrayList、LinkedList、HashMap等集合类提供了数据存储和操作的便利。同时,接口(如Comparator、Iterable)和设计模式(如工厂模式、单例模式)也是高级Java...

    Java-concurrentMap-内存模型深入分析-HotCode

    总结来说,深入理解Java内存模型对于正确实现并发容器如`concurrentMap`至关重要。通过分析HotCode,我们可以找出并优化性能关键点。同时,熟悉`HashMap`的底层机制和使用注解技术可以增强代码的并发安全性。而了解...

    java练习题--容器使用练习

    通过这些练习,你将巩固对Java容器的理解,提高代码编写效率,并为解决实际问题打下坚实基础。记得在实践中不断挑战自己,尝试不同的场景和数据结构,以便更好地掌握Java容器的精髓。祝你在学习过程中取得优异的成绩...

    java容器详细解析

    Java容器主要分为两大类:Collection和Map。 Collection Collection是一个独立元素的序列,这些元素都服从一条或多条规则。Collection接口提供了基本的操作方法,例如add、remove、contains等。 List List是一个...

    JAVA容器对象整理

    这些知识点仅仅是Java容器对象的一部分,实际的博客可能会包含更多细节,如源码分析、性能对比和最佳实践。通过阅读博客中的`持有对象.xmind`文件,可以进一步了解博主对这些概念的详细整理和分类。如果你对Java容器...

    java容器学习心得

    ### Java容器学习心得详解 在Java编程中,容器(Containers)是存储和操作对象集合的重要工具,主要包括集合(Collections)和映射(Maps)。本文将深入解析Java容器的关键概念、特性以及不同容器类型的应用场景。 ...

    基础深化和提高-java容器

    Java容器主要分为两大类:Collection 和 Map。 Collection: Collection表示一组对象,它的主要子接口包括List、Set和Queue。其中: List:以线性方式存储元素,允许重复元素,并且可以根据索引访问元素。 Set:不...

    Java容器有两种基本类型Collection 和 Map

    Java 容器的两种基本类型:Collection 和 Map Collection 和 Map 是 Java 中的两种基本容器类型,它们都可以用来存储和管理对象,但它们有着不同的特点和用途。 Collection 是一种聚集对象的容器,每个位置只能...

    02-Java集合容器面试题(2020最新版)-重点.pdf

    ### Java集合容器知识点详解 #### 一、集合容器概述 - **定义**:集合容器是Java平台提供的标准组件,主要用于存储对象。集合框架提供了一套统一的接口和实现,使得开发者能够灵活地处理不同类型的数据集合。 ####...

    JAVA容器的概述,List,Map,Set

    JAVA容器的概述,List,Map,Set

    java中容器是什么意思?

    在Java编程语言中,容器(Container)是一种用来存储和管理数据结构的重要概念,它提供了组织、存储和操作数据的方式。容器通常指的是集合框架中的各种类,如List、Set、Map等,它们允许开发者以不同的方式存储和...

    java版list-map实现 树结构 父子结构 通俗易懂

    此java类实现了对数据表的分类递归树的实现,为本人倾力之作,后期,会发布js版,敬请期待!

    Java 容器.pdf_电子版pdf版

    Java 容器是 Java 语言中的一种集合类库,主要包括 Collection 和 Map 两种类型。Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。 Collection Collection 是一种集合接口,提供了对集合...

    02-Java集合容器面试题-重点.docx

    Java集合容器概述、集合框架、List、Set、Map接口、Iterator、ArrayList、LinkedList、Vector、HashSet、HashMap、Queue、BlockingQueue、ConcurrentHashMap等。 Java 集合容器概述 Java 集合容器是用于存储数据...

    JAVA容器知识积累

    Java容器是Java编程中至关重要的一个部分,它们用于存储、管理和操作对象集合。在这个主题下,我们将深入探讨Java中的核心容器类,包括数组、List、Set和Map,以及它们各自的特点和使用场景。 1. **数组**:数组是...

    java容器(持有对象)

    在Java中,常见的容器主要分为三类:List、Set和Map,这些都是Java集合框架的重要组成部分。 首先,我们来看Collection接口,它是所有单值容器的基础接口。Collection接口定义了通用的操作方法,比如size()返回容器...

    java容器类研究与分析

    首先,Java容器类主要包括两大接口:`Collection`和`Map`。`Collection`接口是最基础的接口,它是一组独立的元素集合,分为两大子接口:`Set`和`List`。`Map`接口则用于存储键值对,不直接属于`Collection`接口,但...

    2020版Java容器 17 道.pdf

    Java容器主要分为三类:Collection、List和Map。Collection是最基本的接口,包括单列集合,如Set(不允许有重复元素)和List(元素有序,允许重复)。Map是双列集合,用于存储键值对。 2. **Collection和...

    JAVA容器的作用和概览

    Java容器(集合框架)是Java编程中极其重要的部分,它提供了多种数据结构,如列表、集合和映射,以适应不同场景下的数据存储和处理需求。通过合理选择和使用不同的容器,可以优化代码的性能和可维护性。同时,了解和...

Global site tag (gtag.js) - Google Analytics