一、概述

二、实现

2.1. 原理

AppendOnlyMap 实际上是⼀个只⽀持 record 添加和对Value进⾏更新的HashMap。与Java HashMap采⽤“数组+链表”实现不同，AppendOnlyMap只使⽤数组来存储元素，根据元素的Hash值确定存储位置，如果存储元素时发⽣Hash值冲突，则使⽤⼆次地址探测法（Quadratic probing)来解决Hash值冲突。

对于每个新来的<K，V>record，先使⽤Hash（K）计算其存放位置，如果存放位置为空，就把 record 存放到该位置。
如果该位置已经被占⽤，就使⽤⼆次探测法来找下⼀个空闲位置。如下图,插入数据<K6，V6>record来说，第1次找到的位置Hash（K6）已被K2占⽤。按照⼆次探测法向后递增1个record位置，也就是Hash（K6）+1×2，发现位置已被K3占⽤，然后向后递增4个record位置（指数递增，Hash（K6）+2×2），发现位置没有被占⽤，放进去即可