💁 个人主页:黄小黄的博客主页
❤️ 支持我:👍 点赞 🌷 收藏 🤘关注
🎏 格言:All miracles start from sometime somewhere, make it right now.
本文来自专栏:JavaSE从入门到精通
相较于前面所学的Set接口,Map接口的元素也是由k-v键值对组成的,只不过在Set接口中,value使用的是present常量进行占位。
Map接口常见的实现类如下图所示:
🐰 Map接口的说明:
需要特别注意的是,在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,追进源码,可以得到如下 重要结论:
方法名 | 作用 |
---|---|
put(K,V) | 添加键值对 |
remove() | 根据键值删除映射关系 |
get() | 根据键值获取值 |
size() | 获取元素个数 |
isEmpty() | 判断个数是否为0 |
clear() | 清除k-v |
containsKey() | 查找键是否存在 |
keySet() | 获取所有的键 |
entrySet() | 获取所有的关系k-v |
values() | 获取所有的值 |
存储案例代码如下:
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());
}
🐰说明:
🦁 hashmap结构示意图:
🐰 扩容机制:
🐴 源码解读:
下面我们通过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,就暂时不树化,先进行扩容:
🐰说明:
🐰 底层机制解读:
🦁 扩容源码解读:
对下面代码进行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;
}
}
}
版本 | 线程安全 | 效率 | 允许null键null值 | |
---|---|---|---|---|
HashMap | 1.2 | 不安全 | 高 | 允许 |
HashTable | 1.0 | 安全 | 较低 | 不允许 |
🌟以上便是本文的全部内容啦,后续内容将会持续免费更新,如果文章对你有所帮助,麻烦动动小手点个赞 + 关注,非常感谢 ❤️ ❤️ ❤️ !
如果有问题,欢迎私信或者评论区!
共勉:“你间歇性的努力和蒙混过日子,都是对之前努力的清零。”