Hashmap_map hashmap-程序员宅基地

技术标签: java  hashmap  

Hashmap是java面试中经常被问的问题,其重要性不言而喻。这不禁想起HashMap和Hashtable的比较:

  1. HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
  2. HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
  3. HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
  4. 由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。HashMap不能保证随着时间的推移Map中的元素次序是不变的。
  5. HashMap几乎可以等价于Hashtable,那为什么用Hashmap呢?因为它快啊。Haspmap实现了Map接口,说起Map,我们就想起了put和get方法,那我们就讲一下Hashmap怎么在get方法上成为快男的。

性能是映射表的一个重要问,当我们应用get()方法,如果使用线性搜索的话,执行速度会很慢,这正是hashmap提高速度的地方。Hashmap使用了特殊的值,称作散列码,来取代对键的缓慢搜索。散列码是相对唯一的,用以代表对象的int值。hashcode()是根类Object的方法,因此所有Java对象都能产生散列码,Hashmap就是使用对象的hashcode进行快速查询,因此hashmap能显著提升性能。


数据结构的物理存储结构只有两种:顺序存储结构和链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而HashMap采用了链地址法,也就是数组+链表的方式。

既然我们了解了hashmap的基本数据结构,那hashmap的实现原理是怎样的呢?
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对,Entry是HashMap中的一个静态内部类。 所以,HashMap的整体结构如下
HashMap结构图
HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象,HashMap是在bucket中储存键对象和值对象,作为Map.Entry。

HashMap由数组+链表组成的,这样的数据结构有什么用呢?
HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度依然为O(1),因为最新的Entry会插入链表头部,急需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

当两个对象就算hashcode相同,但是它们可能并不相等,怎么解决呢?
这就是HashMap中的碰撞问题,了解了hashmap特殊的数据结构是不是恍然大悟啊。因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

hashmap这样的数据结构,怎么使用get方法来获取值对象呢?
当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,然后获取值对象。当hashcode相同,它们的bucket位置可能有两个对象,我们就需要找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_39445733/article/details/79409572

智能推荐

状态机图 java_文本处理(一)状态机(1)-程序员宅基地

文章浏览阅读176次。系统程序员成长计划-文本处理(一)状态机(1)o 有穷状态机的形式定义有穷状态机是一个五元组 (Q,Σ,δ,q0,F),其中:Q是一个有穷集合,称为状态集。Σ是一个有穷集合,称为字母表。δ: Q xΣQ称为状态转移函数。q0 是初始状态。F 是接受状态集。教科书上是这样定义有穷自动机的,这个形式定义精确的描述了有穷状态机的含义。但是大部分人(包括我自己)第一次看到它时,反复的读上几遍,仍然不知道..._自动门的控制器 有穷状态机

Beyond Compare4如何通过密钥连接SFTP进行文件夹的比较_beyondcompare连接sftp服务器-程序员宅基地

文章浏览阅读1.5k次。在网上搜索了很久没有找到相对应的资源特发布一篇关于此类的文章_beyondcompare连接sftp服务器

AndroidStudio项目提交到github以及工作中实际运用(详细步骤)_guihut readme 加载流程图-程序员宅基地

文章浏览阅读836次,点赞2次,收藏3次。在使用studio开发的项目过程中有时候我们想将项目发布到github上,以前都是用一种比较麻烦的方式(cmd)进行提交,最近发现studio其实是自带这种功能的,终于可以摆脱命令行了。 因为自己也没有做很深的研究,这里就先分享一下通过studio将自己的项目上传到github上的步骤。两个相关概念:git和githubGit是一个开源的分布式版本控制系统,用以有效、高速的处理从很小到非常大的项_guihut readme 加载流程图

oracle12c1使用远程图形进行安装_麒麟安装oracle12c数据库-程序员宅基地

文章浏览阅读1.9k次,点赞3次,收藏4次。应为最近安装了好几次了,而且每次使用静默安装12c1版都会失败,所以索性就记录一下图形化安装,方便后期的使用。_麒麟安装oracle12c数据库

office 2016出现错误,无法启动程序。。。是怎么回事?如何解决?_无法启动office 错误代码147-0-程序员宅基地

