集合3(Map)

Map 的实现类较多,在此我们关注 HashMap 、 TreeMap 、 HashTable 、 LinkedHashMap

接口

public interface Map<K,V>

1.特性

  • Map 不能有重复的键(覆盖),每个键可以映射到最多一个值
  • 允许将映射内容视为一组键、值集合或键值映射集合
  • key 不要求有序,不可以重复。 value 也不要求有序,但可以重复
  • 当使用对象作为 key 时,要重写 equals 和 hashCode 方法

2.方法

方法返回值描述
clear()void删除所有的映射。
containsKey(Object key)boolean检查Map中是否包含给定的键。
containsValue(Object value)boolean检查Map中是否包含给定的值。
entrySet()Set<Map.Entry<K,V>>返回包含Map中所有映射的Set集合。
get(Object key)V根据键返回对应的值。
isEmpty()boolean检查Map是否为空。
keySet()Set<K>返回Map中所有键的Set集合。
put(K key, V value)V向Map添加映射。
putAll(Map<? extends K,? extends V> m)void将指定Map中的映射复制到此映射。
remove(Object key)V如果键存在,删除映射。
remove(Object key, Object value)boolean当键值映射存在时,删除。
replace(K key, V value)boolean当键存在时,替换映射内容。
size()int返回Map中映射的数量。
values()Collection<V>返回所有值的集合。

3.TreeMap

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

