HashMapHashTableTreeMap的底层源码分析和对比 _Hashtable

幽沉谢世事，俯默窥唐虞。这篇文章主要讲述HashMapHashTableTreeMap的底层源码分析和对比相关的知识，希望能为你提供帮助。
（一）Map方法概述首先先看一下官方对Map接口的解释，《java Platform SE 8》:
Map是一个通过键值对保存的对象，一个map只能由一个key，但是一个key可以有多个value。
Map的使用很简单：
1.1 Map的几个常用方法通过代码展示一下Map中常用的方法：

public class MapTest { public static void main(String[] args) { Map map=new HashMap(); //添加 put(key,value) map.put("a1",1); map.put("a2",1); map.put(null,1); System.out.println(map); //删除 remove(key) map.remove("a2"); System.out.println(map); //是否包含 key value //containsKey(key)containsValue(value) System.out.println(map.containsKey("a1")); System.out.println(map.containsValue("1")); //获取数据 get(key) System.out.println(map.get("a1")); //获取大小 size() System.out.println(map.size()); //是否为空 isEmpty() System.out.println(map.isEmpty()); //获取所有的关系 entrySet() System.out.println(map.entrySet()); //获取所有的key keySet() System.out.println(map.keySet()); //获取所有的value values() System.out.println(map.values()); } }

（二）HashMap的特点HashMap底层是一个哈希表，以数组加链表的形式存储值。HashMap具有以下特点：
1.HashMap允许key和value为空
2.HashMap是线程不安全的
3.HashMap的初始容量为16，负载因子大小为0.75
4.在jdk7.0中，底层是数组加链表；在jdk8.0中，底层是数组加链表加红黑树（这一点在后面会重点讲一下）
（三）HashMap的源码分析通过代码断点的方法逐个添加元素，单步观察代码执行步骤，首先进入HashMap的构造方法：

public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

该构造方法把负载因子设置为0.75，负载因子的意思是当存入的数据大于总容量的0.75倍时，就扩容。构造方法结束后进入put方法

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

put方法直接返回putVal()方法，putVal方法的第一个参数是根据key计算的一个哈希值，可以看一下这个hash方法：通过hash运算和异或操作得到hash值并返回

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

接下来就进入了比较重要的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; //查看此时table的容量（即哈希表数组部分的长度），如果为空（第一次进入），则进入resize()方法 //resize()是个初始化或扩容方法，初始化成16或扩容2倍 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //根据此时数组的长度n和计算的hash值算出索引 //计算出的索引一定在0~n-1之间 //如果该索引位置没有元素，则直接将元素添加进入 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 1st treeifyBin(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 key V oldValue = https://www.songbingjia.com/android/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //判断容量是否超过临界值，如果超过了就2倍扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

源码分析：
HashMap中维护了Node类型的数组table，当HashMap创建对象时，设置负载因子为0.75，table还是null。
当第一次添加元素时，将table的容量设置为16，临界值设置为12
每次添加元素调用putVal方法：
1.将key的hash值和table容量-1进行与运算，得到索引值
2.判断该存放位置上是否有元素，如若没有元素则直接放上去；如果该索引位置已存在元素，则继续判断
3.如果该位置的元素和添加元素相等，则直接覆盖，如果不相等，则继续判断是链表结构还是树状结构，按照相对应的方式添加。
如果添加的数量大于临界值，执行resize方法对容量双倍扩容。并打乱顺序重新排列。
（四）HashMap在JDK1.7和JDK1.8中的区别前面一直提到树状结构和红黑树，这是HashMap在JDK1.7和JDK1.8之间最大的区别。数组+链表的结构下，如果一个索引后跟着的链表数量很多时，会很影响查找效率，因此在JDK1.8中，HashMap当满足某种条件（链表长度大于8，table容量大于64）时，会将链表转化为红黑树结构，提高效率。
截取一段源码：当链表长度大于等于（TREEIFY_THRESHOLD - 1）时，这个值是7，进入treeifyBin方法。链表长度大于等于7，再加上数组上的一个元素，一共是8个元素。

if (binCount > = TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash);

进入treeifyBin方法：

final void treeifyBin(Node< K,V> [] tab, int hash) { int n, index; Node< K,V> e; //如果进入treeifyBin但是table的容量小于64，则执行resize扩容并重新打乱 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //链表长度大于8，table容量大于64，转化成红黑树 else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode< K,V> hd = null, tl = null; do { TreeNode< K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

如果进入treeifyBin但是table的容量小于64，则执行resize扩容并重新打乱。所以并非容量大于临界容量才会扩容。
第二个差异是插入元素时的变化，JDK1.7中是用头插法的方式插入元素，在JDK1.8中这个插入方式变成了尾插法。这个变化的原因是用头插法插入元素存在链表循环的风险。当两个线程同时put元素并且刚好触发扩容，就会造成链表死循环。
JDK1.7和JDK1.8区别总结：
1.初始化对象时，JDK1.7直接初始化对象容量为16，JDK1.8仅仅初始化负载因子为0.75
2.table类型：JDK1.7是Entry（映射key和value），JDK1.8是Node类型（为了红黑树）
3.底层结构：JDK1.7数组+链表，JDK1.8数组+链表+红黑树（链表长度大于8，table容量大于64）
4.元素插入方式：JDK1.7 头插法，JDK1.8尾插法

（四）HashMap和HashTable的对比HashMap和HashTable的处境有点像Vector和ArrayList，HashTable现在很少使用，就用一个表格来总结它和HashMap的区别

底层结构	版本	线程安全（同步）	允许null
HashMap	哈希表	1.2	不安全	允许键值为null
HashTable	哈希表	1.0	安全	不允许键值null

（五）TreeMap的介绍根据官方文档的介绍，TreeMap底层是一个红黑树，map是根据keys进行自然排序或者定制排序。
自然排序和定制排序的用法和TreeSet类似。
使用自然排序：需要在类中继承Comparable接口，并重写compareTo方法。

public class Book implements Comparable{ private String name; private float price; public Book(String name, float price){ this.name=name; this.price=price; } //......... @Override public int compareTo(Object o) { Book book= (Book) o; return Double.compare(book.price,this.price); } }

使用定制排序：需要在创建TreeMap对象时传入一个Comparator接口，并实现里面的compare方法。

TreeMap map=new TreeMap(new Comparator() { @Override public int compare(Object o1, Object o2) { Book book1= (Book) o1; Book book2= (Book) o2; return Double.compare(book1.getPrice(),book2.getPrice()); } });

（六）总结HashMap绝对是Map中的重点，也是据我所知面试中问到最多的集合知识。因此有条件的话打开源码自己单步调试一遍。HashTable、TreeMap就算没有看过代码但是也要了解各自的特点。
【HashMapHashTableTreeMap的底层源码分析和对比】