遵守 TDD 实现一个精简版的 HashMap-白红宇

前言

上一篇文章笔者解读了 HashMap 的源码，正好趁热打铁，今天笔者抽了些时间通过 TDD 实现了一个精简版的 HashMap，经笔者测试，正常情况下效率略微逊于 HashMap。

预设计

public class SimpleHashMap
    
      {    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
     
       values();    public void forEach(Consumer
       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
    
      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
     
       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
      
        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
       
         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
        
          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
         
           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
          
            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
           
             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
            
              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
             
               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
              
                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
               
                 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
                
                  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
    
      {    private static final int DEFAULT_INITIAL_CAPACITY = 16;    private static final float DEFAULT_LOAD_FACTOR = 0.75f;    private int size;    private Bucket
     
      [] table;    private int threshold;    public boolean containsKey(K key) {        int hash = this.hash(key);        int index = this.index(hash);        Bucket
      
        bucket = this.table[index];        return bucket != null                && bucket.lookup(key) != null;    }    public void forEach(Consumer
       
         action) {        for (Bucket
        
          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
         
           values() { if (this.tableEmpty()) { return new ArrayList<>(); } List
          
            collections = new ArrayList<>(); this.collectValues(collections); return collections; } private void collectValues(List
           
             collections) { for (Bucket
            
              bucket : this.table) { while (bucket != null) { collections.add(bucket.value); bucket = bucket.next; } } } private Bucket
             
               findBucket(int index) { return this.table[index]; } private V getVal(int index, K key) { Bucket
              
                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
               
                 bucket = this.table[index]; if (Objects.isNull(bucket)) { this.table[index] = new Bucket<>(hash, key, value); } else { Bucket
                
                  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
                 
                  [] rebuildTable(int newCap) { Bucket
                  
                   [] oldTable = this.table; Bucket
                   
                    [] newTable = new Bucket[newCap]; for (Bucket
                    
                      bucket : oldTable) { if (bucket != null) { int index = this.index(bucket.hash); newTable[index] = bucket; } } return newTable; } private V removeVal(int index, K key) { Bucket
                     
                       bucket = this.findBucket(index); Bucket
                      
                        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
                       
                         { Bucket
                        
                          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
                         
                           lookup(K key) { Bucket
                          
                            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
                           
                             bucket) { this.last().next = bucket; } private Bucket last() { Bucket
                            
                              bucket = this; while (true) { if (Objects.isNull(bucket.next)) { return bucket; } bucket = bucket.next; } } }}复制代码

总结

其中最难的应属红黑树，真的是极其复杂，笔者用了一个小时还没能理解其中要领，索性使用链表替代了，等有时间再静下心来把未完成的任务消灭掉。

理解问题，Tasking，TDD（包含重构），这是笔者最近一直在遵守的规则，希望可以给您给来一点感悟。

源码

READMD:

Test Code:

Resource: