哈喽,各位小伙伴们,你们好呀,我是喵手。运营社区:C站/掘金/腾讯云;欢迎大家常来逛逛
今天我要给大家分享一些自己日常学习到的一些知识点,并以文字的形式跟大家一起交流,互相学习,一个人虽可以走的更快,但一群人可以走的更远。
我是一名后端开发爱好者,工作日常接触到最多的就是Java语言啦,所以我都尽量抽业余时间把自己所学到所会的,通过文章的形式进行输出,希望以这种方式帮助到更多的初学者或者想入门的小伙伴们,同时也能对自己的技术进行沉淀,加以复盘,查缺补漏。
小伙伴们在批阅的过程中,如果觉得文章不错,欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持!
前言
在Java中,HashMap
是一种重要的数据结构,也是我们经常使用的一种存储数据的容器。但是,你是否了解HashMap的具体实现?在使用HashMap时,你是否遇到过问题或者疑惑?在本文中,我们将通过源代码解析、应用场景案例、优缺点分析等方面,深入了解HashMap
这个精妙的数据结构。
摘要
本文将从以下几个方面对Java中的HashMap
进行分析:
- 源代码解析:对
HashMap
的源代码进行解析,了解HashMap的具体实现; - 应用场景案例:通过具体场景案例,让读者了解在实际开发中如何灵活运用HashMap;
- 优缺点分析:对
HashMap
的优缺点进行分析,帮助读者更好地掌握HashMap
的适用范围; - 类代码方法介绍:对
HashMap
中各个方法的使用方法和注意事项进行详细介绍; - 测试用例:提供相关测试用例,帮助读者更好地理解
HashMap
的应用。
HashMap
简介
HashMap是一种常见的键值对存储容器,其内部采用散列表实现,可以快速地查找键对应的值。具体来说,HashMap内部维护了一个Entry数组,每个Entry包含了一个键值对。HashMap使用哈希算法将键值对映射到数组中的位置,从而实现快速查找。
在Java中,HashMap继承自AbstractMap
类,实现了Map接口,提供了一系列的方法用于操作键值对。
源代码解析
为了更好地理解HashMap
的实现,我们将对其源代码进行解析。
数据结构
HashMap内部维护了一个Entry数组,每个Entry包含了一个键值对,定义如下:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
// ...
}
其中,key表示键,value表示值,next表示下一个节点,hash表示键的哈希值。
插入操作
HashMap中插入一个键值对的操作可以通过以下代码实现:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
其中,inflateTable用于初始化Entry数组,如果Entry数组未被初始化,则调用inflateTable方法进行初始化。putForNullKey用于处理键为null的情况。hash方法用于计算键的哈希值。indexFor方法用于将哈希值映射到Entry数组的位置。for循环用于查找键是否已经存在于Entry数组中。如果键已经存在,则更新值;否则,添加新的Entry。
查找操作
HashMap中查找某个键的值的操作可以通过以下代码实现:
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
其中,get方法用于获取指定键的值,如果键不存在,则返回null。getEntry方法用于查找对应的Entry。
删除操作
HashMap中删除某个键值对的操作可以通过以下代码实现:
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
其中,remove方法用于删除指定键值对,先调用removeEntryForKey方法查找对应的Entry。如果找到对应的Entry,则将其删除;否则,不做任何操作。
应用场景案例
HashMap可以用于存储键值对,适用于如下场景:
- 对象属性存储和查找;
- 缓存实现;
- 计数器实现。
下面以缓存实现为例,介绍HashMap的应用:
public class Cache {
private Map<String, Object> cache = new HashMap<>();
public void put(String key, Object value) {
cache.put(key, value);
}
public Object get(String key) {
return cache.get(key);
}
public void remove(String key) {
cache.remove(key);
}
public void clear() {
cache.clear();
}
public int size() {
return cache.size();
}
public boolean containsKey(String key) {
return cache.containsKey(key);
}
public boolean containsValue(Object value) {
return cache.containsValue(value);
}
}
在上述代码中,我们利用了HashMap实现了一个简单的缓存,用户可以通过put、get、remove、clear等方法来操作缓存中的对象,方便地实现了对象缓存的功能。
优缺点分析
优点
- 快速查找:由于HashMap采用哈希算法实现,可以快速地查找指定键对应的值;
- 高效存储:HashMap内部采用数组实现,可以高效地存储大量键值对;
- 线程不安全:HashMap在多线程环境下是不安全的,需要手动加锁保证线程安全;
- 可适应扩容: HashMap在添加元素过程中,当元素个数达到临界值时,会自动对数组进行扩容,保证可容纳更多元素;
缺点
- 内存占用:HashMap内部维护了一个数组,如果数组过大则会占用大量的内存;
- 不可保证顺序:HashMap内部使用哈希算法存储,因此键值对的顺序不可预测。
在实际应用中,需要根据具体情况来选择使用HashMap还是其他的容器。
类代码方法介绍
构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
其中,第一个构造方法创建了默认大小的HashMap,第二个构造方法指定了HashMap的初始容量,第三个构造方法同时指定了初始容量和负载因子,第四个构造方法根据给定的Map创建了一个新的HashMap对象。
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
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;
}
其中,put方法用于向HashMap中添加新的键值对,putVal方法是实际的插入操作。如果当前HashMap中的数组为空,则进行初始化;否则,根据键的哈希值计算出要插入的位置。如果该位置已经有Entry,则遍历整个链表,直到找到该键的Entry,然后更新其值;如果整个链表中不存在该键的Entry,则新建一个Entry并插入到链表头部。如果数组中该位置上的链表长度大于等于阈值,则将链表转化为红黑树。
get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
其中,get方法用于获取指定键对应的值,getNode方法用于查找对应的Entry。如果数组中该位置上的Entry不为空,则遍历整个链表或红黑树,直到找到该键的Entry。
remove方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
其中,remove方法用于删除指定键值对,removeNode
方法为实际的删除操作。如果数组中该位置上的Entry不为空,则遍历整个链表或红黑树,找到该键的Entry,并删除之。
其他方法
HashMap还提供了一些其他的方法,如size
、isEmpty
、containsKey
、containsValue
、clear
等,这些方法都是用于操作HashMap中的键值对。
测试用例
为了更好地理解HashMap的应用,我们提供了如下的测试用例,读者可以通过测试用例加深对HashMap的应用和实现的理解:
测试代码演示
package com.example.javase.collection;
import java.util.HashMap;
import java.util.Map;
/**
* @Author ms
* @Date 2023-10-22 19:47
*/
public class HashMapTest {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
// test put() and get()
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
System.out.println(map.get("a")); // output: 1
System.out.println(map.get("b")); // output: 2
System.out.println(map.get("c")); // output: 3
// test replace()
map.put("a", 4);
System.out.println(map.get("a")); // output: 4
// test remove()
map.remove("a");
System.out.println(map.get("a")); // output: null
// test clear()
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.clear();
System.out.println(map.size()); // output: 0
// test contains()
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
System.out.println(map.containsKey("a")); // output: true
System.out.println(map.containsValue(2)); // output: true
System.out.println(map.containsKey("d")); // output: false
System.out.println(map.containsValue(4)); // output: false
}
}
测试结果
根据如上测试用例,本地测试结果如下,仅供参考,你们也可以自行修改测试用例或者添加更多的测试数据或测试方法,进行熟练学习以此加深理解。
测试代码分析
根据如上测试用例,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。
如上测试用例演示了如何使用 Java 中的 HashMap 类。首先,代码创建了一个空的 HashMap 对象,并使用 put()
方法添加了三个键值对。然后,代码使用 get()
方法获取这些键对应的值,并使用 replace()
方法替换掉其中一个键的值。接着,代码使用 remove()
方法删除了一个键值对,并使用 clear()
方法清空了整个 HashMap。最后,代码使用 containsKey()
和 containsValue()
方法测试是否包含某个键或值。
小结
HashMap是Java中一个重要的数据结构,内部维护了一个Entry数组,使用哈希算法将键值对映射到数组中的位置,实现快速查找。在实际开发中,HashMap可以用于存储对象属性、实现缓存、实现计数器等。HashMap的优点包括快速查找、高效存储、可适应扩容;缺点包括内存占用、不可保证顺序、线程不安全等。在使用时需要根据具体情况进行选择。
总结
通过本文的阐述,我们了解了HashMap在Java中的实现和应用场景,深入了解了其数据结构、源代码实现、方法介绍和优缺点分析。同时,我们也提供了相关测试用例,希望读者能够通过实践更好地理解HashMap的应用。对于Java程序员而言,掌握HashMap的使用和内部实现是非常重要的,可以在实际开发中发挥重要作用。
… …
文末
好啦,以上就是我这期的全部内容,如果有任何疑问,欢迎下方留言哦,咱们下期见。
… …
学习不分先后,知识不分多少;事无巨细,当以虚心求教;三人行,必有我师焉!!!
wished for you successed !!!
⭐️若喜欢我,就请关注我叭。
⭐️若对您有用,就请点赞叭。
⭐️若有疑问,就请评论留言告诉我叭。