遵守 TDD 实现一个精简版的 HashMap
上一篇文章笔者解读了 HashMap 的源码，正好趁热打铁，今天笔者抽了些时间通过 TDD 实现了一个精简版的 HashMap，经笔者测试，正常情况下效率略微逊于 HashMap。
预设计
public class SimpleHashMap<K, V> {
public V put(K key, V value);
public V get(K key);
public V remove(K key);
public boolean containsKey(K key);
public int size();
public Iterator<V> values();
public void forEach(Consumer<? super K> action);
}
复制代码
Tasking
- 无参构建 SimpleHashMap
- 构造函数初始化 initial capacity
- 构造函数初始化 initial capacity 和 load factor
- initial capacity 默认使用 16
- load factor 默认使用 0.75f
- 初始化的 resize 门槛为 initial capacity * load factor
- 再次 resize 门槛为 threshold = threshold << 1
- 增加 put 接口
- 计算 hash 值
- 增加 hash table 用于保存数据节点.
- 如果 hash table 的容量为 0 或者 hash table 的容量超过门槛，则设置新的 resize 门槛，并扩容和 rehash。
- hash table 的下标为 hash & (capacity -1)
- 扩容时需要把旧的 hash table 的数据转移到新的 hash table
- 转移数据到新的 hash table 之前需要 rehash，rehash = entry.hash & (new_capacity -1)
- 如果 hash 冲突，使用链表存储
- 如果同一个 hash 冲突超过 8 次，使用红黑树存储
- 增加 size 接口
- 增加全局的 size 成员变量.
- put 接口调用成功，则 size += 1.
- remove 接口调用成功，则 size -= 1.
- 考虑链表
- 考虑红黑树
- 增加 containsKey 接口
- 通过 key 计算 hash
- 通过 hash 计算 index
- 通过 index 检索 key，检索到return true,否则 return false，
- 考虑 hash table 为 null.
- 考虑链表
- 考虑红黑树
- 增加 get 接口
- 通过 key 计算 hash
- 通过 hash 计算 index
- 通过 index 检索 bucket
- 如果 bucket 存在多个数据节点，则需要判断 key 的值和引用是否相等.
- 如果相等返回对应的 value，否则返回 null.
- 考虑链表
- 考虑红黑树
- 增加 remove 接口
- 通过 key 计算 hash
- 通过 hash 计算 index
- 通过 index 检索 bucket
- 如果相等则将对应的 bucket 置 null，并返回对应的 value，否则返回 null，
- 考虑链表
- 考虑红黑树
- 增加 values 接口
- 每次 put 成功时保存 list 中到
- 每次 put 替换成功时，需要替换 list 中对应的 value
- 每次 remove 成功时从 list 中到删除
- 考虑链表
- 考虑红黑树
- 增加 forEach 接口
- 遍历 hash table
- 如果存在 bucket，则通过 action.apply(key)
- 考虑链表
- 考虑红黑树
- 增加 fail-fast
- 增加 modCount 成员变量用于统计变更次数
- 迭代前后需要验证 modCount 前后是否一致
- 如果 modCount 前后是否一致需要抛出 ConcurrentModificationException.
- 增加 rb tree 保存 hash 冲突超过 8 次的数据节点.
测试覆盖率
测试代码
**
* @author lyning
*/
public class SimpleHashMapTest {
private SimpleHashMap<Integer, Integer> map;
@BeforeEach
public void setUp() throws Exception {
// given
this.map = new SimpleHashMap<>();
}
/************ size test start **********/
@Test
@DisplayName("given empty entries" +
"when call size() " +
"then return 0")
public void size1() {
// when
int size = map.size();
// then
assertThat(size).isZero();
}
@Test
@DisplayName("given multiple entries(contains duplicate key) " +
"when call size() " +
"then return correct size")
public void size2() {
// given
SimpleHashMap<Integer, Integer> map = new SimpleHashMap<>();
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(3, 4);
map.put(3, 5);
map.put(4, 4);
map.put(5, 5);
map.remove(1);
map.remove(2);
// when
int size = map.size();
// then
assertThat(size).isEqualTo(3);
}
@Test
@DisplayName("given multiple entries(hash conflict) " +
"when call size() " +
"then return correct size")
public void size3() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
map.remove(new HashConflict(5));
map.remove(new HashConflict(3));
// when
int size = map.size();
// then
assertThat(size).isEqualTo(3);
}
/************ size test end **********/
/************ put test start **********/
@Test
@DisplayName("given empty entries " +
"when put one entry " +
"then return size 1")
public void put1() {
// when
map.put(1, 1);
// then
assertThat(map.size()).isOne();
}
@Test
@DisplayName("given empty entries " +
"when put two entries(duplicate key) " +
"then return size 1")
public void put2() {
// when
map.put(1, 1);
map.put(1, 2);
// then
assertThat(map.size()).isEqualTo(1);
}
@Test
@DisplayName("given empty entries " +
"when put three entries " +
"then return size 3")
public void put3() {
// when
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
// then
assertThat(map.size()).isEqualTo(3);
}
@Test
@DisplayName("should return value " +
"when call put")
public void put4() {
// when
Integer value = map.put(1, 1);
// then
assertThat(value).isEqualTo(1);
}
@Test
@DisplayName("given empty entries " +
"when put multiples entries(hash conflict) " +
"then")
public void put5() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
// when
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(3), 4);
map.put(new HashConflict(3), 5);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
// then
assertThat(Lists.newArrayList(map.values())).isEqualTo(Lists.list(1, 2, 5, 4, 5));
}
@Test
@DisplayName("should auto grow " +
"when capacity exceed threshold")
public void put6() {
// given default threshold = 8
// when
for (int i = 1; i <= 20; i++) {
map.put(i, i);
}
// then
assertThat(map.size()).isEqualTo(20);
assertThat(map.get(20)).isEqualTo(20);
}
/************ put test end **********/
/************ get test start **********/
@Test
@DisplayName("given empty entries" +
"when get by null key" +
"then return null")
public void get1() {
// when
Integer value = map.get(null);
// then
assertThat(value).isNull();
}
@Test
@DisplayName("given empty entries" +
"when get value by not exist key" +
"then return null")
public void get2() {
// when
Integer value = map.get(2);
// then
assertThat(value).isNull();
}
@Test
@DisplayName("given entry" +
"when get value by not exist key" +
"then return null")
public void get3() {
// given
map.put(1, 1);
// when
Integer value = map.get(2);
// then
assertThat(value).isNull();
}
@Test
@DisplayName("given entry" +
"when get value" +
"then return value")
public void get4() {
// given
map.put(1, 1);
// when
Integer value = map.get(1);
// then
assertThat(value).isEqualTo(1);
}
@Test
@DisplayName("given multiple entries(hash conflict)" +
"when get value by hash conflict key" +
"then return value")
public void get5() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(3), 4);
map.put(new HashConflict(3), 5);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
// when
Integer value = map.get(new HashConflict(3));
// then
assertThat(value).isEqualTo(5);
}
@Test
@DisplayName("given multiple entries(hash conflict)" +
"when get value by not exist hash conflict key" +
"then return null")
public void get6() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
// when
Integer value = map.get(new HashConflict(6));
// then
assertThat(value).isNull();
}
/************ get test end **********/
/************ remove test start **********/
@Test
@DisplayName("given empty entries" +
"when remove by null key" +
"then return null")
public void remove1() {
// when
Integer value = map.remove(null);
// then
assertThat(value).isNull();
}
@Test
@DisplayName("given entry" +
"when remove by null key" +
"then return null")
public void remove2() {
// given
map.put(1, 1);
// when
Integer value = map.remove(null);
// then
assertThat(value).isNull();
}
@Test
@DisplayName("given entry" +
"when remove by key" +
"then return value")
public void remove3() {
// given
map.put(1, 1);
// when
int value = map.remove(1);
// then
assertThat(value).isEqualTo(1);
}
@Test
@DisplayName("given entry" +
"when remove by not exist key" +
"then return null")
public void remove4() {
// given
map.put(1, 1);
// when
Integer value = map.remove(2);
// then
assertThat(value).isNull();
}
@Test
@DisplayName("given multiple entries(hash conflict)" +
"when remove by hash conflict key" +
"then return value")
public void remove5() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
// when
Integer value = map.remove(new HashConflict(3));
// then
assertThat(value).isEqualTo(3);
assertThat(Lists.newArrayList(map.values())).isEqualTo(Lists.list(1, 2, 4, 5));
}
/************ remove test end **********/
/************ values test start **********/
@Test
@DisplayName("given empty entries" +
"when call values" +
"then return empty values")
public void values1() {
// when
Iterable<Integer> values = map.values();
// then
assertThat(values).isEmpty();
}
@Test
@DisplayName("given multiple entries" +
"when call values" +
"then return all values")
public void values2() {
// given
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(3, 4);
map.put(4, 4);
map.remove(4);
// when
Iterable<Integer> values = map.values();
// then
assertThat(values.spliterator().estimateSize()).isEqualTo(3);
assertThat(Lists.newArrayList(values)).isEqualTo(Lists.list(1, 2, 4));
}
/************ values test end **********/
/************ containsKey test start **********/
@Test
@DisplayName("given entry" +
"when key exist" +
"then return true")
public void contains_key1() {
// given
map.put(1, 1);
// when
boolean result = map.containsKey(1);
// then
assertThat(result).isTrue();
}
@Test
@DisplayName("given entry" +
"when key not exist" +
"then return false")
public void containsKey2() {
// given
map.put(1, 1);
// when
boolean result = map.containsKey(2);
// then
assertThat(result).isFalse();
}
@Test
@DisplayName("given multiple entries(hash conflict)" +
"when call containsKey" +
"then return correct result")
public void containsKey3() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
// then
assertThat(map.containsKey(new HashConflict(3))).isTrue();
assertThat(map.containsKey(new HashConflict(5))).isTrue();
assertThat(map.containsKey(new HashConflict(6))).isFalse();
}
/************ containsKey test end **********/
/************ forEach test start **********/
@Test
@DisplayName("given multiple entries" +
"when call forEach" +
"then pass")
public void forEach1() {
// given
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
// when
List<Integer> results = new ArrayList<>();
map.forEach((key) -> results.add(map.get(key)));
// then
assertThat(results).isEqualTo(Lists.list(1, 2, 3, 4));
}
@Test
@DisplayName("given multiple entries(hash conflict)" +
"when call forEach" +
"then pass")
public void forEach2() {
// given
SimpleHashMap<HashConflict, Integer> map = new SimpleHashMap<>();
map.put(new HashConflict(1), 1);
map.put(new HashConflict(2), 2);
map.put(new HashConflict(3), 3);
map.put(new HashConflict(4), 4);
map.put(new HashConflict(5), 5);
// when
List<Integer> results = new ArrayList<>();
map.forEach((key) -> results.add(map.get(key)));
// then
assertThat(results).isEqualTo(Lists.list(1, 2, 3, 4, 5));
}
/************ forEach test end **********/
class HashConflict {
private int field;
HashConflict(int field) {
this.field = field;
}
@Override
public int hashCode() {
return this.field <= 8 ? 1 : this.field;
}
@Override
public boolean equals(Object obj) {
return ((HashConflict) obj).field == this.field;
}
}
}
复制代码
SimpleHashMap 源码
/**
* @author lyning
*/
public class SimpleHashMap<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private int size;
private Bucket<K, V>[] table;
private int threshold;
public boolean containsKey(K key) {
int hash = this.hash(key);
int index = this.index(hash);
Bucket<K, V> bucket = this.table[index];
return bucket != null
&& bucket.lookup(key) != null;
}
public void forEach(Consumer<K> action) {
for (Bucket<K, V> bucket : this.table) {
while (bucket != null) {
action.accept(bucket.key);
bucket = bucket.next;
}
}
}
public V get(K key) {
if (this.tableEmpty()) {
return null;
}
int hash = this.hash(key);
int index = this.index(hash);
return this.getVal(index, key);
}
public V put(K key, V value) {
if (this.tableEmpty() || this.nearByThreshold()) {
this.resize();
}
int hash = this.hash(key);
return this.putVal(key, value, hash);
}
public V remove(K key) {
if (this.tableEmpty()) {
return null;
}
int hash = this.hash(key);
int index = this.index(hash);
return this.removeVal(index, key);
}
public int size() {
return this.size;
}
public Iterable<V> values() {
if (this.tableEmpty()) {
return new ArrayList<>();
}
List<V> collections = new ArrayList<>();
this.collectValues(collections);
return collections;
}
private void collectValues(List<V> collections) {
for (Bucket<K, V> bucket : this.table) {
while (bucket != null) {
collections.add(bucket.value);
bucket = bucket.next;
}
}
}
private Bucket<K, V> findBucket(int index) {
return this.table[index];
}
private V getVal(int index, K key) {
Bucket<K, V> bucket = this.findBucket(index);
if (Objects.isNull(bucket) || Objects.isNull(bucket = bucket.lookup(key))) {
return null;
}
return bucket.value;
}
private void grow(int newCap) {
if (this.tableEmpty()) {
this.initTable(newCap);
return;
}
this.table = this.rebuildTable(newCap);
}
private int hash(K key) {
int hashcode;
return key == null
? 0
: (hashcode = key.hashCode()) ^ (hashcode >>> 16);
}
private int index(int hash) {
return hash & (this.table.length - 1);
}
private void initTable(int newCap) {
this.table = new Bucket[newCap];
}
private boolean nearByThreshold() {
return this.size + 1 >= this.threshold;
}
private V putVal(K key, V value, int hash) {
int index = this.index(hash);
Bucket<K, V> bucket = this.table[index];
if (Objects.isNull(bucket)) {
this.table[index] = new Bucket<>(hash, key, value);
} else {
Bucket<K, V> indexBucket = bucket.lookup(key);
if (indexBucket != null) {
indexBucket.value = value;
return value;
}
bucket.putLast(new Bucket<>(hash, key, value));
}
this.size += 1;
return value;
}
private Bucket<K, V>[] rebuildTable(int newCap) {
Bucket<K, V>[] oldTable = this.table;
Bucket<K, V>[] newTable = new Bucket[newCap];
for (Bucket<K, V> bucket : oldTable) {
if (bucket != null) {
int index = this.index(bucket.hash);
newTable[index] = bucket;
}
}
return newTable;
}
private V removeVal(int index, K key) {
Bucket<K, V> bucket = this.findBucket(index);
Bucket<K, V> prev = null;
while (bucket != null) {
if (bucket.matchKey(key)) {
if (Objects.isNull(prev)) {
this.table[index] = null;
} else {
prev.next = bucket.next;
}
this.size -= 1;
return bucket.value;
}
prev = bucket;
bucket = bucket.next;
}
return null;
}
private void resize() {
int oldCap = this.tableCapacity();
int newCap = 0;
if (oldCap == 0) {
oldCap = DEFAULT_INITIAL_CAPACITY;
this.threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
} else {
newCap = oldCap << 1;
this.threshold = this.threshold << 1;
}
if (newCap == 0) {
newCap = oldCap;
}
this.grow(newCap);
}
private int tableCapacity() {
return Objects.isNull(this.table) ? 0 : this.table.length;
}
private boolean tableEmpty() {
return Objects.isNull(this.table);
}
static class Bucket<K, V> {
Bucket<K, V> next;
int hash;
K key;
V value;
public Bucket(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
public Bucket<K, V> lookup(K key) {
Bucket<K, V> bucket = this;
while (bucket != null) {
if (bucket.matchKey(key)) {
return bucket;
}
bucket = bucket.next;
}
return null;
}
public boolean matchKey(K key) {
return this.key == key || this.key.equals(key);
}
public void putLast(Bucket<K, V> bucket) {
this.last().next = bucket;
}
private Bucket last() {
Bucket<K, V> bucket = this;
while (true) {
if (Objects.isNull(bucket.next)) {
return bucket;
}
bucket = bucket.next;
}
}
}
}
复制代码
总结
其中最难的应属红黑树，真的是极其复杂，笔者用了一个小时还没能理解其中要领，索性使用链表替代了，等有时间再静下心来把未完成的任务消灭掉。
理解问题，Tasking，TDD（包含重构），这是笔者最近一直在遵守的规则，希望可以给您给来一点感悟。
源码
- READMD: github.com/lynings/lea…
- Test Code: github.com/lynings/lea…
- Resource: github.com/lynings/lea…
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
