听说微信搜索《Java鱼仔》会变更强哦！
（一）Map方法概述
首先先看一下官方对Map接口的解释，《Java Platform SE 8》:
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
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 = 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的介绍
A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
根据官方文档的介绍，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就算没有看过代码但是也要了解各自的特点。
原创文章，作者：3628473679，如若转载，请注明出处：https://blog.ytso.com/163124.html