search
HomeDatabaseMysql TutorialJava中对HashMap的深度分析_MySQL

  在Java的世界里,无论类还是各种数据,其结构的处理是整个程序的逻辑以及性能的关键。由于本人接触了一个有关性能与逻辑同时并存的问题,于是就开始研究这方面的问题。找遍了大大小小的论坛,也把《Java 虚拟机规范》,《apress,.java.collections.(2001),.bm.ocr.6.0.shareconnector》,和《Thinking in Java》翻了也找不到很好的答案,于是一气之下把JDK的 src 解压出来研究,扩然开朗,遂写此文,跟大家分享感受和顺便验证我理解还有没有漏洞。 这里就拿HashMap来研究吧。

  HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取。但实际里面做了些什么呢?

  在这之前,先介绍一下负载因子和容量的属性。大家都知道其实一个 HashMap 的实际容量就 因子*容量,其默认值是 16×0.75=12; 这个很重要,对效率很一定影响!当存入HashMap的对象超过这个容量时,HashMap 就会重新构造存取表。这就是一个大问题,我后面慢慢介绍,反正,如果你已经知道你大概要存放多少个对象,最好设为该实际容量的能接受的数字。

  两个关键的方法,put和get:

  先有这样一个概念,HashMap是声明了 Map,Cloneable, Serializable 接口,和继承了 AbstractMap 类,里面的 Iterator 其实主要都是其内部类HashIterator 和其他几个 iterator 类实现,当然还有一个很重要的继承了Map.Entry 的 Entry 内部类,由于大家都有源代码,大家有兴趣可以看看这部分,我主要想说明的是 Entry 内部类。它包含了hash,value,key 和next 这四个属性,很重要。put的源码如下

  public Object put(Object key, Object value) {
  Object k = maskNull(key);

  这个就是判断键值是否为空,并不很深奥,其实如果为空,它会返回一个static Object 作为键值,这就是为什么HashMap允许空键值的原因。

  int hash = hash(k);
  int i = indexFor(hash, table.length);

  这连续的两步就是 HashMap 最牛的地方!研究完我都汗颜了,其中 hash 就是通过 key 这个Object的 hashcode 进行 hash,然后通过 indexFor 获得在Object table的索引值。

  table???不要惊讶,其实HashMap也神不到哪里去,它就是用 table 来放的。最牛的就是用 hash 能正确的返回索引。其中的hash算法,我跟JDK的作者 Doug 联系过,他建议我看看《The art of programing vol3》可恨的是,我之前就一直在找,我都找不到,他这样一提,我就更加急了,可惜口袋空空啊!!!

  不知道大家有没有留意 put 其实是一个有返回的方法,它会把相同键值的 put 覆盖掉并返回旧的值!如下方法彻底说明了 HashMap 的结构,其实就是一个表加上在相应位置的Entry的链表:

  for (Entry e = table[i]; e != null; e = e.next) {
  if (e.hash == hash && eq(k, e.key)) {
  Object oldvalue = e.value;
  e.value = value; //把新的值赋予给对应键值。
  e.recordAccess(this); //空方法,留待实现
  return oldvalue; //返回相同键值的对应的旧的值。
  }
  }
  modCount++; //结构性更改的次数
  addEntry(hash, k, value, i); //添加新元素,关键所在!
  return null; //没有相同的键值返回
  }

  我们把关键的方法拿出来分析:

  void addEntry(int hash, Object key, Object value, int bucketIndex) {
  table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);

  因为 hash 的算法有可能令不同的键值有相同的hash码并有相同的table索引,如:key=“33”和key=Object g的hash都是-8901334,那它经过indexfor之后的索引一定都为i,这样在new的时候这个Entry的next就会指向这个原本的table[i],再有下一个也如此,形成一个链表,和put的循环对定e.next获得旧的值。到这里,HashMap的结构,大家也十分明白了吧?

  if (size++ >= threshold) //这个threshold就是能实际容纳的量
  resize(2 * table.length); //超出这个容量就会将Object table重构

  所谓的重构也不神,就是建一个两倍大的table(我在别的论坛上看到有人说是两倍加1,把我骗了),然后再一个个indexfor进去!注意!!这就是效率!!如果你能让你的HashMap不需要重构那么多次,效率会大大提高!

  说到这里也差不多了,get比put简单得多,大家,了解put,get也差不了多少了。对于collections我是认为,它是适合广泛的,当不完全适合特有的,如果大家的程序需要特殊的用途,自己写吧,其实很简单。(作者是这样跟我说的,他还建议我用LinkedHashMap,我看了源码以后发现,LinkHashMap其实就是继承HashMap的,然后override相应的方法,有兴趣的同人,自己looklook)建个 Object table,写相应的算法,就ok啦。

  举个例子吧,像 Vector,list 啊什么的其实都很简单,最多就多了的同步的声明,其实如果要实现像Vector那种,插入,删除不多的,可以用一个Object table来实现,按索引存取,添加等。

  如果插入,删除比较多的,可以建两个Object table,然后每个元素用含有next结构的,一个table存,如果要插入到i,但是i已经有元素,用next连起来,然后size++,并在另一个table记录其位置。



Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
hashmap的扩容机制是什么hashmap的扩容机制是什么Mar 15, 2023 pm 03:39 PM

hashmap的扩容机制是:重新计算容量,用一个新的数组替换原来的数组。重新计算原数组的所有数据并插入一个新数组,然后指向新数组;如果数组在容量扩展前已达到最大值,则直接将阈值设置为最大整数返回。

php如何实现Redis的Hash操作php如何实现Redis的Hash操作May 30, 2023 am 08:58 AM

Hash操作//为hash表中的字段赋值。成功返回1,失败返回0。若hash表不存在会先创建表再赋值,若字段已存在会覆盖旧值。$ret=$redis->hSet('user','realname','jetwu');//获取hash表中指定字段的值。若hash表不存在则返回false。$ret=$redis->hGet('user','rea

java中LinkedHashMap和HashMap区别是什么java中LinkedHashMap和HashMap区别是什么May 02, 2023 am 08:31 AM

1、说明Map基本上可以使用HashMap,但是HashMap有一个问题,那就是迭代HashMap的顺序不是HashMap放置的顺序,就是无序。HashMap的这个缺点往往会带来麻烦,因为有些场景我们期待一个有序的Map,这就是LinkedHashMap。2、区别实例publicstaticvoidmain(String[]args){Mapmap=newLinkedHashMap();map.put("apple","苹果");map.put("

Java单例模式怎么利用HashMap实现缓存数据Java单例模式怎么利用HashMap实现缓存数据May 13, 2023 am 09:43 AM

一、单例模式是什么?单例模式是一种对象创建模式,它用于产生一个对象的具体实例,它可以确保系统中一个类只产生一个实例。Java里面实现的单例是一个虚拟机的范围,因为装载类的功能是虚拟机的,所以一个虚拟机在通过自己的ClassLoad装载实现单例类的时候就会创建一个类的实例。在Java语言中,这样的行为能带来两大好处:1.对于频繁使用的对象,可以省略创建对象所花费的时间,这对于那些重量级对象而言,是非常可观的一笔系统开销;2.由于new操作的次数减少,因而对系统内存的使用频率也会降低,这将减轻GC压

Java使用HashMap类的putAll()函数将一个Map添加到另一个Map中Java使用HashMap类的putAll()函数将一个Map添加到另一个Map中Jul 24, 2023 am 09:36 AM

Java使用HashMap类的putAll()函数将一个Map添加到另一个Map中Map是Java中常用的数据结构,用来表示键值对的集合。在Java的集合框架中,HashMap是一个常用的实现类。它提供了putAll()函数,用于将一个Map添加到另一个Map中,方便实现数据的合并和拷贝。本文将介绍putAll()函数的使用方法,并提供相应的代码示例。首先,

Laravel开发:如何使用Laravel Hash生成密码散列?Laravel开发:如何使用Laravel Hash生成密码散列?Jun 17, 2023 am 10:59 AM

Laravel是目前最为流行的PHPweb框架之一,为开发人员提供了许多强大的功能和组件,其中LaravelHash也是其中之一。LaravelHash是一个用于密码散列的PHP库,其可以用于保护密码的安全,并使应用程序的用户数据更加安全。在本文中,我们将了解LaravelHash的工作原理以及如何使用它来对密码进行散列和验证。前置知识在学习Lara

基于Java HashMap,如何解决插入重复的Key值问题基于Java HashMap,如何解决插入重复的Key值问题May 09, 2023 am 10:52 AM

javaHashMap插入重复Key值要在HashMap中插入重复的值,首先需要弄清楚HashMap里面是怎么存放元素的。put方法Map里面存放的每一个元素都是key-value这样的键值对,而且都是通过put方法进行添加的,而且相同的key在Map中只会有一个与之关联的value存在。put方法在Map中的定义如下。Vput(Kkey,Vvalue);put()方法实现:首先hash(key)得到key的hashcode(),hashmap根据获得的hashcode找到要插入的位置所在的链,

Java中使用HashMap类的keySet()方法获取映射中所有的键Java中使用HashMap类的keySet()方法获取映射中所有的键Jul 24, 2023 pm 12:24 PM

Java中使用HashMap类的keySet()方法获取映射中所有的键HashMap是Java中常用的集合类之一,它提供了一种映射关系,可以通过键值对的方式存储和访问数据。在实际开发中,我们经常需要获取HashMap中所有的键,以便进行相应的处理。而HashMap提供的keySet()方法正是用来获取映射中所有键的方法。keySet()方法是HashMap类

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
1 months agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.