Re: HashMap problem: insert with hash code retrieve by index
"Royan" <romayankin@gmail.com> wrote in message
news:d734714a-b5d3-42c8-b5e5-2f44b8beadb5@34g2000hsh.googlegroups.com...
<snip code>
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?
Absolute indexes (especially continguous ones) are rarely used in hashing
because they become inconsistent when the table is expanded and because hash
tables work best when the table is not 100% full. Hash maps also must cope
with distinct keys that produce the same hash code and your example isn't
really compatible with that. Based on your previous post, I think you're
expecting hash codes to be unique--they're not. You must use special
algorithms for that http://en.wikipedia.org/wiki/Perfect_hash
I think what you're looking for is a way to assign index numbers to keys. I
don't think there's a Java class for that, although there's probably one
somewhere out there. You can add the keys and get back indexes for them
and then retrieve the keys by the indexes, but without searching. You can
use the following structure for that (this is in the style of your Foo
class).
public class Foo {
private List <String> keys = new ArrayList <String> ();
private Map<String,Integer> dataMap
= new HashMap<String,Integer>();
public String getValueAt(int idx) {
return keys.get(idx);
}
// This does not guard against duplicate keys. This can be
// combined with find so that duplicates simply return the
// existing index
public int addValue(String s) {
int idx = keys.size ();
keys.add(s);
dataMap.put(s,idx);
return idx;
}
// Returns -1 if item is not found
public int findValue (String s) {
Integer idxInteger = dataMap.get(s);
if (idxInteger == null) return -1;
return idxInteger.intValue();
}
}
This code does not need to deal with the hash codes at all. I did not
compile or test this--it's just to illustrate the concept.
Matt Humphrey http://www.iviz.com/