共计 4527 个字符，预计需要花费 12 分钟才能阅读完成。
系列文章:
「深入浅出」java 集合 Collection 和 Map
「深入浅出」集合 List
「深入浅出」集合 Set
前面已经介绍完了 Collection 接口下的集合实现类，今天我们来介绍 Map 接口下的几个重要的集合实现类 HashMap,Hashtable,LinkedHashMap,TreeMap。
HashMap
(最常用, 随机访问速度快, 无序, 可存一个 Null key, 多个 Null value, 非同步)
HashMap 是最常用的 Map，它根据键的 HashCode 值存储数据，根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。因为键对象不可以重复，所以 HashMap 最多只允许一条记录的键为 Null，允许多条记录的值为 Null，是非同步的
Hashtable
(HashMap 线程安全版, 效率低,key 和 value 都不能为 null, 同步)
Hashtable 与 HashMap 类似，是 HashMap 的线程安全版，它支持线程同步，即任一时刻只有一个线程能写 Hashtable，因此也导致了 Hashtale 在写入时会比较慢，它继承自 Dictionary 类，不同的是它不允许记录的键或者值为 null，同时效率较低。
LinkedHashMap
(有序, 遍历性能好, 可存一个 Null key, 多个 Null 值, 非同步)
LinkedHashMap 是由散列表 + 循环双向链表实现的。LinkedHashMap 需要维护元素的插入顺序，因此性能略低于 HashMap 的性能；但是因为它以链表来维护内部顺序，所以在迭代访问 Map 里的全部元素时有较好的性能。迭代输出 LinkedHashMap 的元素时，将会按照添加 key-value 对的顺序输出, 有 HashMap 的全部特性。
TreeMap
(有序, 可自定义排序,key 不能为空, 非同步)
TreeMap 是一个有序的 key-value 集合，它是通过红黑树实现的，每个 key-value 对即作为红黑树的一个节点。能够把它保存的记录根据键排序，默认是按键值的升序排序（自然顺序），也可以指定排序的比较器，不允许 key 值为空，非同步的。
HashMap 的实现
下面具体说说 hashMap 的实现原理(基于 jdk1.7)
HashMap 的构造函数
// 初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认构造函数。
HashMap()
// 指定“容量大小”的构造函数
HashMap(int capacity)
// 指定“容量大小”和“加载因子”的构造函数
HashMap(int capacity, float loadFactor)
// 包含“子 Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)
HashMap 有以上 4 种构造方法, 其中 HashMap(int capacity)和 HashMap(int capacity, float loadFactor)可以指定容量或加载因子。
容量即是 HashMap 所能存储的 ” 最大 ” 容量 (注意: 最大加了双引号, 因为 hashMap 会做扩容) 加载因子是 HashMap 在其容量做扩容前可以达到多满的程度。当容量超出了加载因子与当前容量的乘积时，hashMap 会进行扩容达到原来的 2 倍容量。
当使用默认构造函数 HashMap()构建时，会使用默认的容量 DEFAULT_INITIAL_CAPACITY = 1 << 4(即是 16)和默认加载因子 DEFAULT_LOAD_FACTOR = 0.75f
注意: 使用 HashMap 时, 尽量指定它的初始容量, 因为扩容是按 1 倍扩展的, 如果频繁的扩容会导致性能下降, 内存的消耗。
底层存储 Node
HashMap 是通过 ” 拉链法 ” 实现的哈希表。其底层存储结构是 Node 数组,Node 实际上就是一个单向链表, 哈希表的 ”key-value 键值对 ” 都是存储在 Node 中的。
Node 是 HashMap 的内部类, 如下
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
// 指向下一个节点
Node<K,V> next;
// 构造函数。
// 输入参数包括 ” 哈希值(hash)”, “ 键(key)”, “ 值(value)”, “ 下一节点(next)”
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key;}
public final V getValue() { return value;}
public final String toString() { return key + “=” + value;}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判断两个 Node 是否相等
// 若两个 Node 的“key”和“value”都相等，则返回 true。
// 否则，返回 false
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
Java 中数据存储方式最底层的两种结构: 数组和链表。
数组的特点：连续空间，寻址迅速，但是在刪除或者添加元素的时候需要有较大幅度的移动，所以查询速度快，增刪较慢。而链表正好相反，由于空间不连续，寻址困难，增刪元素只需修改指針，所以查询速度慢、增刪快。
有沒有一种数组结构來综合一下数组和链表，以便发挥它们各自的优势？答案是肯定的！就是：哈希表（HashMap）。
哈希表具有较快（常量级）的查询速度，及相对较快的增刪速度，所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”，我們可以理解为“链表的数组”，如下图：
从图中，我们可清楚地看出哈希表是由数组 + 链表组成的，一个长度为 16 的数组中，每個元素存储的是一个链表的头结点。通过 hash(key)方法判断出元素的存储位置，如果 hash(key)值相等，则都存入该 hash 值所对应的链表中。
这个 hash(key)方法是 HashMap 的一个方法, 与 Object 类的 hashCode()是有所区别的,hash(key)在 hashCode()方法的基础做一些修改。
HashMap 遍历
有 3 种遍历方式,map.keySet()、map.values()、Map.Entry, 例子代码如下
public class Demo2 {
public static void main(String[] args) {
Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, “aaaa”);
map.put(2, “bbbb”);
map.put(3, “cccc”);
System.out.println(map);
// 第一种方式: 使用 keySet
// 需要分别获取 key 和 value，没有面向对象的思想
// Set<K> keySet() 返回所有的 key 对象的 Set 集合
Set<Integer> ks = map.keySet();
Iterator<Integer> it = ks.iterator();
while (it.hasNext()) {
Integer key = it.next();
String value = map.get(key);
System.out.println(“key=” + key + ” value=” + value);
}
// 第二种方式：map.values()
// 通过 values 获取所有值, 不能获取到 key 对象
// Collection<V> values()
Collection<String> vs = map.values();
Iterator<String> it = vs.iterator();
while (it.hasNext()) {
String value = it.next();
System.out.println(” value=” + value);
}
// 第三种方式：Map.Entry 对象 推荐使用 重点
// Set<Map.Entry<K,V>> entrySet()
// 返回的 Map.Entry 对象的 Set 集合 Map.Entry 包含了 key 和 value 对象
Set<Map.Entry<Integer, String>> es = map.entrySet();
Iterator<Map.Entry<Integer, String>> it = es.iterator();
while (it.hasNext()) {
// 返回的是封装了 key 和 value 对象的 Map.Entry 对象
Map.Entry<Integer, String> en = it.next();
// 获取 Map.Entry 对象中封装的 key 和 value 对象
Integer key = en.getKey();
String value = en.getValue();
System.out.println(“key=” + key + ” value=” + value);
}
}
}
性能分析及适用场景
HashMap 与 Hashtable 实现机制几乎一样，但是 HashMap 比 Hashtable 性能更好些。
LinkedHashMap 比 HashMap 慢一点，因为它需要维护一个双向链表。
TreeMap 比 HashMap 与 Hashtable 慢（尤其在插入、删除 key-value 时更慢），因为 TreeMap 底层采用红黑树来管理键值对。
适用场景：
一般的应用场景，尽可能多考虑使用 HashMap，因为其为快速查询设计的。
如需特定的排序时，考虑使用 TreeMap。
如仅仅需要插入的顺序时，考虑使用 LinkedHashMap。
集合篇系列上讲完了,Queue 就不讲了, 实在是很少用到, 请自行学习哈~
推荐阅读: 小黄官宣: 排队有序退款「第七期福利活动」15 本书籍，无套路直接送！java 小心机(6)| 多态的一些坑
阅读原文, 查看更多精彩内容 …
您的点赞、转发是对我最大的支持！
THANDKS
End –
一个立志成大腿而每天努力奋斗的年轻人
伴学习伴成长，成长之路你并不孤单!
