源码分析之HashMap

末蓝、 2022-07-26 01:49 231阅读 0赞

# 源码分析之HashMap #

## 1、概述 ##

HashMap是java中很常用的一种数据结构，**其存储和检索的速度非常的快(基于数组和散列函数实现)**。HashMap也是很多面试官比较喜欢问的一种数据结构。**HashMap不是线程安全的**，如在多线程环境下可以使用Collections辅助类的synchronizedMap()方法将其转为同步的来使用或使用并发包下的ConcurrentHashMap数据结构。

--------------------

## 2、数据结构 ##

HashMap实现原理图  
![HashMap实现原理图][HashMap]

#### 说明 ####

Map接口将一组键值对当做一个entry对待，存放在数组下标中。如果存在hash冲突的时候那么就以链表形式存放在数组中。jdk1.8开始，如果冲突数比较多的时候(大于16)，会采用树形结构来存冲突的元素。  
**备注:数组和指针(对java而言:理解为引用)可以实现任何数据结构。**

--------------------

## 3、HashMap部分源码展示 ##

**HashMap层次结构和成员属性**

public class HashMap<K,V> extends AbstractMap<K,V> 
    implements Map<K,V>, Cloneable, Serializable
    {
    
        //默认初始容量16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        //最大容量
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        //负载因子(Map容器中元素个数/容器大小(数组长度))
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        //空Entry<?,?>数组
        static final Entry<?,?>[] EMPTY_TABLE = {};
    
        //空entry<K,V>数组,注意是transient修饰
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
        //Map中元素个数(entry个数)
        transient int size;
    
        //The next size value at which to resize (capacity * load factor).
        //thread=capacity * load factor
        int threshold;
    
        //负载因子
        final float loadFactor;
    
        //Map修改次数
        transient int modCount;
    }

--------------------

**HashMap 插入元素代码**

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
    
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

**备注**:原理就是对key计算hash值然后确定在entry数组中的下标，存储起来。如果key已经存在那么就覆盖原先值，如果hash值相等则加到链表上。

--------------------

**HashMap 获取key对应的value代码**

public V get(Object key) {
        if (key == null)
            return getForNullKey();//获得null对应的value值
        Entry<K,V> entry = getEntry(key);
    
        return null == entry ? null : entry.getValue();
    }
    
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
    
        int hash = (key == null) ? 0 : hash(key);
        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;
    }

--------------------

## 4、注意说明 ##

1、HashMap的继承和实现层次(继承AbstractMap实现Map接口)
    2、键值对存储方式(Entry(key,value)) 
    3、HashMap的大小和加载因子loadFactor(默认0.75),由碰撞率决定
    4、HashMap查找和插入通常都是O(1)的算法复杂度,非常快。特殊情况:查询遇到碰撞要链表(树)、插入遇到需要扩容的时候
    5、HashMap使用的算法是散列函数算法(不可逆的函数),通过二次计算key的hashCode值决定value该插入到数组的下标
    6、由于Map接口是没有实现Iterator迭代器接口的,所以遍历HashMap元素时是无法使用迭代器的,可以使用EntrySet方法来获得Map内的元素
    7、由于java.util下的Map不是并发Map所以当在多线程编程时,推荐使用并发包下的ConcurrentHashMap对象,或使用Collections. synchronizedMap(Map map);
    8、工作中HashMap使用的非常广,大多数语言都会支持这种结构的存储,通常称字典、映射其实都是一个意思。
    9、Hash算法(散列算法)很重要,MD5、SHA等摘要算法使用的就是散列算法(不可逆)
    10、正因为HashMap使用了散列算法所以HashMap是无法保证元素插入的顺序的,迭代出来是无序的
    11、jdk1.8当某个下标下发生碰撞节点大于八个的时候,就会使用红黑树来存储这些节点,否则使用单向链表存储      
    备注:JDK1.8对HashMap的实现稍做了些变动(引入了Node<K,V> 是实现Entry<K,V>的),但是大体的思路是没有变得,1.7的源码更加清晰,1.8源码更复杂了些。推荐先看1. 7之后再看1.8源码

--------------------

### 对HashMap的简单理解 ###

HashMap理解拆分:
    数组部分:Entry[] tables=new Entry[16];Length默认16<br>
    确定数组下标:对key的二次Hash算法取值,然后对tables数组长度取模,假如取模结果为3,那么就存储在tables[2]位置
    冲突存储:插入循环上一步操作,如果遇到tables[n]已经存在元素了,那么就使用链表来存储该下标下的多个元素
    扩容重分布:当Map中的元素大于12(loadFactor*Length)时就要进行tables扩容了,重新散列分布之前存储的值了,
    对HashMap扩容是比较耗时的

--------------------

### 对Hash函数的理解 ###

Hash函数即散列函数，站在数学角度对于y=f(x);如果每次传递不同的x获得的y都不同，那么该散列函数就是一个设计比较好的散列函数。散列函数是不可逆的，对计算越简便和散列越分散那就是一个好的散列函数。

--------------------

## 总结: ##

**对于HashMap的源码研究其实并不难，重点在于掌握其使用的数据结构数组、链表、树以及一个很重要的hash(散列函数)算法。站在数学角度即是单射。HashMap多用于存储和检索比较频繁的场景下，其遍历通常需要借组entrySet方法。**

## 参考 ##

1.  [http://www.cnblogs.com/leesf456/p/5242233.html][http_www.cnblogs.com_leesf456_p_5242233.html]
2.  [http://beginnersbook.com/2014/08/java-hashmap-class/][http_beginnersbook.com_2014_08_java-hashmap-class]
3.  [http://blog.csdn.net/ns\_code/article/details/36034955][http_blog.csdn.net_ns_code_article_details_36034955]
4.  [https://www.ibm.com/developerworks/cn/java/j-lo-hash/][https_www.ibm.com_developerworks_cn_java_j-lo-hash]
5.  [https://www.ibm.com/developerworks/cn/java/j-jtp05273/][https_www.ibm.com_developerworks_cn_java_j-jtp05273]

[HashMap]: http://i.imgur.com/vTNjN8h.jpg
[http_www.cnblogs.com_leesf456_p_5242233.html]: http://www.cnblogs.com/leesf456/p/5242233.html
[http_beginnersbook.com_2014_08_java-hashmap-class]: http://beginnersbook.com/2014/08/java-hashmap-class/
[http_blog.csdn.net_ns_code_article_details_36034955]: http://blog.csdn.net/ns_code/article/details/36034955
[https_www.ibm.com_developerworks_cn_java_j-lo-hash]: https://www.ibm.com/developerworks/cn/java/j-lo-hash/
[https_www.ibm.com_developerworks_cn_java_j-jtp05273]: https://www.ibm.com/developerworks/cn/java/j-jtp05273/