浅析HashMap（上）

version 0.2

[TOC]

介绍：

HashMap是平时工作开发经常接触的数据结构，但很多时候疏于查看原理，在使用过程中会发生一些问题。最近根据自己所学与参考记录一下。结合其他相近数据结构HashTable，LinkedHashMap,ConcurrentHashMap等展开分析梳理。

Java中对Map定义了接口java.util.Map，主要有HashMap，HashTable,LinkedHashMap,TreeMap四种常用实现类。继承关系如图所示（我盗用的美团的）

简单区分一下各自的特点：

1. HashMap：根据键的哈希值来存储数据，内部大体是数组+链表结构，很多情况下可以直接从数组的位置直接获取到值，因此有很快的访问速度。同时允许至多一条键为null的数据存入，而值的null不限制。缺点是虽然访问速度很快，但是遍历的顺序是不确定的，也不保证在结构变动后元素顺序不变化，所以HashMap如果直接用来表示顺序很多情况是不满足的，同时它的每个操作也不是线程安全，在并发情况容易产生问题，JDK 1.8之前甚至可能产生死循环（头插法变动导致环产生），但可以用Collections类中的synchronizedMap()来包装实现线程安全的能力，本质上也是采用synchronized来加锁。
2. HashTable：相较于线程不安全的HashMap,HashTable在以前编程初期经常用来当做解决各种奇怪问题的解药。由于内部对数据结构修改的方法都是用synchronized修饰，所以是线程安全的，同一时间只有一个线程能进行写操作，所以并发性受到限制。在JDK 1.5后用ConcurrentHashMap类来代替，相较于暴力的大段加锁，ConcurrentHashMap采用分段锁等优化（ConcurrentHashMap本身的优化也具有迭代性是一个持续性的表现比如对分段锁的懒加载，volatile等操作）
3. LinkedHashMap：是HashMap的子类，通过引入新的辅助双向链表使得结构支持表示顺序，如插入顺序或访问顺序。其中将构造函数LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)中传入 accessOrder 为 true时支持按照访问顺序遍历的特性，基于这个数据结构的天然特性安卓的很多LRU缓存机制都能见到它的身影。
4. TreeMap：实现了SortedMap接口，会根据键值的hashCode做排序，默认是升序，也可以指定排序的比较器，在迭代时可以按照需要的情况遍历数据。同时由于涉及排序，所以key一定要实现Comparable接口，或者在构造时传入自定义的比较器Comparator，否则会抛出java.lang.ClassCastException异常。

在介绍上面四种常见Map类型时我们发现很多情况这个为了实现这种映射关系时都必须要保证一个大前提，那就是key的值要是不可变的。简而言之就是在他们存入Map后，它的hashCode一定不能变更，否则很可能下次查找就找不到需要的数据位置。所以我打算从hashCode讲起。

如何确定哈希值

在开发过程中，我们在覆写对象equals（）方法后常常需要覆写hashCode()，那么不覆写会产生什么问题呢？

我们知道在Java中如果不覆写对象的equals（）方法，在用equals（）进行比较时默认使用内存地址进行比较的，那很多情况物理上是不一样的对象但逻辑上可能是相同的对象。比如从反序列化中读取到的数据，这个是新的对象，但逻辑上可能和我们实际来说是一个。这个时候如果我们覆写了equals（）方法，加入了具体的判断逻辑，比如:

如果加入覆写逻辑则可以为相同：

那为什么还要覆写hashCode呢？
这是由于java.lang.Object中对于hashCode的约定：

简而言之就是：运行期间如果两个对象的equals判定为一样，那么hashCode一定一样，反之如果equals不一样，那么hashCode一定不一样，同时在对象比较的方法内信息如果没有改动的话必须每次hashCode值还是一样。

所以当我们改动了判定的信息条件时，也必须改动合理的hashCode判断方法以确保我们符合这个定义。但同时需要谨慎区分，如果equals一样那么两个对象一定一样。但由于存在哈希碰撞，反之我们并不能确保相同的hashCode代表同一个对象。

哈希的计算方式一定要尽量散列，让不同对象尽可能产生不同的值来减少碰撞，这样才能用此来当做一种消息摘要来快速比对是否是同一个内容。

好在这种头疼的问题大多数情况不用我们考虑，默认的hashCode()方法已经能满足我们大部分情况。但思考一个问题，既然是随机散列，那么就一定可能产生负数，而我们知道在数组中是必须从0开始的自然数，很多时候还需要做进一步处理，比如HashTable中会将hashCode再与一个大素数计算得到正数再放入数组中。

这样我们便能通过简单的一次计算快速得到数据在数组中的存储位置，以此来提高访问性能。

大体结构

从实现上来说，HashMap的结构是数组+ （链表/红黑树）结合

这里是JDK 1.8 ，之前没有转换红黑树的过程。
其中HashMap一个重要的字段就是 Node[] table即哈希桶数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

本质上没一个Node都是一个键值对，而上图的每一个黑色点便是一个Node对象。

存储过程概述

当有元素进来，会进行判断是否存在，如果不存在，则直接将元素放入对应的数组中去。但当已经有数据时，就有了Hash碰撞。常见的解决方法有几种：开放地址，再哈希，链地址等等。解决Hash碰撞冲突方法总结

HashMap采用了链地址法，在每个元素上都追加了一个链表结构，以此来存储相同哈希值的元素。所以在早先版本如果没有红黑树的转换，极端情况当所有数据的哈希值都一样的情况下，HashMap会退化为单链表，查找速度也从O(1)退化为0（N）。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

同时对于JDK 1.8中当一个链表元素超过8个的时候还会进行红黑树转化即treeify过程来增强性能。

1
2
3
4

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;  

HashMap默认开辟的存储空间为16，theshold = length * loadFactor 当存储到12后开始进行扩容，大小就是之前的两倍。扩容过程意味着需要时间，开辟新的空间并拷贝过去。所以意味着我们尽量避免扩容的发生，又不想浪费太多空间。0.75是默认的负载因子，通常可以比较好的平衡空间与性能，除非特殊需求。

具体过程分析与区别或许还是需要阅读源码才可以，这部分看了一些但还需要再总结归纳一下有时间写到下篇中分析。

（未完待续…）

参考链接

• Java 8系列之重新认识HashMap

更新日志：