`

HashMap的数据结构

 
阅读更多
1. HashMap的数据结构
数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。

数组

数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

链表

链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。

哈希表
那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表。哈希表((Hash table)既满足了数据的查找方便,同时不占用太多的内容空间,使用也十分方便。

  哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为“链表的数组” ,如图:




从上图我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

  HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

  首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

参考:http://blog.csdn.net/vking_wang/article/details/14166593
分享到:
评论

相关推荐

    比较分析Vector、ArrayList和hashtable hashmap数据结构

    比较分析Vector、ArrayList和hashtable hashmap数据结构

    javaScript模拟的HashMap数据结构的对象

    javaScript模拟的HashMap数据结构,可以方便的put和get。几乎和Java中HashMap类的功能一模一样。非常好用的!

    HashMap的一个数据结构

    HashMap的一个数据结构 锁升级:锁升级过程 resize的过程在开发中 怎么保证容器它线程安全后就是数据插入过程使用的头插法 但是头插法会造成一些问题等等等等的那个等等的那个等等的那个等等的那个等等的那个等等的...

    dcl.rar_Delphi DCL_dcl数据_delphi hashmap_hashmap.pas

    本篇文章将详细探讨标题中的“dcl.rar_Delphi DCL_dcl数据_delphi hashmap_hashmap.pas”,特别是其在Delphi中对HashMap数据结构的实现。 首先,让我们来了解下什么是DCL(Data Control Library)。DCL是Delphi中的...

    剖析Java中HashMap数据结构的源码及其性能优化

    在Java编程语言中,HashMap是实现键值对存储的关键数据结构之一。它是基于哈希表原理,通过将键(Key)映射到哈希值,快速定位到存储的值(Value)。本文将深入剖析Java中HashMap的数据结构以及性能优化策略,特别是...

    基于JavaScript的HashMap实现

    这篇博客“基于JavaScript的HashMap实现”可能详细阐述了如何通过自定义函数来创建一个高效且灵活的HashMap数据结构。 在JavaScript中,对象(Object)是哈希表的一种表现形式,其内部通过键(key)来定位值(value...

    js 版 java hashmap

    在描述中提到的"js版java HashMap"可能是指一个JavaScript实现的HashMap类,它模仿了Java中的HashMap数据结构,提供了更高效和灵活的操作。Java的HashMap是一个基于哈希表的Map接口实现,提供快速的插入、删除和查找...

    kpcb-hashmap:自定义Java HashMap数据结构

    Java中的HashMap是编程中最常用的集合...如果你深入研究这个项目的源码,不仅可以学习到高级的Java编程技巧,还能了解如何针对具体应用场景优化数据结构,这对于提升编程技能和理解数据结构的底层工作原理非常有帮助。

    今天的赛事的比分如下.docx

    该技术使用Java语言中的HashMap数据结构来统计单词的出现次数,并使用Scanner类来获取用户输入的英文句子。 首先,在strTostrArray方法中,将输入的英文句子转换为小写,并使用正则表达式将非字母字符替换为空格...

    jdk1.8中文文学习手册

    hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组的...

    Java HashMap的三种遍历方法及优缺点含示例

    ### HashMap数据结构简介 在深入遍历方法之前,我们先回顾一下HashMap的基本数据结构。HashMap由数组和链表(在JDK1.8之后还包括红黑树)组成,数组是其主体结构,而链表和红黑树则用于处理哈希冲突。当两个键的...

    jdk1.8.zip

    hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组的...

    01-HashMap底层数据结构分析.mp4

    01-HashMap底层数据结构分析.mp4

    关于如何解决HashMap线程安全问题的介绍

    在Java编程中,HashMap是一个非常常用的集合类,用于存储键值对数据。然而,它存在一个重要的特性,那就是线程不...在设计和编写多线程程序时,要始终关注数据结构的选择和操作的同步控制,以保证程序的正确性和效率。

    jdk-8u202-linux-x64.tar

    hashMap数据结构的优化,原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode方法,计算出哈希码值,经过哈希算法算成数组的...

    jdk-8u112-windows-x64.zip

    hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组...

    jdk1.8.0_60_linux.zip

    hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode 方法,计算出哈希码值,经过哈希算法算成数组的...

    Hashmap详解

    HashMap 是一种常用的数据结构,在 Java 中,它是一个数组和链表的结合体。下面我们将深入探讨 HashMap 的数据结构、 put 方法的实现细节和 Hash 码的计算过程。 HashMap 的数据结构 HashMap 的数据结构可以分为两...

Global site tag (gtag.js) - Google Analytics