HashMap的理解

公众号:码农乐园 等级 476 0 0

HashMap在Map.Entry静态内部类实现中存储key-value对。HashMap使用哈希算法,在put和get方法中,它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候, HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。Entry存储在LinkedList中,所以如果存在entry,它使用equals()方法来检查传递的key是否已经存在,如果存在,它会覆盖value,如果不存在,它会创建一个新的entry然后保存。当我们通过传递key调用get方法时,它再次使用hashCode()来找到数组中的索引,然后使用equals()方法找出正确的Entry,然后返回它的值。下面的图片解释了详细内容。 其它关于HashMap比较重要的问题是容量、负荷系数和阀值调整。HashMap默认的初始容量是32,负荷系数是0.75。阀值是为负荷系数乘以容量,无论何时我们尝试添加一个entry,如果map的大小比阀值大的时候,HashMap会对map的内容进行重新哈希,且使用更大的容量。容量总是2的幂,所以如果你知道你需要存储大量的key-value对,比如缓存从数据库里面拉取的数据,使用正确的容量和负荷系数对HashMap进行初始化是个不错的做法。 HashMap内部是使用一个默认容量为16的数组来存储数据的,而数组中每一个元素却又是一个链表的头结点,所以,更准确的来说,HashMap内部存储结构是使用哈希表的拉链结构(数组+链表),这种存储数据的方法叫做拉链法 。如图: HashMap的理解 且每一个结点都是Entry类型,那么Entry是什么呢?我们来看看HashMap中Entry的属性: final K key; final V value; final int hash; HashMapEntry<K, V> next; 从中我们得知Entry存储的内容有key、value、hash值、和next下一个Entry,那么,这些Entry数据是按什么规则进行存储的呢?就是通过计算元素key的hash值,然后对HashMap中数组长度取余得到该元素存储的位置,计算公式为hash(key)%len,比如:假设hash(14)=14,hash(30)=30,hash(46)=46 我们对len取余,得到hash(14)%16=14,hash(30)%16=14,hash(46)%16=14。所以hash值为14的这个元素存储在数组下标为14的位置。 HashMap的理解 从中可以看出,如果有多个元素key的hash值相同的话,后一个元素并不会覆盖上一个元素,而是采取链表的方式,把之后加进来的元素加入链表末尾,从而解决了hash冲突的问题,由此我们知道HashMap中处理hash冲突的方法是链地址法。 在此补充一个知识点,处理hash冲突的方法有以下几种:

  1. 开放地址法
  2. 再哈希法
  3. 链地址法
  4. 建立公共溢出区 讲到这里,重点来了,我们知道HashMap中默认的存储大小就是一个容量为16的数组,所以当我们创建出一个HashMap对象时,即使里面没有任何元素,也要分别一块内存空间给它,而且,我们再不断的向HashMap里put数据时,当达到一定的容量限制时(这个容量满足这样的一个关系时候将会扩容:HashMap中的数据量>容量*加载因子,而HashMap中默认的加载因子是0.75),HashMap的空间将会扩大,而且扩大后新的空间一定是原来的2倍,我们可以看put()方法中有这样的一行代码: int newCapacity = oldCapacity * 2; 所以,只要一满足扩容条件,HashMap的空间将会以2倍的规律进行增大。假如我们有几十万、几百万条数据,那么HashMap要存储完这些数据将要不断的扩容,而且在此过程中也需要不断的做hash运算,这将对我们的内存空间造成很大消耗和浪费,而且HashMap获取数据是通过遍历Entry[]数组来得到对应的元素,在数据量很大时候会比较慢,所以在Android中,HashMap是比较费内存的。 所以我们在一些情况下可以使用SparseArray和ArrayMap来代替HashMap。
收藏
评论区

相关推荐

