I have written two hash map implementations, one that stores Vertices and one that stores self implemented vectors of Edges. They are all fully functioning, however in my application they are quite slow and was hoping if anyone could point out how to improve their speed.
Vertex Hash Map
public class VertexHashMap
{
public double noofitems;
public Vertex[] data;
int resize;
public VertexHashMap(int initlen)
{
noofitems=0;
data=new Vertex[initlen];
this.resize = 67;
}
public void AddItem(Vertex value)
{
if ((noofitems/data.length) > 0.7)
{
resize();
}
int index=value.city % data.length;
boolean inserted = false;
int increment = 1;
do
{
if (data[index] == null) {
data[index]=value;
noofitems++;
inserted = true;
}
else {
index+= (increment<<4);
index = index % data.length;
}
} while (!inserted);
}
public Vertex GetValue(int key)
{
int index=key % data.length;
boolean found = false;
int increment = 1;
do
{
if (data[index].city == key)
return data[index];
else if (data[index] == null)
return null;
else {
index+= (increment<<4);
index = index % data.length;
}
} while (!found);
return null;
}
private void resize()
{
//long time = System.nanoTime();
Vertex[] newData = new Vertex[data.length * resize];
resize = 11;
for (Vertex oldMap1 : data) {
if (oldMap1 != null) {
int index = oldMap1.city % newData.length;
boolean inserted = false;
int increment = 1;
while (!inserted) {
if (newData[index] == null) {
newData[index] = oldMap1;
inserted = true;
} else {
index+= (increment<<4);
index = index % newData.length;
}
}
}
}
//System.out.println("Resizing hashmap took: " + ((System.nanoTime() - time)/1000000) + "ms");
data = newData;
}
public double getNumberOfItems()
{
return noofitems;
}
}
In my application, I call this method 215,000 times which takes (according to my timings) around 300ms.
public void AddVertex(final int vertexid, final int x, final int y)
{
allVertices.AddItem(new Vertex(vertexid, x, y));
}
Edge Hash Map
public class EdgeHashMap
{
private double noofitems, noitems;
public EdgeHashPair[] data;
int multiplier = 60;
public EdgeHashMap(int initlen)
{
noofitems=0;
noitems = 0;
data=new EdgeHashPair[initlen];
}
public void AddItem(Edge value)
{
if ((noofitems/data.length) > 0.7)
resize();
value.hashIndex=HashFunction(value.label);
int index = value.hashIndex % data.length;
int increment = 0;
boolean inserted = false;
do {
if (data[index] != null)
if (data[index].data.GetItem(0).label.compareTo(value.label) == 0) {
data[index].addItem(value);
inserted = true;
noitems++;
}
else {
increment+=1;
index+= (increment<<4);
index = index % data.length;
}
else {
data[index] = new EdgeHashPair();
data[index].addItem(value);
noofitems++;
inserted = true;
}
} while (!inserted);
}
private int HashFunction(String key)
{
//long time = System.nanoTime();
char[] t = key.toCharArray();
int a = 0;
for (int i=0; i<t.length; ++i)
a = ((a<<5) - a) + t[i];
//System.out.println("Hash Function took: " + ((System.nanoTime() - time)) + "ns");
return Math.abs(a);
}
public EdgeVector GetValue(String key)
{
int index=HashFunction(key);
int increment = 0;
index = index % data.length;
boolean found = false;
do
{
if (data[index] == null)
return null;
else if (data[index].data.GetItem(0).label.compareTo(key) == 0)
return data[index].data;
else {
increment+=1;
index+= (increment<<4);
index = index % data.length;
}
} while (!found);
return null;
}
private void resize()
{
//long time = System.nanoTime();
EdgeHashPair[] newMap = new EdgeHashPair[data.length * multiplier];
multiplier = 8;
for (EdgeHashPair oldMap1 : data)
{
if (oldMap1 != null) {
int index = oldMap1.data.GetItem(0).hashIndex;
int increment = 0;
index = index % newMap.length;
boolean inserted = false;
do {
if (newMap[index] == null) {
newMap[index] = oldMap1;
inserted = true;
}
else {
increment+=1;
index+= (increment<<4);
index = index % newMap.length;
}
} while (!inserted);
}
}
data = newMap;
//System.out.println("Edge Hashmap resizing took: " + ((System.nanoTime() - time)/1000000) +"ms");
}
In the application, I call this method around 260,000 times, however I only store around 110,000 Edge Vectors, as they each contain multiple Edges.
public void AddEdge(final String label, final int fromid, final int toid, final double distance, final boolean oneway, final int speedlimit)
{
currentRoad = new Edge(label, fromid, toid, distance, speedlimit, oneway);
allVertices.GetValue(fromid).addEdge(currentRoad);
allEdges.AddItem(currentRoad);
if (!oneway)
{
allVertices.GetValue(toid).addEdge(new Edge(label, toid, fromid, distance, speedlimit, oneway));
}
}
It takes roughly 700-1000ms to execute - I was expecting much less and I can't seem to make it quicker (it originally started at over 1000ms).
EdgeHashPair
public class EdgeHashPair
{
EdgeVector data;
public EdgeHashPair()
{
data = new EdgeVector(50);
}
public EdgeHashPair(int length)
{
data = new EdgeVector(length+10);
}
public void addItem(Edge item)
{
data.AddItem(item);
}
}
The EdgeVector and VertexVector are basic implementations of Vectors. They have methods such as AddItem, GetItem, DeleteItem etc.
If anyone could take a look and suggest some improvements that would be fantastic.