1.特性

  • 继承 AbstractMap ,一个红黑树基于 NavigableMap 实现
  • 非线程安全的
  • key 不能存 `null ,但是 value 可以存 null
  • key 必须是可比较的 (实现 Comparable 接口,传递一个 Comparator 比较器)

image-20230906233151597

3.方法

方法返回值描述
clear()void删除所有的键值对。
clone()Object创建并返回此 TreeMap 实例的浅表副本。
containsKey(Object key)boolean检查是否包含指定的键。
containsValue(Object value)boolean检查是否包含指定的值。
entrySet()Set<Map.Entry<K,V>>返回包含所有映射的 Set 集合。
firstKey()K返回最小的键。
get(Object key)V根据键返回对应的值。
isEmpty()boolean检查是否为空。
keySet()Set<K>返回所有键的 Set 集合。
lastKey()K返回最大的键。
put(K key, V value)V将指定的键值对添加到 TreeMap 中。
putAll(Map<? extends K, ? extends V> m)void将指定 Map 中的映射添加到此 TreeMap 中。
remove(Object key)V删除指定键对应的键值对。
size()int返回 TreeMap 中键值对的数量。
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)SortedMap<K, V>返回一个子映射,其键的范围从 fromKeytoKey
tailMap(K fromKey)SortedMap<K, V>返回大于等于 fromKey 的部分映射。
values()Collection<V>返回所有值的 Collection

4.Hashtable

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, Serializable

Hashtable 是一个经典的哈希表数据结构,用于存储键值对。在构造方法中,可以指定初始容量(哈希表中的槽位数量)和加载因子。加载因子是一个浮点数,它表示在哈希表需要进行扩容之前可以存储多少键值对。默认情况下,Hashtable 的初始容量为 11,加载因子为 0.75。

1.特性

  • 该类实现了一个哈希表,它将键映射到值
  • 不允许 null 作为键和值
  • 默认初始容量( initialCapacity )为 11 ,默认负载因子( loadFactor )为 0.75f
  • 同步的(线程安全的)
  • 不保证顺序
  • 扩容方式是旧容量的2倍 +1
  • 为什么hashtable的扩容方式选择为2n+1
  • 为了均匀分布,降低冲突率
  • 数组 + 链表方式存储实现Hash表存储
  • 添加值时
  • 如果 hash 一样 equals 为 false 则将当前值添加到链表头
  • 如果 hash 一样 equals 为 true 则使用当前值替换原来的值 ( key 相同)

image-20230906233414426

2.构造方法

构造方法描述
Hashtable()创建一个空的 Hashtable,初始容量默认为 11。
Hashtable(int initialCapacity)创建一个具有指定初始容量的 Hashtable
Hashtable(int initialCapacity, float loadFactor)创建一个具有指定初始容量和加载因子的 Hashtable
Hashtable(Map<? extends K, ? extends V> t)创建一个包含指定 Map 中的键值对的 Hashtable

3.方法

方法描述
void clear()Hashtable 中移除所有键值对,使其变为空。
Object clone()创建并返回 Hashtable 的浅拷贝。
boolean contains(Object value)检查 Hashtable 中是否包含指定的值。
boolean containsKey(Object key)检查 Hashtable 中是否包含指定的键。
boolean containsValue(Object value)检查 Hashtable 中是否包含指定的值。
Enumeration<V> elements()返回一个枚举,用于遍历 Hashtable 中的所有值。
Set<Map.Entry<K, V>> entrySet()返回一个包含 Hashtable 中所有键值对的 Set 视图。
boolean equals(Object o)比较指定对象与 Hashtable 是否相等。
V get(Object key)根据指定的键获取对应的值。
int hashCode()返回 Hashtable 的哈希码值。
boolean isEmpty()检查 Hashtable 是否为空(不包含任何键值对)。
Enumeration<K> keys()返回一个枚举,用于遍历 Hashtable 中的所有键。
Set<K> keySet()返回一个包含 Hashtable 中所有键的 Set 视图。
V put(K key, V value)Hashtable 中添加键值对。
void putAll(Map<? extends K, ? extends V> t)将指定 Map 中的键值对添加到 Hashtable 中。
V remove(Object key)Hashtable 中移除指定键的键值对,并返回对应的值。
int size()返回 Hashtable 中键值对的数量。
String toString()返回包含 Hashtable 中键值对的字符串表示形式。
Collection<V> values()返回一个包含 Hashtable 中所有值的 Collection 视图。

4.put过程

public synchronized V put(K key, V value) {
// 值不能为 null
if (value == null) {
throw new NullPointerException();
}
// 确认 key 不在 hashtable 中存在
Entry<?,?> tab[] = table;
// 计算 key 的 hash
int hash = key.hashCode();
// 找 key 应在存放在 数组中的位置
int index = (hash & 0x7FFFFFFF) % tab.length;
// index 位置的元素的 key 和 当前的 key 不一样
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
// 判断 key 是否相同
if ((entry.hash == hash) && entry.key.equals(key)) {
// 当 key 一样时,替换值
V old = entry.value;
HashMap
基于哈希表的实现的 Map 接口
允许 null 的值和 null 键
非线程安全
entry.value = value;
return old;
}
}
// 当 key 在 hashtable 中不存在时,添加
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
Entry<?,?> tab[] = table;
// 判断是否需要 "扩容"
if (count >= threshold) {
// 对数组进行扩容 (2n + 1),将原有元素重新计算 hash
rehash();
tab = table;
// 将当前的 key 也重新计算 hash
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// 原来数组中的 entry 对象
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
// 创建一个 新的 entry 对象, 放到 数组中
tab[index] = new Entry<>(hash, key, value, e);
// 元素个数 +1
count++;
// 修改次数 +1
modCount++;

5.HashMap

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

1.特性

  • 基于哈希表的实现的 Map 接口
  • 允许 null 的值和 null 键
  • 非线程安全
  • 默认容量 16,默认负载因子 0.75
  • HashMap容量是2的n次方
  • 扩容是 2 倍旧的容量
  • 在存储数据时, key 的 hash 计算调用的是 HashMap 中的 hash 方法
  • 添加值时,如果 hash 一样添加到链表尾部

HashMap 类大致相当于 Hashtable ,除了它是不同步的,并允许null

注:这里允许null指的是key允许一个null值,value允许多个null

内部采用 数组 + 链表实现 , JDK 8 及以后版本增加红黑树的支持

2.put过程image-20230906234645363

存储时,根据内部的 hash 方法计算 key ,来确定 value 的存储位置( Map 的桶bucket),
如果 hash 相同,在计算下标。如果产生没有碰撞( key 不相同),直接放到桶中,由于 h
ash 相同,所以放到一个桶中。放的时候,如果没有超过阈值(8),以链表的形式放到后
边,长度超过阈值且数组长度大于等于64将链表转换成红黑树存储。

删除元素时,如果时以红黑树存储的如果节点小于 6 个将会变为链表存储
如果产生碰撞(节点已经存在)就替换值

public V put(K key, V value) {
// 根据 key 计算 hash 值后调用 putVal 方法
return putVal(hash(key), key, value, false, true);
}
// HashMap 中计算 hash 的方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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;
// (n - 1) & hash 找key在数组中的位置。 判断这个位置是否有元素
if ((p = tab[i = (n - 1) & hash]) == null)
// 这个位置没元素,直接放到这个位置上
tab[i] = newNode(hash, key, value, null);
else {
// i 这个位置上有元素
Node<K,V> e; K k;
// 判断当前hash和 i这个位置上的元素的hash是否一样
if (p.hash == hash &&
// key 是否相同
((k = p.key) == key || (key != null && key.equals(k))))
// 已经存在同样的 key, 将原来 key 对象赋值给 e
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);
// 当链表节点数 大于等于 8 时
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;
使用,主要是操作方法,demo如下:
}
}
if (e != null) { // existing mapping for key 已经存在这个 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