前言

HashMap类可以说是集合类中最重要的一个，也是我们开发中经常用到的一个类。它底层实现涉及到一些比较有代表性的数据结构和算法。它本身也是在面试的时候被经常问到的。下面让我们来详细的学习一下吧！

HashMap介绍

其实在讲集合之前，我们都应该先了解一下什么是泛型？因为在使用集合的时候，常常和泛型结合使用的。

泛型

泛型其实是在JDK1.5以后增加的， 本质就是“数据类型的参数化”。通俗理解就是数据类型的一个占位符(形式参数)，其目的就是为了告诉编译器，在调用泛型时必须传入实际类型。当然JDK也提供了支持泛型的编译器，就是将运行时的类型检查提前到了编译时执行，提高了代码可读性和安全性。其实使用泛型为程序员解决了很多麻烦，因为泛型的作用还是比较明显的。它可以校验代码、在使用了泛型的集合中，遍历时就不必进行强制类型转换、还有一点就是代码的扩展性更强了。

泛型的使用其实非常简单。比如，直接在类上加，其中的T，就像一个占位符一样表示“未知的某个数据类型”，我们在真正调用的时候传入这个“数据类型”。我们常把T，K，E，V这三个当作泛型占位符来使用。比如Map接口的定义源码：

public interface Map<K,V> {

当然我们在使用泛型的时候也需要注意一些地方，比如说它只能使用引用类型，当它存在在有继承关系的类之间是不能直接隐式向上造型的。

了解完泛型后，再来学习集合吧！HashMap其实是Map接口的一个实现，所以我们先来介绍一下map接口！

Map接口

Map就是用来存储“键(key)-值(value) 对”的。 Map类中存储的“键值对”通过键来标识，所以“键对象”是不能重复的。那么我们判断的依据是什么呢？就是通过 equals方法来判断的，如果出现重复的，它也不会报错，只是会覆盖之前的对象。Map接口下定义了一些常用的方法，如下：

Map 接口的实现类非常多，常用的有这些：HashMap、TreeMap、HashTable、Properties等。

下面就来详细的学习一下HashMap。

HashMap

HashMap是采用哈希算法实现，是Map接口中最常用的实现类。

public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {

由于底层采用了哈希表（这里简单解释一下什么是哈希表？就是数组+单向链表）存储数据，我们要求键不能重复，如果发生重复，新的键值对会替换旧的键值对。 同时HashMap在查找、删除、修改方面都有非常高的效率。这里先给出结论，当你看了它的底层是怎么实现，你也就清楚了。

HashMap底层实现

在学习HashMap底层之前，在这里先抛出一些问题，这些问题会在下面一一接答的。

1. 默认初始容量16和加载因子0.75有什么作用？
2. 数组有什么作用，什么时候创建数组？
3. 链表有什么作用？什么时候形成链表？
4. 红黑树有什么作用？什么时候形成红黑树？
5. put方法的返回值为什么是被覆盖的值？
6. 怎么去确定每一个entry在数组中存放的位置？
7. 为什么key可以为null？

上面已经说HashMap底层是由哈希表实现的。并且哈希表在jdk1.7的时候是基于数组+链表 ，在jdk1.8的时候基于数组+链表+红黑树。其实在HashMap中，是用Node类来存放键值对的，它是HashMap中的一个静态内部类。部分源码如下：

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}

其中key就是键对象，value就是值对象，next是指向下一个节点（这里我们就可以看出这是一个单向链表），hash就是键对象计算出来的hash值。给大家提供一个比较形象的图，方便理解。

前面我们说了哈希表是数组+单向链表或者再加红黑树，这里的数组其实有个比较专业的名称，叫做位桶数组。源码如下：

  transient Node<K,V>[] table;

可以看到它就是用来存放我们的Node对象的。那么它是怎样存放的呢？当然是通过put方法来实现的，所以我们就来重点看看put方法里究竟做了些什么？这里带领大家看看源码，千万不要被源码吓住，不一定是要每句都能看懂，但要知道它大概做了哪些事情。put方法源码：

