💁 个人主页：黄小黄的博客主页
❤️ 支持我：👍 点赞 🌷 收藏 🤘关注
🎏 格言：All miracles start from sometime somewhere, make it right now.
本文来自专栏：JavaSE从入门到精通
文章目录
1 Map接口
1.1 Map接口简介及说明
相较于前面所学的Set接口，Map接口的元素也是由k-v键值对组成的，只不过在Set接口中，value使用的是present常量进行占位。
Map接口常见的实现类如下图所示：
🐰 Map接口的说明：
- Map与Collection并列存在。用于保存具有映射关系的数据：key-value；
- Map中的key与value可以是任何引用数据类型，会封装到HashMap$Node对象中；
- Map中的key不重复，原理与之前分析的Set源码相同，不再赘述；
- Map中的value可以重复；
- Map中的key、value都可以为null，但是key只能有一个为null；
- 常用String作为Map的key；
- key与value存在着单向一对一关系，可以通过key找到对应的value。
需要特别注意的是，在Map中如果key相同，则会将相应的value进行更新， 具体案例如下：
import java.util.HashMap;
import java.util.Map;
public class MapTest01 {
public static void main(String[] args) {
Map map = new HashMap();
map.put("nezuko", "祢豆子");
map.put("temp1", "祢豆子");
map.put("temp2", "祢豆子");
map.put("nezuko", "黄小黄");
System.out.println(map);
}
}
当我们对上述代码进行debug，追进源码，可以得到如下 重要结论：
- k-v 最后的存在形式为 HashMap$Node node = newNode(hash，key，value，null)；
- k-v 为了方便程序员的遍历，还会创建一个 EntrySet 集合，该集合存放的元素类型为 Entry，即 transient Set<Map.Entry<K，V>> entrySet;
- 虽然在 entrySet 中，定义的类型是 Map.Entry，但是实际上存放的是 HashMap $ Node ，因为，HashMap$Node implement Map.Entry。
1.2 Map接口的常用方法
| 方法名 | 作用 |
|---|---|
| put(K，V) | 添加键值对 |
| remove() | 根据键值删除映射关系 |
| get() | 根据键值获取值 |
| size() | 获取元素个数 |
| isEmpty() | 判断个数是否为0 |
| clear() | 清除k-v |
| containsKey() | 查找键是否存在 |
| keySet() | 获取所有的键 |
| entrySet() | 获取所有的关系k-v |
| values() | 获取所有的值 |
1.3 Map的常用遍历方式
存储案例代码如下：
import java.util.HashMap;
import java.util.Map;
public class MapTest01 {
public static void main(String[] args) {
Map map = new HashMap();
map.put("红色", "red");
map.put("绿色", "green");
map.put("黑色", "black");
map.put(null, "未知");
map.put("未知", null);
}
}
1️⃣ 先取出所有的 key，然后通过 key 取值：
Set keySet = map.keySet();
// (1)for
for (Object key :
keySet) {
System.out.println(key + "-" + map.get(key));
}
// (2)迭代器
Iterator iterator = keySet.iterator();
while (iterator.hasNext()){
Object key = iterator.next();
System.out.println(key + "-" + map.get(key));
}
2️⃣ 直接取出所有的 values：
Collection values = map.values();
// (1)for
for (Object value :
values) {
System.out.println(value);
}
// (2)迭代器
Iterator iterator = values.iterator();
while (iterator.hasNext()){
Object value = iterator.next();
System.out.println(value);
}
3️⃣ 通过EntrySet 来获取 k-v：
Set entrySet = map.entrySet();
// (1)for
for (Object entry:
entrySet) {
// 将 entry 转成 Map.Entry
Map.Entry m = (Map.Entry)entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
// (2)迭代器
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()){
Object next = iterator.next();
Map.Entry m = (Map.Entry)next;
System.out.println(m.getKey() + "-" + m.getValue());
}
2 HashMap
2.1 HashMap简介
🐰说明：
- 如果添加相同的key，则会覆盖原来的k-v，等同于修改；
- 与HashSet一样，不保证映射的顺序，底层的由hash表的方式存储；
- HashMap没有实现同步，线程不安全;
- jdk7.0的hashmap底层（数组＋链表），jdk8.0底层（数组＋链表+红黑树）。
2.2 HashMap底层机制与源码解读
🦁 hashmap结构示意图：
🐰 扩容机制：
- HashMap底层维护了Node类型的数组table，默认为null；
- 当创建的对象的时候，加载因子（loadfactor）初始化为0.75；
- 当添加key-val时，通过key的哈希值得到在table的索引，然后判断该索引处是否有元素。如果没有元素则直接添加，如果有元素，则继续判断该元素的key是否与准备添加的key相等。如果相等，则将val进行替换；如果不相等，需要判断该位置是树结构还是链表结构，进行相应的添加元素处理。如果添加时发现容量不够，则需要进行扩容；
- 第1次添加，table初始容量扩容为16，临界值（threshold）为12；
- 以后需要扩容的时候，每次将table扩容为原来大小的2倍，临界值为原来的2倍，即24，以此类推；
- 在Java8 中，如果一条链表的元素个数超过 TREEIFY_THRESHOLD(默认是8)，并且table的大小>= MIN_TREEIFY_CAPACITY(默认64)，就会进行树化（红黑树）;
- 若已经树化，当树的结点 < 8，则会通过剪枝重新变回链表。
🐴 源码解读：
下面我们通过debug该段代码，追进jdk源码，来进行源码解读：
import java.util.HashMap;
/**
* @author 兴趣使然黄小黄
* @version 1.0
*/
public class HashMapTest {
public static void main(String[] args) {
HashMap hashMap = new HashMap();
hashMap.put("java", 10);
hashMap.put("python", 10);
hashMap.put("java", 20);
}
}
1️⃣ 执行构造器 new HashMap() ，初始化了加载因子loadFactor = 0.75，并且table表 HashMap $ Node[] table = null；
2️⃣执行第一个put方法，在put方法内部会调用 hash 方法，计算key的hash值，在HashSet源码解读中已经阐述，这里不再赘述：
3️⃣重要的一步， 执行 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 数组为 null，或者 length = 0，就扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取出hash值对应的table的索引位置的Node
//如果为null，就直接把加入的k-v创建成一个Node，加入该位置
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
4️⃣ 执行第二个put时，重复了上述步骤，索引可能位置不同，最终结果是创建了一个新的结点，加入到了HashMap中；
5️⃣ 关键来啦！ 执行第三个put时，由于key值相同，因此通过hash算法求得的hash值相同，所在hash表的索引位置也相同，因此，就会进入源码的else代码块 （与该索引位置上的所有结点逐个比较，如果key相同，则替换val，否则，直接添加）， 具体看源码注释：
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 数组为 null，或者 length = 0，就扩容到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//取出hash值对应的table的索引位置的Node
//如果为null，就直接把加入的k-v创建成一个Node，加入该位置
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 && //如果table的索引位置的key的hash值与新的key索引位置的hash值相同
//并且满足现有的key与添加的key是同一对象 或者 equals返回真
//就认为不能加入
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) //如果当前table已有的Node已经是红黑树，则按照树的逻辑操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//如果找到的结点后面是链表，则逐个结点比较
for (int binCount = 0; ; ++binCount) { //死循环
if ((e = p.next) == null) { //如果整个链表没有与它相同的key，就加在该链表的最后
p.next = newNode(hash, key, value, null);
//加入后判断是否到达8个，如果到达，则进行树化
//调用 treeifyBin 方法进行红黑树的转化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && //如果发现有相同的，就不添加，break，简单替换val
((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; //替换，key
afterNodeAccess(e);
return oldValue;
}
}
++modCount; //每增加一个Node，就size++
if (++size > threshold) //size大于临界值，就进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
6️⃣ 树化的要求， table表为空，或者大小未到达64，就暂时不树化，先进行扩容：
3 HashTable
3.1 HashTable简介
🐰说明：
- 存放的元素依然是键值对 k-v；
- hashtable的键和值都不能为null；
- HashTable是线程安全的；
- HashTable使用的方法基本上和HashMap一样。
3.2 HashTable扩容机制与源码解读
🐰 底层机制解读：
- 底层有数组 HashTable $ Entry[] 初始化大小为11；
- 临界值threshold = 8 = 11 * 0.75；
- 扩容：按照HashTable扩容机制进行扩容，首次扩容情况为 count > 8。
🦁 扩容源码解读：
对下面代码进行debug，断点打在第9个put前：
import java.util.Hashtable;
/**
* @author 兴趣使然黄小黄
* @version 1.0
*/
public class HashTableTest {
public static void main(String[] args) {
Hashtable hashtable = new Hashtable();
hashtable.put("java1", 100);
hashtable.put("java2", 100);
hashtable.put("java3", 100);
hashtable.put("java4", 100);
hashtable.put("java5", 100);
hashtable.put("java6", 100);
hashtable.put("java7", 100);
hashtable.put("java8", 100);
hashtable.put("java9", 100);
}
}
1️⃣ 在debug开始时，HashTable容量已经为11，此时，table里有8个元素：
2️⃣先进行装箱，然后判断put的值是否为null，如果为null就抛出异常：
3️⃣ 对于中间求hash值的步骤我们暂时不关心，追进addEntry方法，该法方法用于添加 k-v 封装到 Entry。在该方法中，当count大于等于临界值时，就会调用rehash方法进行扩容。
4️⃣ 追进rehash方法，发现，扩容后的容量 newCapacity = (oldCapacity << 1) + 1，相当于原来的容量✖ 2 + 1，相关源码如下：
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
4 小结
- HashTable 与 HashMap 简单对比：
| 版本 | 线程安全 | 效率 | 允许null键null值 | |
|---|---|---|---|---|
| HashMap | 1.2 | 不安全 | 高 | 允许 |
| HashTable | 1.0 | 安全 | 较低 | 不允许 |
写在最后
🌟以上便是本文的全部内容啦，后续内容将会持续免费更新，如果文章对你有所帮助，麻烦动动小手点个赞 + 关注，非常感谢 ❤️ ❤️ ❤️ !
如果有问题，欢迎私信或者评论区！
共勉：“你间歇性的努力和蒙混过日子，都是对之前努力的清零。”
