HashMap problem: insert with hash code retrieve by index

R

Royan

Lets say we have the following class

public class Foo {
private Map<Integer, String> dataMap = new HashMap<Integer,
String>();

public String getValueAt(int idx) {
// I wish I don't use for loop here ...
}

public void addValue(String s) {
String l = dataMap.put(getHashCode(s), s);
}
}

The problem is that I have to fill the map with values that are
absolutely inconsistent with each other, they are actually hash codes,
but when I call getValueAt method I need to get an element that would
be taken from Nth position.

Assume I have the following code

Foo f = new Foo();
f.addValue("qwerty");
f.addValue("12345");
// i know that the size of the HashMap is 2, so the following must be
fair
f.getValueAt(0); // OK
f.getValueAt(1); // OK
f.getValueAt(2); // ERROR - out of range


I do understand that the order of extraction in HashMap is unpredicted
- this is OK, but what is the best way to implement the functionality
that would help me extract elements from that map by an absolute index?
 
O

Owen Jacobson

Lets say we have the following class

public class Foo {
    private Map<Integer, String> dataMap = new HashMap<Integer,
String>();

    public String getValueAt(int idx) {
        // I wish I don't use for loop here ...
    }

    public void addValue(String s) {
        String l = dataMap.put(getHashCode(s), s);
    }

}

The problem is that I have to fill the map with values that are
absolutely inconsistent with each other, they are actually hash codes,
but when I call getValueAt method I need to get an element that would
be taken from Nth position.

Assume I have the following code

Foo f = new Foo();
f.addValue("qwerty");
f.addValue("12345");
// i know that the size of the HashMap is 2, so the following must be
fair
f.getValueAt(0); // OK
f.getValueAt(1); // OK
f.getValueAt(2); // ERROR - out of range

I do understand that the order of extraction in HashMap is unpredicted
- this is OK, but what is the best way to implement the functionality
that would help me extract elements from that map by an absolute index?

Do you have a good reason not to use ArrayList for this? You'd get
the same complexity without introducing a class that does nothing more
than make a hashmap look like a subset of the List interface.
 
P

Patricia Shanahan

Royan said:
Lets say we have the following class

public class Foo {
private Map<Integer, String> dataMap = new HashMap<Integer,
String>();

public String getValueAt(int idx) {
// I wish I don't use for loop here ...
}

public void addValue(String s) {
String l = dataMap.put(getHashCode(s), s);
}
}
....

I'm not sure I fully understand the problem, but often the easiest way
to get unusual functionality from the collections is to combine a couple
of them.

For example, a bidirectional map between String and int can be
implemented very simply using the combination of a
HashMap<String,Integer> and an ArrayList<String>. The ArrayList provides
a very efficient way to get the String associated with an index, and the
HashMap provides a way to get the index given a String.

Of course, all this can be hidden inside a class that provides the
access methods you need.

Patricia
 
R

Roedy Green

I call getValueAt method I need to get an element that would
be taken from Nth position.

You don't likely want a HashMap. You want an ArrayList with nulls for
the unused slots.

To use a HashMap, you would need some mechanism to assign slot numbers
uniquely. It would only make sense for very sparse array.
 
R

Royan

2Lew
Bear in mind that only *one* Integer of any given value can key the Map, and so if two Strings have the same
hashCode(), you'll lose one of them.


Thats OK, it would be worse if two different String's would have the
same hash code


public String put( String val )
{
return data.put( val.hashCode(), val );
}

This piece of code would be OK, if i was 100% sure that
String#hashCode would produce unique hash code for every two different
strings.





2Owen
Do you have a good reason not to use ArrayList for this? You'd get
the same complexity without introducing a class that does nothing more
than make a hashmap look like a subset of the List interface.

I'm bound to HashMap or perhaps Map implementation of some kind. I'll
explain. Imagine you have server and a dozen of remote clients that
operate (add/delete/edit/whatever) data on that server. Data is
represented by strings. All of those strings are unique there is no
way there can be a dup. When some remote clients connects to server
saying I want to edit "xxxxx" string it is actually sending hash code
of such string. If I use ArrayList there is no fast way to determine
which string client is searching for.



2Matt

I think you proposed the right solution for my problem. After reading
your thought, and comparing it with other suggestions I feel this is
what i'm going to do. However I believe that if I could afford
sequential indexing I would follow Owens advice and simply use
ArrayList, alas i can't afford this, because my remote clients contain
unsynchronized data, it might happen that one client may try to update
some string that has already been deleted. I must be 100% sure I'm
addressing the correct string and the unique string hash appears to be
the only way to do that.



2Patricia Your idea appears to be a development of Matts suggestion,
so I believe this is what I'm looking for.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top