1. The problem
Nobody likes lags. So for some (real time) applications like real time rendered 3D games it is nessessary to avoid memory allocations and garbage collection when beeing e.g. ingame as GC might block your game just when you do not need or want it.
Additionally there is no way to control garbage collection in standard JVMs.
When profiling your application with tools like Visual VM (http://visualvm.java.net) you will notice iterators very fast as one main cause for frequent garbage collection.
While you can work around creating iterators of ArrayList using simple old for loops like
//
ArrayList arrayList = new ArrayList();
arrayList.add("Blues");
arrayList.add("Rock ann Roll");
arrayList.add("Swing");
// avoids creating an iterator
for (int i = 0; i < 3; i++)
for (int j = 0; j < arrayList.size(); j++) {
String value = arrayList.get(j);
System.out.println(value);
}
// will create 3 iterators!
for (int i = 0; i < 3; i++)
for (String value : arrayList) {
System.out.println(value);
}
you simply can not work around looping over keys or values within a java.util.HashMap.
The following code will always create iterators on heap!
// create hash map
HashMap<string, string=""> hashMap = new HashMap<string, string="">();
hashMap.put("1", "Blues");
hashMap.put("2", "Rock and roll");
hashMap.put("3", "Swing");
// iterate values, will create 3 iterators!
for (int i = 0; i < 3; i++)
for (String value : hashMap.values()) {
System.out.println(value);
}
// iterate keys, will create 3 iterators!
for (int i = 0; i < 3; i++)
for (String key : hashMap.keySet()) {
System.out.println(key);
}
// iterate entries, will create 3 iterators!
for (int i = 0; i < 3; i++)
for (Map.Entry<string, string=""> entry : hashMap.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}2. The solution
As there is no way to avoid creating iterators in theses cases I just programmed an own unordered hash map which is set up to reuse a single values and key iterator.
There is one drawback as you can not do nesting with the same hash map iterator in it self which is rarely required.
Basically a hash map does some kind of partition based on a hash function (which is provided e.g. in String.hashCode(), …, Object.hashCode())
Here it is called buckets. Each bucket can contain several key value pairs.
The bucket is identified by the hash function of the key object. The key value pair is finally identified by Object.equals() in a bucket as a bucket can contain multiple key value pairs.
The number of buckets always equals the number of elements stored in a hash map.
In best case you would have N buckets for N elements and each bucket would contain a single key value pair.
In this case the complexity for put, get, remove would be O(1). With collisions (means multiple key value pairs in one bucket) complexity will have a little O(n) shadow.
package net.drewke.tdme.utils;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
/**
* Hashmap which keeps track of keys and values in a array list
* @author Andreas Drewke
*
* @param
* @param
*/
public class HashMap<K,V> {
/**
* Values Iterator
* @author Andreas Drewke
* @param
* @param
*/
public static class ValuesIterator<K,V> implements Iterator, Iterable {
private HashMap<K,V> hashMap;
private int bucketIdx;
private int keyValuePairIdx;
private int elementIdx;
/**
* Public constructor
* @param hashmap
*/
public ValuesIterator(HashMap<K,V> hashmap) {
this.hashMap = hashmap;
reset();
}
/**
* Reset
* @return this iterator
*/
public Iterator reset() {
this.bucketIdx = 0;
this.keyValuePairIdx = 0;
this.elementIdx = 0;
return this;
}
/*
* (non-Javadoc)
* @see java.lang.Iterable#iterator()
*/
public Iterator iterator() {
return reset();
}
/*
* (non-Javadoc)
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return elementIdx < hashMap.elements;
}
/*
* (non-Javadoc)
* @see java.util.Iterator#next()
*/
public V next() {
while (bucketIdx < hashMap.buckets.size()) {
ArrayList<Pair<K,V>> bucket = hashMap.buckets.get(bucketIdx);
if (keyValuePairIdx == bucket.size()) {
keyValuePairIdx = 0;
bucketIdx++;
} else {
Pair<K,V> keyValuePair = bucket.get(keyValuePairIdx++);
elementIdx++;
return keyValuePair.value;
}
}
return null;
}
}
/**
* Keys Iterator
* @author Andreas Drewke
* @param
* @param
*/
public static class KeysIterator<K,V> implements Iterator, Iterable {
private HashMap<K,V> hashMap;
private int bucketIdx;
private int keyValuePairIdx;
private int elementIdx;
/**
* Public constructor
* @param hashmap
*/
public KeysIterator(HashMap<K,V> hashmap) {
this.hashMap = hashmap;
reset();
}
/**
* Reset
* @return this iterator
*/
public Iterator reset() {
this.bucketIdx = 0;
this.keyValuePairIdx = 0;
this.elementIdx = 0;
return this;
}
/*
* (non-Javadoc)
* @see java.lang.Iterable#iterator()
*/
public Iterator iterator() {
return reset();
}
/*
* (non-Javadoc)
* @see java.util.Iterator#hasNext()
*/
public boolean hasNext() {
return elementIdx < hashMap.elements;
}
/*
* (non-Javadoc)
* @see java.util.Iterator#next()
*/
public K next() {
while (bucketIdx < hashMap.buckets.size()) {
ArrayList<Pair<K,V>> bucket = hashMap.buckets.get(bucketIdx);
if (keyValuePairIdx == bucket.size()) {
keyValuePairIdx = 0;
bucketIdx++;
} else {
Pair<K,V> keyValuePair = bucket.get(keyValuePairIdx++);
elementIdx++;
return keyValuePair.key;
}
}
return null;
}
}
/**
* @author Andreas Drewke
* @param
* @param
*/
private static class Pair<K,V> {
private K key;
private V value;
}
private int capacity = 256;
private int elements = 0;
private ArrayList<ArrayList<Pair<K,V>>> buckets = new ArrayList<ArrayList<Pair<K,V>>>();
private HashMap.ValuesIterator<K,V> valuesIterator = new ValuesIterator<K,V>(this);
private HashMap.KeysIterator<K,V> keysIterator = new KeysIterator<K,V>(this);
/**
* Public constructor
*/
public HashMap() {
for (int i = 0; i < capacity; i++) {
buckets.add(new ArrayList<Pair<K,V>>());
}
}
/**
* Clears this hash table
*/
public void clear() {
elements = 0;
for (int i = 0; i < capacity; i++) {
buckets.get(i).clear();
}
}
/**
* Grow hash map
*/
private void grow() {
// store old buckets
ArrayList<ArrayList<Pair<K,V>>> oldBuckets = buckets;
// create new buckets
buckets = new ArrayList<ArrayList<Pair<K,V>>>();
capacity*= 2;
elements = 0;
for (int i = 0; i < capacity; i++) {
buckets.add(new ArrayList<Pair<K,V>>());
}
// recreate bucket table
for (int i = 0; i < oldBuckets.size(); i++) {
ArrayList<Pair<K,V>> bucket = oldBuckets.get(i);
for (int j = 0; j < bucket.size(); j++) {
Pair<K,V> keyValuePair = bucket.get(j);
put(keyValuePair.key, keyValuePair.value);
}
}
}
/**
* Get the associated value of given object / key
*/
public V get(K key) {
ArrayList<Pair<K,V>> bucket = buckets.get(Math.abs(key.hashCode()) % capacity);
for (int i = 0; i < bucket.size(); i++) {
Pair<K,V> keyValuePair = bucket.get(i);
if (keyValuePair.key.equals(key)) return keyValuePair.value;
}
return null;
}
/**
* Removes associated value of given object / key
*/
public V remove(K key) {
ArrayList<Pair<K,V>> bucket = buckets.get(Math.abs(key.hashCode()) % capacity);
for (int i = 0; i < bucket.size(); i++) {
Pair<K,V> keyValuePair = bucket.get(i);
if (keyValuePair.key.equals(key)) {
bucket.remove(i);
elements--;
return keyValuePair.value;
}
}
return null;
}
/**
* Put given value with associated key into this hash map
*/
public V put(K key, V value) {
if (elements + 1 >= buckets.size()) grow();
V oldValue = remove(key);
ArrayList<Pair<K,V>> bucket = buckets.get(Math.abs(key.hashCode()) % capacity);
Pair<K,V> keyValuePair = new Pair<K,V>();
keyValuePair.key = key;
keyValuePair.value = value;
bucket.add(keyValuePair);
elements++;
return oldValue;
}
/**
* @return number of elements
*/
public int size() {
return elements;
}
/**
* @return Values Iterator
*/
public ValuesIterator<K,V> getValuesIterator() {
valuesIterator.reset();
return valuesIterator;
}
/**
* @return Keys Iterator
*/
public KeysIterator<K,V> getKeysIterator() {
keysIterator.reset();
return keysIterator;
}
/*
* (non-Javadoc)
* @see java.lang.Object#toString()
*/
public String toString() {
String string = new String();
for (int i = 0; i < buckets.size(); i++) {
ArrayList<Pair<K,V>> bucket = buckets.get(i);
for (int j = 0; j < bucket.size(); j++) {
Pair<K,V> keyValuePair = bucket.get(j);
if (string.length() > 0) string+=", ";
string+= keyValuePair.key + "=" + keyValuePair.value;
}
}
string ="HashMap[" + string + "]";
return string;
}
}
With the own hash map implementation you can iterate over values and keys while allocating no new iterators as they are reused:
// create hash map HashMap<string, string=""> hashMap = new HashMap<string, string="">(); hashMap.put("1", "Blues"); hashMap.put("2", "Rock and roll"); hashMap.put("3", "Swing"); // iterate values, will reuse iterator for (int i = 0; i < 3; i++) for (String value : hashMap.getValuesIterator()) { System.out.println(value); } // iterate over keys, will reuse iterator for (int i = 0; i < 3; i++) for (String key : hashMap.getKeysIterator()) { System.out.println(key); }