HashMap、LinkedHashMap 学习笔记

用户头像
陈俊
关注
发布于: 2020 年 08 月 13 日

HashMap

来看一下 HashMap 的特点:

  • HashMap 的键必须是唯一的,不能重复。

  • HashMap 的键允许为 null,但只能有一个这样的键;值可以有多个 null。

  • HashMap 是无序的,它不保证元素的任何特定顺序。

  • HashMap 不是线程安全的;多线程环境下,建议使用 ConcurrentHashMap,或者使用 Collections.synchronizedMap(hashMap) 将 HashMap 转成线程同步的。

  • 只能使用关联的键来获取值。

  • HashMap 只能存储对象,所以基本数据类型应该使用其包装器类型,比如说 int 应该为 Integer。

  • HashMap 实现了 Cloneable 和 Serializable 接口,因此可以拷贝和序列化。



  1. HashMap 有 5 个重要的字段

// 注意是数组,默认长度为 16,在第一次执行 resize() 方法的时候初始化
transient Node<K,V>[] table;
// Node 有 3 个字段
final int hash;
final K key;
V value;
HashMap.Node<K,V> next;
// 实际存储键值对数量
transient int size;
// 记录实际操作次数,迭代器在执行 remove() 等操作的时候快速抛出 ConcurrentModificationException
transient int modCount;
// 数组大小 * 负载因子。默认情况下为 12(16 * 0.75)
int threshold;
// 负载因子,默认的 0.75 是对空间和时间效率上的一个平衡选择,一般不建议修改
final float loadFactor;



  1. HashMap 的 Hash 算法

Hash,把任意长度的数据通过一种算法映射到固定长度的域上(散列值)。



HashMap 的底层数据结构是一个数组,不管是增加、删除,还是查找键值对,定位到数组的下标非常关键。 HashMap 是通过什么样的方法来定位下标呢?

String [] keys = {"沉","默","王","二"};
for (String k : keys) {
int hasCode = k.hashCode();
int right = hasCode >>> 16;
int hash = hasCode ^ right;
int i = (16 - 1) & hash;
System.out.println(hash + " 下标:" + i);
}



>>> 为无符号右移运算符,高位补 0,移多少位补多少个 0

^ 为异或运算符,其运算规则为 1^0 = 1、1^1 = 0、0^1 = 1、0^0 = 0。

& 为按位与运算符,运算规则是将两边的数转换为二进制位,然后运算最终值,运算规则即(两个为真才为真)1&1=1、1&0=0、0&1=0、0&0=0。



k.hashCode() 用来计算键的 hashCode 值。对于任意给定的对象,只要它的 hashCode() 返回值是相同,那么 hash() 方法计算得到的 Hash 码就总是相同的。

要能够做到这一点,就要求作为键的对象必须是不可变的,并且 hashCode() 方法要足够的巧妙,能够最大可能返回不重复的 hashCode 值,比如说 String 类。

public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}



  1. put()

计算后的 hash 值冲突了怎么办?put() 方法会先调用 hash() 方法计算 key 的 hash 值,然后再调用内部方法 putVal()

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// ①、数组 table 为 null 时,调用 resize 方法创建默认大小的数组
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 {
HashMap.Node<K,V> e; K k;
// ③、如果键已经存在了,并且 hash 值相同,直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④、红黑树处理
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.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;
}
// 如果键已经存在了,并且 hash 值相同,直接覆盖
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;
}

如果哈希冲突的话,会执行 ② 处对应的 else 语句,先判断键是否相等,相等的话直接覆盖;否则执行 ④,做红黑树处理;如果不是,会执行 ⑤,把上一个节点的 next 赋值为新的 Node。

也就是说,如果哈希冲突了,会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理。

简单点说,就是数组加链表,由于链表的查询效率比较低(时间复杂度为 ),Java 8 又追加了红黑树(时间复杂度为 )。



  1. get()

首先计算 key 的 hash 值,当 hash 值确定后,键值对在数组中的下标位置也就确定了,然后再调用 getNode() 方法:

final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.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 HashMap.TreeNode)
return ((HashMap.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;
}

其中 first = tab[(n - 1) & hash] 就可以快速的确定键对应的值,如果键相等并且键的 hash 相等,则直接返回;如果键的哈希冲突了,就先判断是不是红黑树,不是的话就遍历链表。



LinkedHashMap

  1. 插入顺序

LinkedHashMap.Entry 继承了 HashMap.Node,并且追加了两个字段 before 和 after



LinkedHashMap 在添加第一个元素的时候,会把 head 赋值为第一个元素,等到第二个元素添加进来的时候,会把第二个元素的 before 赋值为第一个元素,第一个元素的 after 赋值为第二个元素。



HashMap#put

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// ①、数组 table 为 null 时,调用 resize 方法创建默认大小的数组
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);
}



LinkedHashMap 重写 newNode 方法

HashMap.Node<K,V> newNode(int hash, K key, V value, HashMap.Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}



  1. 访问顺序

访问包括调用 get() 方法、remove() 方法和 put() 方法。最不经常访问的放在头部,使用 LinkedHashMap 来实现 LRU(Least Recently Used) 缓存。



重写 removeEldestEntry

public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 5;
public MyLinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
}



维护访问顺序

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }



哪个元素被访问,哪个元素就放到最后

void afterNodeAccess(HashMap.Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}



LinkedHashMap 实现 LRU,在插入元素的时候,需要调用 put() 方法,该方法最后会调用 afterNodeInsertion() 方法,这个方法被 LinkedHashMap 重写了。removeEldestEntry() 方法会判断第一个元素是否超出了可容纳的最大范围,如果超出,那就会调用 removeNode() 方法对最不经常访问的那个元素进行删除。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}



用户头像

陈俊

关注

还未添加个人签名 2017.09.10 加入

还未添加个人简介

评论

发布
暂无评论
HashMap、LinkedHashMap 学习笔记