HashMap(JDK 14)

发表于 | 分类于 |

public class HashMap extends AbstractMap

implements Map, Cloneable, Serializable

与父类AbstractMap都声明实现Map是为了易读。

是基于HashTable的Map接口实现。与HashTable的区别是非同步和支持null作为键名和键值。

影响性能的两个因素：初始容量和负载因子（默认0.75）。

元素数量达到两者乘积时，再哈希。

过多相同哈希值的元素将影响性能。当元素实现了Comparable接口，将使用比较顺序。

创建时同步：

1
Map m = Collections.synchronizedMap(new HashMap(...));

fail-fast: 除了迭代器自身的结构改变外，其他的结构改变将抛出异常ConcurrentModificationException。

fail-fast在非同步的并发更改中不被保证。仅检测缺陷，程序的正确性不应该对此依赖。

当bin中元素过多时(TREEIFY_THRESHOLD=8)，将转换为TreeNode(类似于TreeMap)。大多数操作首先尝试按照bin使用，TreeNode可用时再用。可以在元素较多时提高查找效率。当元素减少到一定数量，恢复bin结构。

所有元素都是TreeNode的bin，称为Tree bin。通常按照哈希值排序。但是当两个元素属于同一类且实现了Comparable接口(使用反射获取，详见comparableClassFor())，则根据compareTo()方法比较。对于不理想的hashcode()，或没有实现Comparable()都能达到对数时间复杂度。即使两种情况同时存在，TreeNode时空复杂度约是常规的2倍，也比用户没有处理好以上两种情况的影响小。Tree bin的根节点通常是第一个Tree node。但在某种情况下可能是其他（当前仅对于Iterator.remove()，可恢复）。

内部方法允许在不需重新计算哈希值的情况下互相调用。

当bin列表树化、分割或解树化时，保持其相对的访问和遍历顺序，以提供良好的本地性，且在简化分割和遍历处理(调用Iterator.remove())。使用comparator插入时，比较类和识别哈希值(tie-breaker)。

子类LinkedHashMap中普通模式和树模式的使用更加复杂。

类似并发编程的SSA代码样式避免了复杂指针操作中的别名错误。SSA，静态单赋值，变量只赋值一次，定义在使用之前。

树化阈值必须大于2，应该至少为8，默认为8。时空效率两倍 + 泊松分布？

解树化阈值应小于树化阈值，默认为6。

bin树化的最小表容量，大于时才会树化，否则扩容。为了避免扩容和树化阈值冲突，应为4倍树化阈值。

hash()：键名高16位不变，低16位与高16位异或。

putVal()：

  • Node数组是否非空，否则重置大小
  • 映射链表是否存在，否则新建(因位置为空，无需判断树化)
  • 是否是首个节点，是则后续复制
  • 是否是树，是则树中查找
  • 节点是否存在，否则新建并判断树化
  • 最后，若新建了节点，修改计数自增，判断是否扩容

tableSizeFor():获取不小于cap的2的幂

resize()扩容不会树化

treeifyBin()树化Bin，容量小于MIN_TREEIFY_CAPACITY只会扩容

public abstract class AbstractMap implements Map

  • 提供不可变Map缺省实现，任何与put/get/迭代器remove相关的操作，默认抛出unsupportedOperationException。
  • 获取键名或键值时，首先查找参数为null的情形，其次找其他值。找不到返回null。注意区分K/V为null和找不到的情形。

  • equals

    • 1 是否相同引用
    • 2 是否同一祖先Map
    • 3 是否容量一致
    • 4 逐一比较元素。注意区分null键值

  • 哈希值是所有entry哈希值之和

entry的哈希值是键名与键值哈希值异或，其中null的哈希值为0。

  • clone是浅拷贝，keys和values标记为非序列化，不拷贝
  • SimpleEntry和SimpleImmutableEntry是不相关的类，即使部分代码相同，但不足以抽象出共同祖先。SimpleEntry名值可变，具有setValue方法，用于促进自定义Map实现，如map.entrySet().toArray()。SimpleImmutableEntry名值不可变，setValue方法抛出unsupportedOperationException，用于返回线程安全的map快照。
  • 为了解决问题JDK-8015417，增加了一个私有静态方法eq用于替代Object.equals()，在SimpleEntry和SimpleImmutableEntry中检测空值并比较。

JDK-8015417：profile pollution after call through invokestatic to shared code。

image-20200526114237215

public interface Map

替换抽象类Dictionary

提供3种集合视图:键、值和键值对。

不同的实现有不同的顺序保证。如TreeMap保证顺序，而HashMap不保证。

注意使用可变对象作为键名的情况。键名对象改变，影响哈希值和比较结果。

通用目的扩展需要使用无参和参数为Map的两个构造器，如JDK中的实现

大多数实现没有对自身引用进行处理

不可变Map不允许null键名或键值。

当所有键名和键值为可序列化的，该不可变Map可序列化。由于工厂随意创建或复用，任何识别相关的操作是不可靠的。如==、equal和hashcode

容量即使超过Integer.MAX_VALUE，也只返回Integer.MAX_VALUE

containsKey()可用于区分null键值还是映射不存在

entrySet()、keySet()和values()方法不支持add()或addAll()

默认的Comparator直接比较键名或键值对象

of()可以返回0-10个键值对的不可变Map

image-20200526115440815

public interface Cloneable

标记接口，允许通过Object.clone()进行字段到字段的复制

复制没有标记的对象，将抛出异常CloneNotSupportedException

通常实现该接口的类需要将protected的Object.clone()重写为public

反射调用时，不保证成功

public interface Serializable

标记接口

反序列化不可靠数据是危险的，详见Serialization and Deserialization

对于不可序列化父类，只有其可以通过无参构造器初始化字段时，序列化的子类可以保存和恢复其非私有字段（public、protected、package）。

反序列化时，序列化子类无参构造器需要可以使用。

不支持序列化的对象将抛出异常NotSerializableException

序列化与反序列化过程中需要特殊处理的类，必须实现以下接口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 负责写入对象状态，以便恢复
// 默认实现可调用out.defaultWriteObject
// 不必关心父类或子类的状态
// 对象字段通过writeObject， 基本类型通过DataOutput写到ObjectOutputStream
private void writeObject(java.io.ObjectOutputStream out) throws IOException;

// 负责恢复对象状态，通过映射流中和当前对象中相同名称字段
// 默认实现可调用in.defaultReadObject
// 不必关心父类或子类的状态
// 对象字段通过writeObject， 基本类型通过DataInput写到ObjectInputStream
private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException;

// 用于处理流中没有列出反序列化对象父类的情形
// 发送方和接收方版本不一致导致接收方有父类，或序列化过程被干扰
private void readObjectNoData() throws ObjectStreamException;

写入时替换对象。当writeReplace存在时，被序列化过程调用。writeReplace需要能被对象内部方法访问，因此可以是私有、保护或包私有的。子类遵从Java访问规则。

readResolve调用和访问规则类似。

1
2
3
ANY-ACCESS-MODIFIER Object writeReplace() throws ObjectStreamException;

ANY-ACCESS-MODIFIER Object readResolve() throws ObjectStreamException;

枚举类型都是可序列化的。但以上声明的所有方法不可用。详见Java Object Serialization Specification

serialVersionUID用于在运行时检查发送方和接收方是否加载了与对象匹配的类，否则抛出异常InvalidClassException。可以显示声明为静态、不可变、长整型。

1
ANY-ACCESS-MODIFIER static final long serialVersionUID = 42L;

没有显示声明时，默认通过阶段对象细节产生默认的serialVersionUID， 详见Java Object Serialization Specification。

由于与细节有关，对于不同的编译器实现，可能产生不同的默认值。因此，建议显式声明。

由于之和当前对象相关，不必继承，建议声明为私有。

枚举类型采用默认的serialVersionUID = 0L

数组类型由于不能显式定义，serialVersionUID被忽略。

参考资料

Collections Framework Overview