Chinaunix首页 | 论坛 | 博客
  • 博客访问: 82460
  • 博文数量: 34
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 378
  • 用 户 组: 普通用户
  • 注册时间: 2017-01-17 11:19
个人简介

人的一生犹如负重致远,不可急躁。 以不自由为常事,则不觉不足。 心生欲望时,应回顾贫困之日。 心怀宽恕,视怒如敌,则能无视长久。 只知胜而不知敗,必害其身。 责人不如责己,不及胜于过之。

文章分类

全部博文(34)

文章存档

2018年(2)

2017年(32)

我的朋友

分类: Java

2017-02-22 22:58:37

Java容器HashMap

1  HashMap

HashMap是我们使用非常多的集合,它是基于哈希表的Map接口的实现,以key-value的形式存在。在HashMap中,key-value总是会当做一个整体来处理,系统会根据hash算法来计算key-value的存储位置,我们总是可以通过key快速地存取value。下面就来分析HashMap的存取。下面对HashMap源码的分析的是jdk1.8.0_65版本。

1.1  HashMap源码声明

        public class HashMap extends AbstractMap
                            implements
Map,Cloneable, Serializable {

HashMap实现了Map接口,继承AbstractMap。其中Map接口定义了键映射到值的规则,而AbstractMap类提供 Map 接口的骨干实现,以最大限度地减少实现此接口所需的工作,其实AbstractMap类已经实现了Map。

1.2  Hashmap构造函数

       HashMap的三个构造方法的源码声明:

                    public HashMap()
                    public
HashMap(int initialCapacity)
                    public
HashMap(int initialCapacity, float loadFactor)

HashMap():构造一个具有默认初始容量(16)和默认加载因子(0.75)的空HashMap。

HashMap(int initialCapacity):构造一个带指定初始容量和默认加载因子(0.75)的空 HashMap。

HashMap(int initialCapacity, float loadFactor):构造一个带指定初始容量和加载因子的空 HashMap。

在这里提到了两个参数:初始容量(initialCapacity),加载因子(loadFactor)。这两个参数是影响HashMap性能的重要参数,其中容量表示哈希表中桶的数量,初始容量是创建哈希表时的容量,加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。系统默认负载因子为0.75,一般情况下我们是无需修改的。

1.3  HashMap用的数据结构

HashMap是一种支持快速存取的数据结构,要了解它的性能必须要了解它的数据结构。Java中最常用的两种结构是数组和模拟指针(引用),几乎所有的数据结构都可以利用这两种来组合实现,HashMap也是如此,实际上HashMap是一个“链表散列”。

它的数据结构图:

从上图我们可以看出HashMap底层实现还是数组,只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。


阅读(226) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~