Java容器HashMap

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就代表了该数组的长度。