`

Java HashMap分析之一 基本结构

 
阅读更多

Java的HashMap非常的常用,本篇研究它的实现算法,最后希望计算出内存占用,性能的量化数据,然后得出什么时候使用HashMap,什么时候不能滥用的结论。

  HashMap实际上是一个数组,数组里面的每个元素都是一个链表。每个元素在通过put方法放入HashMap中的时候,要按照如下步骤进行:1.根据该元素自身提供的hashcode计算出散列值,该散列值就是数组的下标2.将新元素放入该数组位置的链表中先来看一下数组的定义:[java] view plaincopy /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table;

  这是一个数组,transient关键字告诉我们它不会参与序列化。既然是一个数组,总有数目上限,也就意味着如果存入HashMap的元素太多,导致数组大小不能够存放所有的链表的时候,数组大小必须要能够调整。所以首先来考察一下数组容量的相关算法。

  第一,Entry是什么类型?

  [java] view plaincopy static class Entry implements Map.Entry { final K key;V value;Entry next;final int hash;

  /** * Creates new entry. */ Entry(int h, K k, V v, Entry n) { value = v;next = n;key = k;hash = h;}……

  public final boolean equals(Object o) { if (!(o instanceof Map.Entry))

  return false;Map.Entry e = (Map.Entry)o;Object k1 = getKey();Object k2 = e.getKey();if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue();Object v2 = e.getValue();if (v1 == v2 || (v1 != null && v1.equals(v2)))

  return true;} return false;}

  public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^(value==null ? 0 : value.hashCode());}……

  这是一个HashMap类的内部静态类。实现了Map.Entry接口。接受两个模板参数K和V.key和hash一旦在构造函数中被初始化,就不可改变,并且由于有next的存在,Entry可以构成一个单向链表。

  比较重要的是equals和hashCode方法。代码先列出来,后面再解释。

  第二,初始容量的设定大多数都在下面的构造函数里面。用于指定的initialCapacity不准小于0,也不能超过最大值。并且最终的capicity必须是2的n次方。还有如果使用了无参数的构造函数,默认会创建一个拥有16个元素的数组。

  [java] view plaincopy public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)

  throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)

  initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))

  throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

  // Find a power of 2 >= initialCapacity int capacity = 1;while (capacity < initialCapacity)

  capacity <<= 1;

  this.loadFactor = loadFactor;threshold = (int)(capacity * loadFactor);table = new Entry[capacity];init();}

  第三,什么时候应该调整数组的大小?

  算法是这样,有一个变量size保存了实际数组已经使用了多少个元素,并且如果size的值达到了变量threshold的值,就必须扩充数组的容量。threshold=capicity*loadFactor.capicity是数组最大的容纳元素个数,loadFactor可以在构造函数中制定,否则采用默认值0.75f.capicity的最大值是1<<30(也就是2的30次方,1073741824)。由此我们可以看到HashMap最多存放10亿多个链表。

  第四,如何调整数组大小?

  答案是2倍,很像C++里面的vector的分配策略。

  [java] view plaincopy void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex];table[bucketIndex] = new Entry(hash, key, value, e);if (size++ >= threshold)

  resize(2 * table.length);}

  第五,为什么数组大小必须是2的倍数?

  在后面介绍散列值算法的时候会回答。

 

http://soft.chinabyte.com/database/34/12325034.shtml

分享到:
评论

相关推荐

    深入理解Java之HashMap —— 03

    HashMap是Java集合框架中的一种数据结构,它实现了Map接口,允许将键(Key)映射到值(Value)。HashMap通过哈希函数来快速定位键值对,提供O(1)的平均时间复杂度进行插入、删除和查找操作。 HashMap在内部使用了一...

    Java数据结构分析+Java程序员面试宝典

    Java是世界上最流行的编程语言之一,尤其在企业级应用和服务器端开发中占据主导地位。面试时,对于Java程序员,特别是那些寻求高级职位的人来说,对数据结构和算法的深入理解至关重要。"Java数据结构分析+Java程序员...

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

    面试中,HashMap的源码分析与实现是一个常见的考察点,因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...

    数据结构(java版本)

    总的来说,《数据结构(Java版本)》是一本适合程序员入门的教材,通过学习,你可以系统地掌握数据结构和算法,并用Java语言进行实现,为今后的软件开发打下坚实的基础。无论你是准备面试,还是想要提升编程技能,这...

    数据结构与算法分析:Java语言描述

    《数据结构与算法分析:Java语言描述》是一本深度探讨数据结构和算法的书籍,尤其注重使用Java语言进行实现。本书旨在帮助读者理解和掌握如何在实际编程中有效地使用数据结构和算法,提升软件开发的效率和质量。...

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

    HashMap是Java编程语言中最常用的集合类之一,尤其在面试中,HashMap的相关知识是考察候选人对数据结构和算法理解的重要部分。本套学习资料全面涵盖了HashMap的深入解析,旨在帮助求职者掌握大厂面试中的核心知识点...

    Java数据结构和算法中文第二版

    1. **数组(Array)**:数组是最基础的数据结构之一,通过连续的内存空间来存储相同类型的数据元素。 2. **链表(Linked List)**:链表是一种线性数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针...

    Java语言程序设计与数据结构(基础篇)第7章课后习题代码chapter7.rar

    Java语言是目前广泛应用的编程语言之一,特别是在企业级应用、Android开发等领域有着广泛的应用。本压缩包"Java语言程序设计与数据结构(基础篇)第7章课后习题代码chapter7.rar"聚焦于Java的基础知识,特别是与数据...

    数据结构(java)第四版_叶核亚【全套】

    数据结构是计算机科学中的核心课程之一,它主要研究如何在计算机中组织和管理数据,以提高数据处理的效率。在Java编程语言中,理解和掌握数据结构对于开发高效、可维护的软件至关重要。叶核亚的《数据结构(java)第四...

    java数据结构

    首先,数组是Java中最基本的数据结构之一,是相同类型变量的集合。数组可以是一维或多维的,通过下标来访问数组元素。Java中数组的初始化和内存分配是一个重要概念,包括动态数组的概念和Java的边界检查机制。 简单...

    数据结构(Java版)

    数据结构(Java版)是计算机科学中的核心课程之一,它主要研究如何在计算机中组织和存储数据,以便高效地访问和处理。Java作为一种强大的面向对象的编程语言,为实现各种数据结构提供了良好的支持。本节将深入探讨...

    Java基础,Java进阶,Java数据结构,十大算法

    Java是世界上最流行的编程语言之一,尤其在企业级应用开发领域占据主导地位。本教程涵盖了从基础到高级,再到数据结构和算法的全面Java知识体系,旨在帮助开发者深入理解和掌握这门语言。 首先,我们从“Java基础”...

    java 数据结构及算法讲义

    在学习Java数据结构和算法时,PPT通常会包含以下内容:概念介绍、实例分析、伪代码展示、Java代码实现以及性能分析。通过这些内容,学习者可以逐步掌握如何在实际问题中选择合适的数据结构和算法,从而编写出更高效...

    对java基础集合部分(List、HashMap、HashSet、ArrayList等)底层源码的分析与总结

    Map接口代表键值对集合,HashMap是最常用的实现之一。在JDK 1.7中,HashMap是一个数组+链表结构,而在JDK 1.8中引入了红黑树,当桶内元素过多时转换为树结构,以提高查找效率。HashMap不是线程安全的,如果需要线程...

    数据结构与算法分析(Java版)

    总之,《数据结构与算法分析(Java版)》是一本全面而深入的教程,它将带领你走进数据结构和算法的世界,让你的编程之路更加扎实,更具竞争力。通过阅读并实践书中的例子,你将能够更好地应对各种编程挑战,成为一名更...

    数据结构(Java版)习题解答

    数据结构是计算机科学中的核心课程之一,它研究如何在计算机中高效地组织和管理数据,以便进行快速查找、插入和删除等操作。Java作为一种广泛使用的编程语言,提供了丰富的类库来支持各种数据结构的实现。《数据结构...

    java提高篇(二三)-----HashMap.pdf

    HashMap是Java编程中非常重要的数据结构之一,它作为基于哈希表实现的Map接口实例,以键值对(key-value)的形式存储数据。HashMap的主要特点在于通过哈希算法快速定位到存储的位置,允许我们高效地插入、删除和查找...

    csc241-HashMapDemo:使用Java HashMap的简单数据库的演示

    在Java编程语言中,HashMap是集合框架中一个重要的类,它实现了Map接口,提供了一种存储键值对(key-value pairs)的数据结构。这个“csc241-HashMapDemo”项目显然旨在演示如何利用HashMap来创建一个简单的数据库...

    Hashmap 通过对VALUE排序 源代码

    HashMap是Java编程语言中最常用的集合类之一,它提供了一种基于键值对(key-value pair)的数据存储方式,允许我们通过键快速查找对应的值。在Java的HashMap中,元素是无序的,也就是说,它们在内存中的存储位置并...

    全面解析Java中的HashMap类

    Java中的HashMap类是集合框架中的核心组件之一,它提供了一个键值对(key-value pairs)的存储方式,允许快速查找和插入数据。HashMap基于哈希表数据结构实现,即通过哈希函数将键映射到数组的特定位置,从而实现...

Global site tag (gtag.js) - Google Analytics