文档章节

HashMap工作原理

 虞旨立
发布于 2017/02/16 15:41
字数 1147
阅读 3
收藏 0

1.HashMap可以接受null键值和值,而Hashtable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对。

2.HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。

3.因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。

4.默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

5.当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

关于HashMap的问题

1.为什么String, Interger这样的wrapper类适合作为键? 

String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

2.我们可以使用自定义的对象作为键吗? 

这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。

3.我们可以使用CocurrentHashMap来代替Hashtable吗?

这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。

 

总结

HashMap的工作原理

HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

当两个不同的键对象的hashcode相同时会发生什么? 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。

 

 

本文转载自:http://atongyeye.iteye.com/blog/2357150

共有 人打赏支持
粉丝 1
博文 4
码字总数 1232
作品 0
宝山
程序员

暂无文章

VSCode 搭建Vue开发环境之Vue CLI

一、简介说明 1.关于VS Code开发工具,安装和配置,更多可以参考以前文章 2.关于Vue.js,Vue是一个优秀的渐进式前端框架,不仅易于上手,还便于与第三方库或既有项目整合。 3.关于Vue是使用方...

tianma3798
30分钟前
2
0
MySQL 相关博客整理

1. 《深入理解 MySQL 底层实现》 简评:文章从硬盘底层存储原理讲解到MySQL存储原理,其中涉及InnoDB 和 Myisam 中 B+Tree 的应用,以及常见数据库优化思路,算是一片很不错的讲解MySQL原理的...

科陆李明
41分钟前
2
0
pada rabbitmq server mangage

查看配置文件 ubuntu@node4:/etc/rabbitmq$ lltotal 28drwxr-xr-x 2 rabbitmq rabbitmq 4096 Jun 6 13:52 ./drwxr-xr-x 104 root root 12288 Sep 26 11:39 ../-rw-r--r-- ......

qwfys
48分钟前
0
0
SpringBoot进阶

慕课网链接 表单数据的验证 在pojo类属性的上面添加注解 @Entitypublic class Girl { @Id @GeneratedValue private Integer id; @NotBlank(message = "这个字段...

踏破铁鞋无觅处
55分钟前
1
0
【SylixOS】QT-QWS流程介绍

QWS简介 QWS(QT Windows System)是QT自行开发的窗口系统,体系结构类似X Windows的C/S结构。QWS Server在物理设备上显示,QWS Client实现界面,两者通过socket进行彼此的通讯。在很多嵌入式系...

suokin
55分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部