preface
In my last article, I read the source code of HashMap and struck while the iron was hot. Today, I took some time to implement a simplified version of HashMap through TDD. In my tests, it is slightly less efficient than HashMap under normal conditions.
Preliminary design
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(a);
public Iterator<V> values(a);
public void forEach(Consumer<? super K> action);
}
Copy the code
Tasking
- Build SimpleHashMap without arguments
- Constructor to initialize Initial Capacity
- The initializer initializes the Initial capacity and Load factor
- Initial Capacity The default value is 16
- Load factor uses 0.75F by default
- The resize threshold for initialization is Initial capacity x load factor
- Resize threshold = threshold << 1
- Adding a PUT Interface
- Calculate the hash value
- Add a Hash table to store data nodes.
- If the hash table capacity is 0 or the hash table capacity exceeds the threshold, set a new threshold for resize and expand the hash capacity.
- Hash table subscripts are hash & (capacity-1)
- During capacity expansion, data from the old Hash table must be transferred to the new hash table
- To transfer data to the new hash table, rehash = entry.hash & (new_capacity -1)
- If hash conflicts, use linked lists for storage
- If the same hash conflicts for more than eight times, use red-black tree storage
- Add size interface
- Add the global size member variable.
- If the PUT interface is successfully invoked, size += 1.
- If the remove interface is successfully invoked, size -= 1.
- Consider the list
- Consider a red-black tree
- Add the containsKey interface
- Computes the hash using the key
- Calculates the index using the hash function
- Index key, return true, otherwise return false,
- Consider that the hash table is null.
- Consider the list
- Consider a red-black tree
- Adding a GET Interface
- Computes the hash using the key
- Calculates the index using the hash function
- Retrieve the bucket through index
- If the bucket has multiple data nodes, you need to determine whether the value of the key is equal to the reference.
- Return value if equal, null otherwise.
- Consider the list
- Consider a red-black tree
- Adding the Remove Interface
- Computes the hash using the key
- Calculates the index using the hash function
- Retrieve the bucket through index
- Set the corresponding bucket to null if it is equal and return the corresponding value, otherwise return NULL,
- Consider the list
- Consider a red-black tree
- Add values interface
- Save the list to every time the put succeeds
- Each time the put is replaced successfully, the value in the list needs to be replaced
- Remove from the list on each successful remove
- Consider the list
- Consider a red-black tree
- Add a forEach interface
- Traverse the hash table
- If there is a bucket, use action.apply(key)
- Consider the list
- Consider a red-black tree
- Increase the fail – fast
- Add modCount member variables to count changes
- You need to verify that modCount is consistent before and after iteration
- If modCount whether consistent need to throw ConcurrentModificationException.
- Add an RB tree to store data nodes that have more than eight hash conflicts.
Test coverage
The test code
* * *@author lyning
*/
public class SimpleHashMapTest {
private SimpleHashMap<Integer, Integer> map;
@BeforeEach
public void setUp(a) throws Exception {
// given
this.map = new SimpleHashMap<>();
}
/************ size test start **********/
@Test
@DisplayName("given empty entries" +
"when call size() " +
"then return 0")
public void size1(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
// 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(a) {
return this.field <= 8 ? 1 : this.field;
}
@Override
public boolean equals(Object obj) {
return ((HashConflict) obj).field == this.field; }}}Copy the code
SimpleHashMap source
/ * * *@author lyning
*/
public class SimpleHashMap<K.V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75 f;
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];
returnbucket ! =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(a) {
return this.size;
}
public Iterable<V> values(a) {
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(a) {
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(a) {
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(a) {
return Objects.isNull(this.table) ? 0 : this.table.length;
}
private boolean tableEmpty(a) {
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(a) {
Bucket<K, V> bucket = this;
while (true) {
if (Objects.isNull(bucket.next)) {
returnbucket; } bucket = bucket.next; }}}}Copy the code
conclusion
One of the most difficult is the red-black tree, which is so complicated that I couldn’t understand it for an hour, so I used a linked list instead, waiting for time to settle down and eliminate the unfinished tasks.
Tasking, UNDERSTANDING problems, TDD (including refactoring), this is the rule that THE author has been obeying recently, hope to give you some insight.
The source code
- READMD: github.com/lynings/lea…
- The Test Code: github.com/lynings/lea…
- Resource: github.com/lynings/lea…