文章浏览阅读1.1w次,点赞4次,收藏2次。我刚刚在自己电脑上解决了相同的问题,将方法发上来供参考: 打开“服务”,在里面找到Microsoft Office ClickToRun Service服务,将它关闭,再启动,调成自动; 如果提示无法开启服务也可以这样操作亲测有效..._无法启动office 错误代码147-0

CSU 1558 和与积_多个数的和与积相等 bzoj-程序员宅基地

文章浏览阅读977次。CSU 1558 和与积 Time Limit: 1 Sec Memory Limit: 128 MB Special Judge Submit: 121 Solved: 69 Description构造N个正数(每个数不超过1000000),使所有数的和与所有数的积相差刚好等于D,按非递减序输出。Input多组测试数据(不超过1000组),每行两个正整数N和D。(2<=N<=1000,_多个数的和与积相等 bzoj

随便推点

初始化vector实例的7种方法_创建和初始化vector的方法,每种都给出一个实例?当然也可以把deque与list写出来-程序员宅基地

文章浏览阅读1.4k次。转载 https://blog.csdn.net/qiaoruozhuo/article/details/52086286/* Name: Copyright: Author: Date: 01-08-16 16:01 Description: 初始化vector实例的7种方法 */ #include&lt;iostream&gt; #..._创建和初始化vector的方法,每种都给出一个实例?当然也可以把deque与list写出来

免费开通PTrade与QMT量化交易系统_ptrade交易系统官网-程序员宅基地

文章浏览阅读1.2w次,点赞2次,收藏12次。免费的券商量化系统开通,急速、安全_ptrade交易系统官网

c语言中set 函数,C里边的STL里边的Set函数-程序员宅基地

文章浏览阅读2.2k次。set函数的用法:这是一个集合函数,这个函数可以处理很多的元素,这些元素可以去重,把相同的元素都去掉,剩下不一样的元素,而且还可以自动给这些元素来排序,从小到大的顺序来排序。这里我们先来举个例子:比如:#include #include using namespace std; int main() { set a; a.insert(1); a.insert(9); a.insert(6); a..._c语言set

牛笔了!字节跳动大佬整理:CSS 核心知识(万字长文,值得收藏!)_字节跳动公司 reset css-程序员宅基地

文章浏览阅读1.1k次,点赞4次,收藏14次。本篇文章围绕了 CSS 的核心知识点和项目中常见的需求来展开。虽然行文偏长,但较基础,适合初级中级前端阅读,阅读的时候请适当跳过已经掌握的部分。这篇文章断断续续写了比较久,也参考了许多优秀的文章,但或许文章里还是存在不好或不对的地方,请多多指教,可以评论里直接提出来哈。小tip:后续内容更精彩哦。核心概念和知识点语法CSS 的核心功能是将 CSS 属性设定为特定的值。一个属性与值的键值对被称为声明(declaration)。color: red;复制代码而如果将一个或者多个声明用 {} _字节跳动公司 reset css

Shell读取mysql数据_while read -a row+读取sql查询结果+shell-程序员宅基地

文章浏览阅读762次。今天有个需求需要写个shell读取mysql记录,操作一些文件,搜索了一下踩了些坑记录一下shell2.0写法注释:注意"done< <(“的写法,第一个”<“要和"done"之间没空格,两个”<“之间有一个空格,”<" 和"("之间没空格COMMAND1="mysql -h${HOSTNAME} -P${PORT} -u${USERNAME} -p${PASSWORD} ${DBNAME}e.g.while read -a rowdo echo "._while read -a row+读取sql查询结果+shell

汉明码_cdsn 汉明-程序员宅基地

文章浏览阅读4k次,点赞7次,收藏37次。汉明码实现原理汉明码(Hamming Code)是广泛用于内存和磁盘纠错的编码。汉明码不仅可以用来检测转移数据时发生的错误,还可以用来修正错误。(要注意的是,汉明码只能发现和修正一位错误,对于两位或者两位以上的错误无法正确和发现)。汉明码的实现原则是在原来的数据的插入k位数据作为校验位,把原来的N为数据变为m(m = n +k)位编码。其中编码时要满足以下原则:2^k - 1 &gt..._cdsn 汉明