<The previous article in this series | The table of contents of this series | The next article in this series>
We Created a Navigable and Elements-Insertable Linked Hash Map
About: Java Programming Language
The Use of Our Navigable and Elements-Insertable Linked Hash Map
Here are -Hypothesizer and -Rebutter sitting in front of a computer screen in a room on a brook among some mountains on the Bias planet.
This is something I encountered while we created the spread sheet cell editor: I couldn't find any navigable and elements-insertable linked hash map in the Java standard library.
What do you mean by 'navigable'?
I don't know whether that term is appropriate for what I mean, but I couldn't find any more appropriate term.
Anyway, what do you mean by it?
I mean that we can get the first element and the last element, and can get the preceding and the following element of any specified element, efficiently.
Can't we do those things with the standard 'LinkedHashMap'?
We can't. Although it remembers the order of the elements, it doesn't provide such features.
Ah, so, we can enjoy the benefit of the order of the elements just for iterating the elements from the first element: we can't directly jump to the following element from a specified element.
In short, 'LinkedHashMap' isn't a linked list: it's just a map that preserves the insertion order of the elements internally.
Do you want to specify an element by the key?
Yes. In fact, in the case of the spread sheet cell editor, we don't need values, but only keys.
So, you can use a Set instead of a Map.
Actually, yes, but that isn't any issue here: we can't use 'LinkedHashSet' on the same reason with 'LinkedHashMap'. We are talking about Map because it is of wider application: we can use a Map as a Set, ignoring values.
But if we don't need key-value pairs, can't we use 'LinkedList' instead?
Ah, as far as only features are concerned, we can: 'LinkedList' allows us to get the following element of a specified element like this, where 'l_linkedList' is the 'LinkedList' instance and 'l_specifiedElement' is the specified element.
l_searchedElement = l_linkedList.get (l_linkedList.indexOf (l_specifiedElement) + 1);
However, the processing isn't efficient: internally, it iterates the elements from the first element to find the specified element.
Hmm, isn't there significant demand for a 'navigable' linked hash map? I mean, is that the reason why the standard Java library doesn't have any 'navigable' linked hash map?
Probably, there isn't much demand, but is some, for there is such a class, 'org.apache.commons.collections4.map.LinkedMap', in Apache commons.
. . . Then, why don't we just use that one?
We could, but I felt a reluctance to introduce the whole Jar just for a single class, especially, when that single class doesn't seem to be very difficult to implement.
Well, . . . that seems a difficult decision.
Besides, we also have to be able to insert elements before any specified element.
Ah, with the standard 'LinkedHashMap', elements are always added at the tail. How about with 'LinkedMap' of Apache commons?
It seems to be the same.
I think, there may be another class that has features we want, in Apache commons.
Well, . . .
-Hypothesizer searches the API document of Apache commons on the internet.
Is this the one?
What is 'this'?
'org.apache.commons.collections4.map.ListOrderedMap'.
-Rebutter scans the Javadoc page of the class.
Well, at least this seems to have methods we need.
But is this efficient? I don't know.
In the first place, where did you want to use your navigable and elements-insertable hash map in the cell editor?
To set the tab order of Swing components on the cell editor frame, we have to implement 'getComponentBefore' and 'getComponentAfter' methods of 'java.awt.FocusTraversalPolicy', each of which receives a Swing component, and returns a Swing component that will receive the focus next. I wanted to specify the tab order in a navigable and elements-insertable hash map.
So that you can get the preceding or the following Swing component of the Swing component passed as the argument?
Yes.
Why do you have to insert elements before a specified element?
Because I wanted to make the cell editor frame a sub class of a more generic editor frame. The generic editor frame has Swing components such as a search-a-specified-phrase button, and the cell editor has additional cell-editor-specific Swing components such as a go-to-the-left-cell button. We want to specify the tab order in the generic editor frame, and insert some Swing components before a certain Swing component in the tab order, in the cell editor frame.
Anyway, your Swing components aren't so many as using 'LinkedList' would have any perceivable impact on performance, are they?
Well, actually, . . . they aren't. Practically, there will be no problem in using 'LinkedList' in that case. But, you know, it seems ridiculous to have to iterate from the first element every time. Besides, this isn't the first time I felt a need for a navigable and elements-insertable linked hash map. So, I thought, "Why don't I create one this time?"
Well, I don't say there is a reason why you shouldn't.
The Design of Our Navigable and Elements-Insertable Linked Hash Map
The same with the previous scene.
So, what's your design?
It's easy as I said. I just need a hash map instance whose value isn't just a value, but an object that has a value, the key of the preceding element, and the key of the following element. We can jump to a specified element by the key because that's a hash map, and can jump to the preceding element or the following element.
So, that hash map instance isn't a 'LinkedHashMap' instance.
We don't need 'LinkedHashMap' because anyway we couldn't use the order of elements stored in the 'LinkedHashMap' instance: we have to insert elements at arbitrary positions.
So, we create entry sets ourselves, based on the preceding keys and the following keys links.
Yes. And of course, we have to maintain the links as elements are put into our map instances, whose logic is the same with in a usual linked list.
Will we extend the 'HashMap' class?
No. That doesn't seem to work: we want to create 'NavigableLinkedHashMap <T, U>', but we can't extend 'HashMap <T, U>' because we use 'HashMap <T, ValueAndLinks <U, T>>', where 'ValueAndLinks' is the class that has the value, the preceding key, and the following key. We will have to implement the 'java.util.Map' interface. The 'HashMap' instance will be a member of our map.
So, we will wrap the 'HashMap' instance.
Yes.
The Implementation of Our Navigable and Elements-Insertable Linked Hash Map
The same with the previous scene.
This is the whole code of our navigable and elements-insertable linked hash map.
package thebiasplanet.coreutilities.collections;
import java.util.AbstractMap;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
public class NavigableLinkedHashMap <T, U> implements Map <T, U> {
private HashMap <T, ValueAndLinks <T, U>> i_keyToValueAndLinksHashMap;
private T i_firstKey;
private T i_lastKey;
private class ValueAndLinks <T, U> {
U i_value;
T i_previousKey;
T i_nextKey;
public ValueAndLinks (U a_value, T a_previousKey, T a_nextKey) {
i_value = a_value;
i_previousKey = a_previousKey;
i_nextKey = a_nextKey;
}
public U getValue () {
return i_value;
}
public void setValue (U a_value) {
i_value = a_value;
}
public T getPreviousKey () {
return i_previousKey;
}
public void setPreviousKey (T a_previousKey) {
i_previousKey = a_previousKey;
}
public T getNextKey () {
return i_nextKey;
}
public void setNextKey (T a_nextKey) {
i_nextKey = a_nextKey;
}
}
public NavigableLinkedHashMap () {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> ();
initialize ();
}
public NavigableLinkedHashMap (int a_initialCapacity) {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> (a_initialCapacity);
initialize ();
}
public NavigableLinkedHashMap (int a_initialCapacity, float a_loadFactor) {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> (a_initialCapacity, a_loadFactor);
initialize ();
}
public NavigableLinkedHashMap (Map <? extends T,? extends U> a_map) {
i_keyToValueAndLinksHashMap = new HashMap <T, ValueAndLinks <T, U>> (a_map.size ());
initialize ();
putAll (a_map);
}
private void initialize () {
i_firstKey = null;
i_lastKey = null;
}
@Override
public boolean containsKey (Object a_key) {
return i_keyToValueAndLinksHashMap.containsKey (a_key);
}
@Override
public boolean containsValue (Object a_value) {
for (Map.Entry <T, ValueAndLinks <T, U>> l_keyToValueAndLinksHashMapEntry: i_keyToValueAndLinksHashMap.entrySet ()) {
U l_value = l_keyToValueAndLinksHashMapEntry.getValue ().getValue ();
return (a_value == null ? l_value == null : a_value.equals (l_value));
}
return false;
}
@Override
public U get (Object a_key) {
return i_keyToValueAndLinksHashMap.get (a_key).getValue ();
}
@Override
public int hashCode () {
return i_keyToValueAndLinksHashMap.hashCode ();
}
@Override
public boolean isEmpty () {
return i_keyToValueAndLinksHashMap.isEmpty ();
}
@Override
public Set <T> keySet () {
LinkedHashSet <T> l_keys = new LinkedHashSet <T> ();
for (T l_key = i_firstKey, l_nexyKey = null; l_key != null; l_key = l_nexyKey) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (l_key);
l_keys.add (l_key);
l_nexyKey = l_valueAndLinks.getNextKey ();
}
return l_keys;
}
@Override
public U put (T a_key, U a_value) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
U l_value = l_valueAndLinks.getValue ();
l_valueAndLinks.setValue (a_value);
return l_value;
}
else {
l_valueAndLinks = new ValueAndLinks <T, U> (a_value, i_lastKey, null);
i_keyToValueAndLinksHashMap.put (a_key, l_valueAndLinks);
T l_previousKey = l_valueAndLinks.getPreviousKey ();
if (l_previousKey != null) {
i_keyToValueAndLinksHashMap.get (l_previousKey).setNextKey (a_key);
}
else {
i_firstKey = a_key;
}
i_lastKey = a_key;
return null;
}
}
public U putBefore (T a_insertedPositionKey, T a_key, U a_value) {
ValueAndLinks <T, U> l_existingValueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_existingValueAndLinks != null) {
return null;
}
else {
ValueAndLinks <T, U> l_insertedPositionValueAndLinks = i_keyToValueAndLinksHashMap.get (a_insertedPositionKey);
if (l_insertedPositionValueAndLinks == null) {
return null;
}
else {
T l_previousKeyOfInsertedPosition = l_insertedPositionValueAndLinks.getPreviousKey ();
ValueAndLinks <T, U> l_valueAndLinks = new ValueAndLinks <T, U> (a_value, l_previousKeyOfInsertedPosition, a_insertedPositionKey);
i_keyToValueAndLinksHashMap.put (a_key, l_valueAndLinks);
if (l_previousKeyOfInsertedPosition != null) {
i_keyToValueAndLinksHashMap.get (l_previousKeyOfInsertedPosition).setNextKey (a_key);
}
else {
i_firstKey = a_key;
}
l_insertedPositionValueAndLinks.setPreviousKey (a_key);
return l_insertedPositionValueAndLinks.getValue ();
}
}
}
@Override
public void putAll (Map <? extends T,? extends U> a_map) {
for (Map.Entry <? extends T,? extends U> l_mapEntry: a_map.entrySet ()) {
put (l_mapEntry.getKey (), l_mapEntry.getValue ());
}
}
@Override
public U remove(Object a_key) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
i_keyToValueAndLinksHashMap.remove (a_key);
T l_previousKey = l_valueAndLinks.getPreviousKey ();
T l_nextKey = l_valueAndLinks.getNextKey ();
if (l_previousKey != null) {
i_keyToValueAndLinksHashMap.get (l_previousKey).setNextKey (l_nextKey);
}
else {
i_firstKey = l_nextKey;
}
if (l_nextKey != null) {
i_keyToValueAndLinksHashMap.get (l_nextKey).setPreviousKey (l_previousKey);
}
else {
i_lastKey = l_previousKey;
}
return l_valueAndLinks.getValue ();
}
else {
return null;
}
}
@Override
public void clear () {
i_keyToValueAndLinksHashMap.clear ();
i_firstKey = null;
i_lastKey = null;
}
@Override
public Set <Map.Entry <T, U>> entrySet () {
LinkedHashSet <Map.Entry <T, U>> l_keyToValueEntries = new LinkedHashSet <Map.Entry <T, U>> ();
for (T l_key = i_firstKey, l_nexyKey = null; l_key != null; l_key = l_nexyKey) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (l_key);
l_keyToValueEntries.add (new AbstractMap.SimpleEntry <T, U> (l_key, l_valueAndLinks.getValue ()));
l_nexyKey = l_valueAndLinks.getNextKey ();
}
return l_keyToValueEntries;
}
@Override
public Collection <U> values () {
LinkedHashSet <U> l_values = new LinkedHashSet <U> ();
for (T l_key = i_firstKey, l_nexyKey = null; l_key != null; l_key = l_nexyKey) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (l_key);
l_values.add (l_valueAndLinks.getValue ());
l_nexyKey = l_valueAndLinks.getNextKey ();
}
return l_values;
}
@Override
public boolean equals (Object a_object) {
if (a_object == null || a_object instanceof Map) {
return false;
}
return entrySet ().equals ( ( (Map) a_object).entrySet ());
}
@Override
public int size () {
return i_keyToValueAndLinksHashMap.size ();
}
public T getPreviousKey (T a_key) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
return l_valueAndLinks.getPreviousKey ();
}
else {
return null;
}
}
public T getNextKey (T a_key) {
ValueAndLinks <T, U> l_valueAndLinks = i_keyToValueAndLinksHashMap.get (a_key);
if (l_valueAndLinks != null) {
return l_valueAndLinks.getNextKey ();
}
else {
return null;
}
}
public T getFirstKey () {
return i_firstKey;
}
public T getLastKey () {
return i_lastKey;
}
}
Ah-ha, certainly, that isn't a big job.
The class is included in this zip file. How to use our zip files is described here.
. . . And?
And what?
Shouldn't we at least test whether our navigable and elements-insertable linked hash map has some advantages in performance? I mean, it would be meaningless if there was none . . .
Well, honestly, I didn't doubt about its having at least some advantages, if not much, considering the mechanisms.
Well, I guess there would be some, but . . .
OK. We will do some tests.
-Hypothesizer writes three classes in the 'coreUtilitiesTestToDisclose' project, taking some time.
. . . . . . . . . zzz
All right. This is the test class for our navigable and elements-insertable linked hash map.
package test.navigablelinkedhashmaptest1;
import java.util.Map;
import thebiasplanet.coreutilities.collections.NavigableLinkedHashMap;
public class Test1Test {
private Test1Test () {
}
public static void main (String [] p_arguments) throws Exception {
int l_numberOfElements = 10000;
int l_mode = 0;
if (p_arguments.length > 0) {
l_numberOfElements = Integer.valueOf (p_arguments [0]);
}
if (p_arguments.length > 1) {
l_mode = Integer.valueOf (p_arguments [1]);
}
Test1Test.test (l_numberOfElements, l_mode);
}
// a_mode: 0 -> without dummy processing, 1 -> with dummy processing, 2 -> show some intermediate results without dummy processing
public static void test (int a_numberOfElements, int a_mode) {
long l_nanoTimeForInsertionStart = -1;
long l_nanoTimeForInsertionStop = -1;
long l_nanoTimeForInsertionAccumulation = 0;
long l_nanoTimeForSearchStart = -1;
long l_nanoTimeForSearchStop = -1;
long l_nanoTimeForIterationStart = -1;
long l_nanoTimeForIterationStop = -1;
int l_power = -1;
NavigableLinkedHashMap <Integer, String> l_navigableLinkedHashMap = new NavigableLinkedHashMap <Integer, String> (a_numberOfElements);
Integer l_lastElement = null;
Integer l_currentElement = null;
Integer l_searchedElement = null;
l_power = 1;
System.out.println ("#For NavigableLinkedHashMap Beginning");
System.out.println ("#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)");
l_nanoTimeForInsertionStart = System.nanoTime ();
l_nanoTimeForInsertionAccumulation = 0;
for (int l_elementIndex = 0; l_elementIndex < a_numberOfElements; l_elementIndex ++) {
l_currentElement = Integer.valueOf (l_elementIndex);
if (l_lastElement != null) {
l_navigableLinkedHashMap.putBefore (((l_elementIndex % 2) == 0) ? l_navigableLinkedHashMap.getNextKey (l_lastElement) : l_lastElement, l_currentElement, "");
}
else {
l_navigableLinkedHashMap.put (l_currentElement , "");
}
l_lastElement = l_currentElement;
// Dummy Processing BEGINNING
if (a_mode == 1 && l_elementIndex == 1) {
l_nanoTimeForInsertionStop = System.nanoTime ();
l_nanoTimeForInsertionAccumulation += l_nanoTimeForInsertionStop - l_nanoTimeForInsertionStart;
l_searchedElement = l_navigableLinkedHashMap.getNextKey (l_lastElement);
for (Map.Entry <Integer, String> l_navigableLinkedHashMapEntry: l_navigableLinkedHashMap.entrySet ()) {
Integer l_element = l_navigableLinkedHashMapEntry.getKey ();
}
l_nanoTimeForInsertionStart = System.nanoTime ();
}
// Dummy Processing END
if (l_elementIndex + 1 == Math.pow (10, l_power)) {
l_nanoTimeForInsertionStop = System.nanoTime ();
l_nanoTimeForInsertionAccumulation += l_nanoTimeForInsertionStop - l_nanoTimeForInsertionStart;
l_nanoTimeForSearchStart = System.nanoTime ();
l_searchedElement = l_navigableLinkedHashMap.getNextKey (l_lastElement);
if (a_mode == 2) {
System.out.println (String.format ("#Searched Element: %d", l_searchedElement));
}
l_nanoTimeForSearchStop = System.nanoTime ();
l_nanoTimeForIterationStart = System.nanoTime ();
for (Map.Entry <Integer, String> l_navigableLinkedHashMapEntry: l_navigableLinkedHashMap.entrySet ()) {
Integer l_element = l_navigableLinkedHashMapEntry.getKey ();
if (a_mode == 2 && l_power == 2) {
System.out.println (String.format ("#Iterated Element: %d", l_element));
}
}
l_nanoTimeForIterationStop = System.nanoTime ();
System.out.println (String.format ("# %,9d: %,18d; %,16d; %,18d", l_elementIndex + 1, l_nanoTimeForInsertionAccumulation, l_nanoTimeForSearchStop - l_nanoTimeForSearchStart, l_nanoTimeForIterationStop - l_nanoTimeForIterationStart));
l_nanoTimeForInsertionStart = System.nanoTime ();
l_power ++;
}
}
System.out.println ("#For NavigableLinkedHashMap End");
}
}
Of course, I also created one for 'LinkedList', and in fact, also for 'ListOrderedMap', but will refrain from showing them here because the logics are almost the same.
-Hypothesizer opens a terminal, change the current directory to the 'coreUtilitiesTestToDisclose' directory, and executes these commands.
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test1Test" -PCOMMAND_LINE_ARGUMENTS="1000000 0"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test2Test" -PCOMMAND_LINE_ARGUMENTS="100000 0"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test3Test" -PCOMMAND_LINE_ARGUMENTS="100000 0"
The results are these.
#For NavigableLinkedHashMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 23,149,950; 4,906; 6,691,418
# 100: 27,823,886; 956; 4,523,059
# 1,000: 57,166,916; 1,005; 17,431,587
# 10,000: 98,915,977; 380; 55,901,657
# 100,000: 401,701,939; 57,463; 339,302,036
# 1,000,000: 1,847,431,862; 54,360; 1,391,781,924
#For NavigableLinkedHashMap End
#For LinkedList Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 673,338; 32,917; 798,186
# 100: 2,880,055; 12,040; 78,205
# 1,000: 36,506,260; 23,692; 5,656,543
# 10,000: 1,047,642,813; 260,234; 6,519,878
# 100,000: 128,732,712,283; 2,437,329; 27,707,494
# 1,000,000: -; -; -
#For LinkedList End
#For ListOrderedMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 7,039,154; 107,793; 58,504,655
# 100: 10,158,446; 10,332; 856,906
# 1,000: 57,747,306; 19,041; 15,046,638
# 10,000: 1,685,974,232; 165,994; 20,261,828
# 100,000: 88,471,135,958; 601,450; 39,563,050
# 1,000,000: -; -; -
#For ListOrderedMap End
zzzzzz . . .
I said, results are these!
Huh? . . . What is this?
The results!
Of course, I know. . . . I asked what each of these numbers means.
I inserted a certain number of elements into a collection instance (of our navigable and elements-insertable linked hash map, 'LinkedList', or 'ListOrderedMap') with each element inserted in front of or after the lastly-inserted element alternately.
Um? What is your intention?
My intention is always inserting the new element nearly at the middle of the existing list. You know, inserting at the head or the tail would be meaningless as our test: it's obvious that elements can be efficiently added at the head or the tail of the 'LinkedList' instance.
Of course.
When the number of the elements became 10, 100, 1,000, etc, I outputted the number of the elements and the time that had been spent in inserting the elements so far. And then, I also got the following element of the lastly-inserted element (meaning an element nearly at the middle) from the collection instance, and outputted the time of doing so. And then, I also iterated through all the elements of the collection instance, and outputted the time of doing so.
So, you did them at each time when the number of the elements became 10 to the power of any natural number?
Yes. So, in short, in the table of 'NavigableLinkedHashMap' (which is our navigable and elements-insertable linked hash map) above, the third row means that 57,166,916 nanoseconds took in inserting 1,000 elements, 1,005 nanoseconds took in getting an element from 1,000 elements, and 17,431,587 nanoseconds took in iterating through 1,000 elements.
Your explanation doesn't seem particularly 'short', but I understand what you mean.
-Rebutter sees through the 3 tables of numbers, taking a while.
Hmm, . . . interesting.
Insertions for 'LinkedList' and 'ListOrderedMap' are faster when the numbers of the elements are small, but become unbearably slower when the numbers of the elements become bigger.
In fact, that's the reason we didn't do 1,000,000 elements tests for them: they would take too much time.
Search times of 'NavigableLinkedHashMap' are smaller, as expected, but the change according to the numbers of the elements is something I couldn't expect. Why are that decrease to 380 and the sudden increase to 57,463, but not increasing at 1,000,000 elements?
Honestly, I have no idea.
I guess, those numbers aren't very stable from test execution to test execution.
Certainly, they aren't, but that tendency is fairly stable.
And I notice that iterations of 'NavigableLinkedHashMap' are slower than the other two. Why is that?
Well, there is a difference in that 'NavigableLinkedHashMap' has to create a map entry set as a view: we can't let the iterator iterate through the elements as they are in the map instance.
I guess there is, but 'NavigableLinkedHashMap' is also slower than 'ListOrderedMap'.
Yes. . . . Maybe just, our code of 'entrySet' method is too crude.
And I wonder what is the implementation principle of 'ListOrderedMap'.
According to the search times, it doesn't seem to be hash-based. The tendency resembles more to 'LinkedList' than to our map, but there are certain differences.
And why are the search times and the iteration times for 10 elements such unreasonably long, regardless of the collection types?
Ah, I don't know the fundamental reason, but that isn't because of the number of elements, but because they are the first measurements. In fact, as we execute tests in another mode like these, those anomalies disappear.
-Hypothesizer executes the commands below.
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test1Test" -PCOMMAND_LINE_ARGUMENTS="1000000 1"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test2Test" -PCOMMAND_LINE_ARGUMENTS="100000 1"
gradle run -PMAIN_CLASS_NAME="test.navigablelinkedhashmaptest1.Test3Test" -PCOMMAND_LINE_ARGUMENTS="100000 1"
#For NavigableLinkedHashMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 28,520,467; 2,908; 156,256
# 100: 33,321,037; 797; 2,413,758
# 1,000: 38,163,177; 1,065; 13,511,453
# 10,000: 89,912,506; 391; 30,831,210
# 100,000: 395,634,986; 62,369; 234,624,658
# 1,000,000: 1,879,539,755; 57,196; 1,385,221,677
#For NavigableLinkedHashMap End
#For LinkedList Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 647,509; 3,608; 12,280
# 100: 2,723,686; 9,707; 76,147
# 1,000: 63,961,605; 23,011; 7,731,741
# 10,000: 1,384,062,815; 259,357; 4,904,449
# 100,000: 132,988,500,832; 2,434,372; 28,290,306
# 1,000,000: -; -; -
#For LinkedList End
#For ListOrderedMap Beginning
#Elements : Insertion for (ns); Search from (ns); Iteration for (ns)
# 10: 510,002; 5,851; 32,134
# 100: 3,148,831; 8,390; 2,031,163
# 1,000: 49,244,310; 16,848; 15,572,011
# 10,000: 920,952,896; 168,168; 8,021,630
# 100,000: 82,659,823,277; 655,516; 41,154,981
# 1,000,000: -; -; -
#For ListOrderedMap End
Um? The anomaly of the search time of 'NavigableLinkedHashMap' doesn't look to have disappeared, to me . . .
No . . ., but other anomalies have disappeared.
Why not, only of the search time of 'NavigableLinkedHashMap'?
I don't know.
What did you do in the new mode?
I just did the search and the iteration when the number of elements is 2, secretly.
Hmm, so, the first search and the first iteration takes longer time, somehow . . .
Honestly, I don't know the underlying mechanism . . .
Anyway, I included those test codes in the zip file, but 'Test3Test' is being disabled by its source file being renamed. You know, as I didn't include the Apache commons Jar file in the zip file, otherwise, the project won't be compiled successfully. We can enable it by downloading the Apache commons Jar file, registering the Jar file in 'OTHER_CLASSES_PATHS' in the project-specific Gradle built script or Ant build file, and restoring the 'Test3Test' source file name.
- Oracle and/or its affiliates. (2017). Overview (Java Platform SE 8). Retrieved from https://docs.oracle.com/javase/8/docs/api/
- The Apache Software Foundation. (2017). Overview (Apache Commons Collections 4.2-SNAPSHOT API). Retrieved from https://commons.apache.org/proper/commons-collections/apidocs/
<The previous article in this series | The table of contents of this series | The next article in this series>
