Map Implementation Evaluation
AionMap is a HashMap implementation and a useful data structure for smart contract development. There are several different ways of implementing a HashMap and resolving key collisions. This document details the energy consumption of three different HashMap implementations:
- B+ tree
- Open Addressing, using Linear Probing
- Separate Chaining
Separate Chaining and Open Addressing maps have two parameters that affect their performance: the initial capacity, and the load factor. The initial capacity is the size of the entry table, and the load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The threshold for initiating a rehashing operation is calculated as the product of the load factor and the current capacity. When the number of hash table entries exceeds this threshold, the capacity is doubled and the internal structure is rebuilt by rehashing all the keys.
In Open Addressing (with linear probing), resolving a hash collision is done by moving in a sequential manner through the entry table slots until we encounter the first slot that is empty. In separate chaining, each entry table slot points to a linked list of key-value pairs with the same hash. A new key-value pair with a colliding hash value is added to the end of the list. Note that map resizing is done based on its size. Key’s hashcode is used as the router in the B+ Tree implementation.
To obtain the results for this document, three different contracts were written, all of which utilise a HashMap that maps integer keys to String values. The code below is one of the sample contracts that were used for the experiment.
public class AionMapContract {
private static AionMap<Integer, String> map = new AionMap<>();
@Callable
public static void put(int key) {
map.put(key, "STRING");
}
@Callable
public static String get(int key) {
return map.get(key);
}
@Callable
public static String remove(int key) {
return map.remove(key);
}
}
HashMaps that implement Separate Chaining and Open Addressing algorithms were
initialized with an initial capacity of 16, and a load factor of 0.75. In these maps,
the hash value was calculated as: abs(Key.hashcode) % capacity.
In the B+ Tree implementation, the hash value was defined as key.hashcode().
Deployment cost of each contract (after performing jar optimization steps) is as follows:
| HashMap Type | Energy Used |
|---|---|
| B+ Tree | 744464 |
| Separate Chaining | 476879 |
| Open Addressing | 473468 |
For the put operation, two cases are evaluated:
1- Inserting 1000 sequential keys starting from 1.
2- Inserting 1000 keys, all of which collide with a hash value of 1.
The following charts demonstrate the energy consumed for the nth operation. The fee associated with each transaction also includes the cost for object graph serialization and deserialization, growing linearly with the map size.
NOTE: The values corresponding to multiples of 12 include a map resizing cost for the Open Addressing and Separate Chaining implementations. As an example, 768 was included in the charts.
Difference in energy consumption is also observable when the HashMap is defined as a local variable. For this test, one transaction defines the map and inserts multiple keys into it by calling the method below, thus avoiding the graph serialization and deserialization costs.
@Callable
public static void put(int count) {
AionMap<Integer, String> map = new AionMap<>();
for(int i = 0; i < count; i++) {
map.put(i, "STRING");
}
}
A similar method can be used to insert multiple entries with colliding key hash values.
For this test, key-value pairs are first inserted into the maps in a manner identical to the Put test. Since inserting a large amount of entries with colliding key hash values in Open Addressing implementation runs out of energy, it is not considered for this test.
For this test, sequential key-value pairs are first inserted into the maps in a manner identical to the Put test.
Based on the experiments, Separate Chaining has a better deployment and execution energy consumption than the other algorithms. This is especially true if the required size of the map is known in advance, and rehashing is thus avoided.
For more information refer to AionMapEnergyTest.