   public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}

看到put方法源码，是不是很简单啊！并不是多么难以看懂。这里put方法其实没有做很多事情，就是计算了一下key的hash值和调用了putVal方法。来看看key的hash是怎么计算的。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

这里其实就是一个三目运算，当key为null的时候，就直接返回0，不会null，就进行高位的与运算。看到这里，上面提出的第7个问题是不是解决了。

下面让我们继续跟踪putVal方法。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

不要看到这么多的代码就吓住，其实一行一行的看，它是很简单的。

首先声明了几个变量；

然后判断了当前数组是否存在，通过这句代码：if ((tab = table) == null || (n = tab.length) == 0)；如果不存在，调用resize方法创建数组；

接着根据int值和数组的最大索引值，计算当前entry在数组中存放的位置，并且判断该位置是否已经存在entry ，if ((p = tab[i = (n - 1) & hash]) == null)，如果不存在，则直接创建一个新的node放在该位置，在这里就解决了上面的第6个问题；

如果存在，就判断key是否完全相同，通过equals方法，if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))，如果相同，则将该位置的node赋值给一个临时的变量e， 方便最后返回被覆盖的值，看到这上面的第5个问题解决了；

如果key不相同，则判断是红黑树还是链表（else if (p instanceof TreeNode)），如果是红黑树，则以红黑树的方式存储值，如果是链表，则以链表的方式存储值；

然后判断链表长度是否超过8（if (binCount >= TREEIFY_THRESHOLD - 1)），如果超过就转换为红黑树；

如果有被覆盖的值（if (e != null)），最后返回被覆盖的值；

最后判断数组的使用长度是否已经超过加载因子所约定的长度（if (++size > threshold)），调用resize方法进行数组扩容 ，扩容为原来的两倍。

以上就是put方法所完成的事情，看过之后上面提出的问题也就迎刃而解了。这里再介绍哈几个HashMap里定义的常量吧。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16static final float DEFAULT_LOAD_FACTOR = 0.75f;static final int TREEIFY_THRESHOLD = 8;static final int UNTREEIFY_THRESHOLD = 6;

其中DEFAULT_INITIAL_CAPACITY就表示数组的初始长度；DEFAULT_LOAD_FACTOR就是加载因子，用来判断数组是否需要扩容；TREEIFY_THRESHOLD就表示链表的长度，如果大于8，就转换为红黑树；UNTREEIFY_THRESHOLD也是表示链表的长度，如果小于6，就转换为单向链表。为什么要转换呢？因为我们都知道链表查询就是从头遍历到尾，如果你单向链表太长的话，查询效率就会受到影响，此时再转换为红黑树，查询效率就会好很多，同样链表的长度如果小于6的话，链表查询效率就会更好一些。

当你知道hashmap是怎么存值后，再去看取值get方法，就会跟简单了。

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;}

这里同样也是一个三目运算，重点就是根据key计算int值后，调用了getNode方法。

    final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

getNode方法还是先声明了几个变量；

然后判断数组是存在，如果不存在，就直接返回null；

如果存在，就判断该位置的第一个元素是否为要找的元素 ，通过equals方法；

如果是，就直接返回；如果不是，就用红黑树或者链表的方式取值并返回。

区别

下面来总结一下map接口下常用实现类之间的区别：

• HashMap: 线程不安全，但是效率较高。多数情况使用它，可以存在一个key为null，多个value为null 。

• Hashtable: 线程安全，使用sychonized同步方法，效率低，key和value都不能为null。

• HashMap和Hashtable继承类不同，实现接口相同。

  public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {
  

• ConcurrentHashMap：线程安全，同步的代码块，粒度比Hashtable更小 ，不能够以null作为key或者value 效率相对比Hashtable较高，它是通过把整个Map分为N个Segment（类似HashTable），都是提供一样的线程安全，但是这样它的效率就会提升N倍，默认提升的是16倍。

• Properties 是HashTable 的子类，主要用于读取配置文件，只能存String，通过List 方法 Load方法进行读取和写入。