HashMap的理解

公众号:码农乐园 等级 814 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。
收藏
评论区

相关推荐

3 手写Java HashMap核心源码
手写Java HashMap核心源码 上一章手写LinkedList核心源码,本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash map,map是映射的意思,HashMap就是用hash进行映射的意思。不明白?没关系。我们来具体讲解一下HashMap的原理。 HashMap
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
推荐程序员面试秘籍!2021年大厂Java岗面试必问
01 JAVA基础 1.1 java知识点 Hashmap 源码级掌握,扩容,红黑树,最小树化容量,hash冲突解决,有些面试官会提出发自灵魂的审问,比如为什么是红黑树,别的树不可以吗;为什么8的时候树化,4不可以吗,等等 concureentHashMap,段锁,如何分段,和hashmap在hash上的区别,性能,等等 HashTable ,同步锁,这块可
10 HashSet HashMap源码 Properties
2 HashSet底层是使用HashMap实现的。当使用add方法将对象添加到Set当中时,实际上是将该对象作为**底层所维护的Map对象的key**,而value则都是同一个Object对象(该对象我们用不上); 3\. HashMap底层维护一个Node数组,我们向HashMap中所放置的对象实际上是存储在该数组当中; HashMap中的Pu
Java中HashMap的实现原理
**总结:HashMap的实现原理:** 1. **利用key的hashCode重新hash计算出当前对象的元素在数组中的下标** 2. **存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中** 3. **获取时,直接找到hash值对应
java HashMap hash方法分析
下面分别分析下,JDK1.7 与 JDK1.8 中 hash方法的运算过程,并且左后结合JDK1.8 中 hash方法来进行详细说明。 JDK1.7 中HashMap 中hash table 定位算法:  int hash = hash(key.hashCode());  int i = indexFor(hash, table.length);  
java基础之HashMap——第一节
前两篇文章粗略的介绍了java中的List,既然已经讲了两种java的数据结构,那么这篇就接着讲java中的数据结构了。 HashMap作为最常用的一种Map,就放在第一个讲了。 Map是一个较复杂的结构,本身内容不是太难,但是各个实现的思想完全不同,所以可能关于Map的介绍会比较多,源码分析会放在后边,主要是算法分析。 要讲HashM
Collectors.groupingBy分组后的排序问题
默认groupingBy代码里会生成一个HashMap(hashMap是无序的,put的顺序与get的顺序不一致) * HashMap是无序的,HashMap在put的时候是根据key的hashcode进行hash然后放入对应的地方。所以在按照一定顺序put进HashMap中,然后遍历出HashMap的顺序跟put的顺序不同(除非在put的时候key已
GridView实现九宫格
GridView gv=(GridView)findViewById(R.id.g1);         ArrayList<HashMap<String,Object>>data=new ArrayList<HashMap<String, Object>>();         for(int i=0;i<images.length;i++)
HashMap 怎么 hash?又如何 map?
HashMap 是 Java 中 Map 的一个实现类,它是一个双列结构(数据+链表),这样的结构使得它的查询和插入效率都很高。HashMap 允许 null 键和值,它的键唯一,元素的存储无序,并且它是线程不安全的。 ![](https://oscimg.oschina.net/oscnet/24e81018b69298cf434a8eb39682070
HashMap中神奇的h & (length
众所周知,HashMap是基于Hash表的Map接口实现,HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。但是知道了Hash值之后,又是怎么确定出key在数组中的索引呢? 根据源码得知如下方法 static
HashMap多线程下死循环的坑记录
**PS:不得不说Java编程思想这本书是真心强大..** **学习内容:** **1.HashMap<K,V>在多线程的情况下出现的死循环现象** **当初学Java的时候只是知道HashMap<K,V>在并发的情况下使用的话,会出现线程安全问题,但是一直都没有进行深入的研究,也是最近实验室的徒弟在问起这个问题的原因之后,才开始进行了一个深入的研究
HashMap解惑
 HashMap中有一些我们容易忽视的点 1\. 关于key的hash和equals public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); }