HashMap在Map体系中的继承实现关系:
HashMap就是我们常说的哈希表。
哈希表的表示:https://blog.csdn.net/weixin_43598687/article/details/119713753
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
HashMap继承至AbstractMap,并且实现了Map, Cloneable, Serializable接口,支持可复制以及序列化操作。
HashMap的底层采用的是数组 + 链表 + 红黑树实现的。使用链地址法来处理冲突,也就是数组加链表的结合,在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。
哈希表的初始容量为16,最大容量为1,073,741,824(1<<30,230),负载因子为0.75,HashMap的容量必须为2n,如果相同哈希值,链表的长度超过8,就从链表转换成红黑树。
/** * The default initial capacity - MUST be a power of two. */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
static final int MAXIMUM_CAPACITY = 1 << 30;
/** * The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashMap也是我们最常用的一种Map结构,在HashMap中提供了多种构造方法,如下:
构造一个空的 HashMap具有指定的初始容量和负载因子。
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);
}
构造一个空的 HashMap ,具有指定的初始容量和默认负载系数(0.75)。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造一个空的 HashMap ,具有默认初始容量和默认负载系数(0.75)。
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
构造一个新的HashMap与指定的相同的映射Map 。 该HashMap与默认负载因数(0.75)和初始容量足以容纳映射在指定Map创建。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
前面提到Map集合的主干是一个Entry数组,Entry是Map的一个基本单元,每一个Entry包含一个key-value键值对。
Node是HashMap中的一个静态内部类,它实现了Map.Entry接口,一个Node就相当于一个Entry。
Node在HashMap中的定义如下:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> 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;
}
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;
}
}
返回此哈希表中键值映射的数量。
public int size() {
return size;
}
如果此哈希表不包含键值映射,则返回 true 。
public boolean isEmpty() {
return size == 0;
}
返回到指定键所映射的值。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
如果此映射包含指定键的映射,则返回 true 。
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
将指定的值与此映射中的指定键相关联。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
将指定map的所有映射复制到此map。
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
从该map中删除指定键的映射(如果存在)。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
从该map中删除所有的映射。
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
如果此map将一个或多个键映射到指定的值,则返回 true 。
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
返回此map中包含的键的Set视图。
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
返回此map中包含的值的Collection视图。
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
返回此map中包含的映射的Set视图。
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
返回到指定键所映射的值,如果此映射不包含该键的映射,返回defaultValue。
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
如果指定的键尚未与值相关联(或映射到 null )将其与给定值相关联并返回 null ,否则返回当前值。
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
仅当指定的键当前映射到指定的值时删除该条目。
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
仅当当前映射到指定的值时,才能替换指定键的条目。
public boolean replace(K key, V oldValue, V newValue) {
Node<K,V> e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
只有当目标映射到某个值时,才能替换指定键的条目。
public V replace(K key, V value) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
返回此 HashMap实例的浅拷贝:键和值本身不被克隆。
public Object clone() {
HashMap<K,V> result;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.reinitialize();
result.putMapEntries(this, false);
return result;
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_43598687/article/details/121717245
内容来源于网络,如有侵权,请联系作者删除!