1 手写ArrayList核心源码
手写ArrayList核心源码 ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue,PriorityQueue等等,我们将手写这些常用的数据结构的核心源码,用尽量少的代码来揭示核心原理。 下面我们来手写ArrayList的核心源码 首先
3 手写Java HashMap核心源码
手写Java HashMap核心源码 上一章手写LinkedList核心源码,本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash map,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。 HashMap
Java中遍历HashMap的5种方式
本教程将为你展示Java中HashMap的几种典型遍历方式。 如果你使用Java8,由于该版本JDK支持lambda表达式,可以采用第5种方式来遍历。 如果你想使用泛型,可以参考方法3。如果你使用旧版JDK不支持泛型可以参考方法4。 1、 通过ForEach循环进行遍历 import java.io.IOException; import jav
Android经典面试题,也可以提升综合能力
基础问题相关 1、接口的意义百度 2、抽象类的意义百度 3、内部类的作用乐视 4、Java 虚拟机的特性百度乐视 5、哪些情况下的对象会被垃圾回收机制处理掉美团小米 6、进程和线程的区别猎豹美团 7、java中和equals和hashCode的区别乐视 8、HashMap的实现原理美团 9、stringst
HashMap深度解析:一文让你彻底了解HashMap
前言 HashMap是Map族中最为常用的一种,也是 Java Collection Framework 的重要成员。本文首先给出了 HashMap 的实质并概述了其与 Map、HashSet 的关系,紧接着给出了 HashMap 在 JDK 中的定义,并结合源码分析了其四种构造方式。 最后,通过对 HashMap 的数据结构、实现原理、源码实现三
深入理解 hashcode 和 hash 用法
摘要 二进制计算的一些基础知识 为什么使用 hashcode String 类型的 hashcode 方法 为什么大部分 hashcode 方法使用 31 HashMap 的 hash 算法的实现原理(为什么右移 16 位,为什么要使用 ^ 位异或) HashMap 为什
HashMap的理解
HashMap在Map.Entry静态内部类实现中存储keyvalue对。HashMap使用哈希算法,在put和get方法中,它使用hashCode()和equals()方法。当我们通过传递keyvalue对调用put方法的时候, HashMap使用Key hashCode()和哈希算法来找出存储keyvalue对的索引。Entry存储在LinkedL
拿下面试!HashMap源码解析!!
拿下面试!HashMap源码解析!! HashMap的设计思想 HashMap的底层结构 本文主要是讲解jdk1.8中的HashMap源码,会对jdk1.7中的HashMap做一些简单的讲解用来和jdk1.8中的HashMap进行对比。 我们先通过下图来理解HashMap的底层结构: (https
深度解读ArrayMap优势与缺陷
ArrayMap在内存使用上较HashMap更有优势,在Android开发中广为使用的基础API,也是大家所推荐的方法, 但你是否想过Google如此重要的基础类存在缺陷?一、引言在移动设备端内存资源很珍贵,HashMap为实现快速查询带来了很大内存的浪费。为此,2013年5月20日Google工程师Dianne Hackborn在Android
一篇文章彻底读懂HashMap之HashMap源码解析
在秋招面试准备中博主找过很多关于HashMap的博客,但是秋招结束后回过头来看,感觉没有一篇全面、通俗易懂的讲解HashMap文章(可能是博主没有找到),所以在秋招结束后,写下了这篇文章,尽最大的努力把HashMap源码讲解的通俗易懂,并且尽量涵盖面试中HashMap的考察点。就博主的经历来看,HashMap是求职面试中名副其实的“明星”,基本上博主面试的每
【Java面试题】全网最全,近5年133个Java面试问题列表汇总,让你轻松拿大厂offer!!!!
133个Java面试问题列表汇总 前言Java 面试随着时间的改变而改变。在过去的日子里,当你知道 String 和 StringBuilder 的区别就能让你直接进第二轮面试但是现在问题变得越来越高级,面试官问的问题也更深入。 在我初入职场的时候,类似于 Vector 与 Array 的区别、HashMap 与 Hashtable 的区别是最流行的问题。
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
简简单单复习一哈HashMap
HashMap可被序列化,线程不安全,允许null值和null键,安全的MapCollections.synchronizedMap(): / Returns a synchronized (threadsafe) map backed by the specified map. In order to guarantee s
高级java面试题,附答案+考点
蚂蚁金服一面1. 两分钟的自我介绍2. 二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树 (红黑树)有什么区别3. B 树和 B+树的区别,为什么 MySQL 要使用 B+树4. HashMap 如何解决 Hash 冲突5. epoll 和 poll 的区别,及其应用场景6. 简述线程池原理,FixedThreadPoo
踩坑了!熬夜整理小米Android面试题
一、Java初中级面试题1.容器(HashMap、HashSet、LinkedList,HashSet等)2.内存模型3.JVM、Davilk、ART 三者的原理和区别4.垃圾回收机制5.类加载方案6.说说你对Java 反射的理解7.说说你对动态代理的理解8.什么是线程池,如何使用?为什么要使用线程池?9.在多线程运行过程中,解决安全性问题?10.设计模式(