`
SonofGod
  • 浏览: 20828 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

HashMap实现原理

阅读更多

HashMap本质用一句话概括就是一个链表数组!

 

下面详细表述!

 

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

 

 

 

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

 

 

 

2.既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

 

存储时:

 

int hash = key.hashCode();--> 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值

 

int index = hash % Entry[].length;

 

Entry[index] = value;

 

取值时:

 

int hash = key.hashCode();

 

int index = hash % Entry[].length;

 

return Entry[index]

 

 

 

到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理

 

 

 

问题:若两个key通过hash % Entry[].length得到的index相同,是否有覆盖的风险?

 

   HashMap里面用到链式数据结构的一个概念.上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方,第一个键 值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A.一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。

 

 参考:http://winse.iteye.com/blog/1331725

分享到:
评论

相关推荐

    hashmap实现原理

    在深入探讨HashMap的实现原理之前,我们需要了解两个关键的接口方法:`hashCode()`和`equals()`。 根据《Effective JAVA》的建议,当重写`equals()`方法时,也应重写`hashCode()`方法。这是因为在HashMap中,`...

    基于HashMap的用户标签处理兼Java中HashMap实现原理研究.pdf

    "基于HashMap的用户标签处理兼Java中HashMap实现原理研究" 本文研究了基于HashMap的用户标签处理方法,并对Java中HashMap的实现原理进行了深入研究。HashMap是一种高效的数据结构,可以快速地存储和检索数据。本文...

    hashmap实现原理.pdf

    hashmap实现原理.pdf

    Jdk1.8中的HashMap实现原理.docx

    《Jdk1.8中的HashMap实现原理》 HashMap作为Java编程语言中常用的数据结构,它在Jdk1.8中的实现结合了哈希表、链表以及红黑树的特性,提供高效且灵活的键值对存储功能。本文将深入探讨HashMap的内部结构、工作原理...

    Jdk1.8中的HashMap实现原理.pdf

    总结起来,JDK1.8中的HashMap实现原理主要包括以下几个要点: 1. 链表散列结构:数组+链表,链表用于处理哈希碰撞。 2. 红黑树优化:当链表长度超过8时,转换为红黑树,减少查找、插入和删除的时间复杂度。 3. 内部...

    Jdk1.8 HashMap实现原理详细介绍

    以下是对JDK 1.8 HashMap实现原理的详细解释。 首先,HashMap是一个基于哈希表的数据结构,它实现了Map接口。它不保证映射的顺序,并且是非同步的。这意味着在多线程环境中,如果不进行同步控制,可能会出现并发...

    详解Java HashMap实现原理

    以下是对HashMap实现原理的详细解析。 首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它的大小可以动态调整,并且长度必须是2的幂。初始时,`table`是一个...

    Java8 HashMap的实现原理分析

    Java8之后新增挺多新东西,接下来通过本文给大家介绍Java8 HashMap的实现原理分析,对java8 hashmap实现原理相关知识感兴趣的朋友一起学习吧

    深入解析java HashMap实现原理

    综上所述,理解HashMap的实现原理对于优化Java程序性能至关重要,尤其是在处理大量数据或并发场景时。在实际应用中,应根据具体需求选择合适的数据结构,例如,如果需要线程安全,可以选择ConcurrentHashMap;如果对...

    HashMap底层原理.md

    HashMap底层原理.md

    源码解析jdk8.0集合:HashMap的底层实现原理.pdf

    根据提供的文件信息,以下是对JDK 8.0中HashMap实现原理的详细知识点介绍: 1. HashMap概述 HashMap是Java集合框架的一部分,它实现了Map接口,用于存储键值对。其核心特点在于基于哈希表的映射机制,能够通过键...

    源码解析jdk7.0集合(3):HashMap的底层实现原理.pdf

    ### JDK 7.0集合系列解析之HashMap实现原理 #### 一、HashMap概述 HashMap是Java集合框架中Map接口的典型实现之一,主要用于存储键值对(Key-Value)数据。其特性如下: - 线程不安全,方法为非同步方法,因此多...

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

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

    HashMap原理的深入理解

    HashMap原理的深入理解 HashMap是基于哈希表的Map接口的非同步实现,提供了所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久...

    java HashMap原理分析

    Java HashMap原理分析 Java HashMap是一种基于哈希表的数据结构,它的存储原理是通过将Key-Value对存储在一个数组中,每个数组元素是一个链表,链表中的每个元素是一个Entry对象,Entry对象包含了Key、Value和指向...

    HashMap底层原理

    HashMap的底层原理主要依赖于哈希表,这是一种数据结构,它通过计算键的哈希码来实现高效的查找操作。 在HashMap中,每个元素都是一个键值对,存储在一个Entry对象中。当向HashMap添加键值对时,首先会计算键的哈希...

    Java HashMap实现原理分析(一)

    HashMap的实现原理基于哈希表,它的核心是通过哈希函数将键(key)映射到一个数组的特定位置,从而实现快速访问。本文将深入解析HashMap的put和get操作的内部机制。 首先,HashMap的底层数据结构是一个动态扩容的...

    HashMap的实现原理

    ### HashMap的实现原理 #### 1. HashMap概述 HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值...

Global site tag (gtag.js) - Google Analytics