概述
在Java集合中，Map是一种特殊的集合，原因在于这种集合容器并不是保存单个元素，而是保存一个一个的Key-Vaue键值对.HashMap是基于哈希表的Map接口的实现,在项目开发中使用广泛,下面就对HashMap的源码进行解析.
Hashmap的特点
1.HashMap是基于哈希表的Map实现.
2.HashMap底层采用的是Entry数组(1.7)和链表实现.
3.HashMap是采用key-value形式存储,其中key是可以允许为null,但是只能有一个,并且key不能重复.
4.HashMap是线程不安全的.
5.HashMap存入数据的顺序和遍历的顺序有可能是不一样的.
在HashMap中存在很多的方法,在此我们只对添加、删除、遍历等方法进行解析.以便了解其原理.
Hashmap的数据结构
在数据结构中,有数组和链表来实现对数据的存储,但这两者基本上是两个极端.
- 数组: 数组储存区间是连续的,占用内存严重,故空间复杂度很大.但数组的二分查找时间复杂度小,为O(1);
数组的特点是寻址容易,插入和删除困难 - 链表：链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N).
链表的特点是寻址困难,插入和删除容易
那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是哈希表,哈希表即满足了数据查找的方便,同时不占用太多的内存空间,使用也十分方便.
HashMap底层使用的就是哈希表.
HashMap实际上是一个"链表"的数组,每个数组中的元素存放链表的头结点,在每一个头结点的中,包含着下一个节点的地址,即数组和链表的结合体.
更为详细的结构如下:
从上图可以看到,HashMap底层就是一个数组结构,数组中的每一项又是一个链表.
原理
1、HashMap的工作原理
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？
它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。
区别：
（1）时间
hashTable是java发布的时候提供的键值映射的数据结构、hashMap是在jdk1.2之后出现的。但是hashTable现在几乎弃用，虽然它是线程安全，但是ConcurrentHashMap却可以替代并且效率更好
（2）提供的接口不同
hashtable相比hashMap多提供了2个接口elements()和contains()。其中elements()返回hashTable的中value的枚举。contains()判断传入的value是否包含在hashTable中。
（3）继承的类不同
hashMap继承AbstractMap类、而hashTable继承自Dictionary类。相同的是同实现了map、Cloneable、Serializable接口
（4）HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。
（5）HashMap是非synchronized， 而Hashtable是synchronized， 这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
（6）另一个区别是HashMap的迭代器(Iterator)是fail-fast（快速失败）迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。但是在jdk8之后hashTable的迭代器也加入了fail-fast迭代器。
（7）初始容量大小和每次扩充容量大小的不同
Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
之所以会有这样的不同，是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀，使得哈希冲突减少。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时，如果模数是2的幂，那么我们可以直接使用位运算来得到结果，效率要大大高于做除法。HashMap为了加快hash的速度，将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题，所以HashMap为解决这问题，又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同 。
（8）计算hash值的方法不同
为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。
Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数发来获得最终的位置。
Hashtable在计算元素的位置时需要进行一次除法运算，而除法运算是比较耗时的。
HashMap为了提高计算效率，将哈希表的大小固定为了2的幂，这样在取模预算时，不需要做除法，只需要做位运算。位运算比除法的效率要高很多。
HashMap的效率虽然提高了，但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高，而计算位运算。
为了解决这个问题，HashMap重新根据hashcode计算hash值后，又对hash值做了一些运算来打散数据。使得取得的位置更加分散，从而减少了hash冲突。当然了，为了高效，HashMap只做了一些简单的位处理。从而不至于把使用2 的幂次方带来的效率提升给抵消掉。
HashMap的部分源码:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{//初始化桶大小,也就是数组的大小,默认大小为16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//桶的最大值static final int MAXIMUM_CAPACITY = 1 << 30;//默认的负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//存放数据的数组transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//存储key-value键值对的个数transient int size;//桶大小,在初始的时候可以显式指定(一定是2的次幂)int threshold;//负载因子,初始化时可以显式指定final float loadFactor;//修改次数,每次map集合变动一次,就加1transient int modCount;//真正存放数据的entry内部类static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;...省略其他}HashMap的构造函数
-
HashMap(): 构造一个具有默认初始容量(16)和默认加载因子(0.75)的空HashMap
-
HashMap(int initialCapacity): 构造一个带指定初始容量和默认加载因子的空HashMap.
-
HashMap(int initialCapacity, float loadFactor): 构造一个带指定初始容量和指定负载因子的空HashMap.
-
HashMap(Map<? extends K, ? extends V> m): 根据指定的map集合创建一个HashMap.
代码实例：
public HashMap(int initialCapacity, float loadFactor) {//如果初始容量小于0,则抛出一个异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//如果指定的初始化大小大于最大值,则将容量置为最大值.if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;//如果负载因子不是数字或者小于等于0,抛出异常if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);//让当前map的容器大小和加载因子等于指定的值 this.loadFactor = loadFactor;threshold = initialCapacity;//初始化方法,在HashMap中没有实现,其子类有具体实现.init();}我们看到,在初始化的时候,没有为table数组分配内存空间,而是在put操作的时候才真正构建table数组.
初始容量和负载因子
在HashMap的属性中,有两个参数:初始容量,负载因子.
这两个参数是影响HashMap性能的重要参数.
其中容量表示哈希表中桶的数量,也就是数组的长度.初始容量是创建哈希表时的容量,如果不指定,默认是16.
加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度,它可以衡量一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之越小.
查看put方法的源码可知:
当哈希表中数据的数量超出了当前容量*加载因子时,对该HashMap进行扩容,将容量扩充至两倍的桶数
HashMap的put方法
public V put(K key, V value) {//如果table数组为空{},则为table初始化分配内存空间,入参为threshold,默认是16if (table == EMPTY_TABLE) {inflateTable(threshold);}//如果key为null,保存null于table的第一个位置,也就是table[0]if (key == null)return putForNullKey(value);//根据ket计算出hash值int hash = hash(key);//计算出该key所应该保存的桶位置,也就是在数组table中的位置int i = indexFor(hash, table.length);for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;//遍历该索引位置的桶链表,如果存在相同的key,用老值替换新值,返回老值if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//修改次数增加1modCount++;//根据key-value新增一个Entry对象写入当前位置addEntry(hash, key, value, i);return null;}通过源码我们可以很清晰的看到put方法的执行逻辑:
- 首先判断HashMap中的table表是不是为空,如果为空,调用inflateTable(threshold)方法为table分配内存空间
- 然后判断key是否为空,如果key为空,则调用putForNullKey(value)方法,将value放在数组的第一个位置上.
- 若key不为空,则根据hash(key)方法计算出hash值,然后根据hash值,得到这个元素在table数组中的位置(下标),如果table在该位置已经存放了其他元素,则通过比较是否存在相同key,若存在则覆盖原来key的value,否则将该元素保存在链头.
- 若table所在该处没有元素,那就直接将该元素放到此数组中的该位置上.
至此完成来了put方法的全过程
HashMap的get方法
public V get(Object key) {//如果key为null,直接去table[0]处检索.if (key == null)return getForNullKey();//查找出map中对应key的entry对象Entry<K,V> entry = getEntry(key);//如果value不存在就返回null,否则返回对应的valuereturn null == entry ? null : entry.getValue();}在具体的getEntry()方法中:
final Entry<K,V> getEntry(Object key) {if (size == 0) {return null;}//计算出key对应的hash值int hash = (key == null) ? 0 : hash(key);//获取最终数组中的索引,遍历链表,通过equals方法找出对应的entry对象返回.for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}get方法相对比较简单:从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
