Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > HashMap problem: insert with hash code retrieve by index

Reply
Thread Tools

HashMap problem: insert with hash code retrieve by index

 
 
Royan
Guest
Posts: n/a
 
      04-27-2008
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?
 
Reply With Quote
 
 
 
 
Owen Jacobson
Guest
Posts: n/a
 
      04-27-2008
On Apr 27, 4:50*pm, Royan <(E-Mail Removed)> wrote:
> 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.
 
Reply With Quote
 
 
 
 
Patricia Shanahan
Guest
Posts: n/a
 
      04-27-2008
Royan wrote:
> 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
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      04-28-2008
On Sun, 27 Apr 2008 13:50:59 -0700 (PDT), Royan <(E-Mail Removed)>
wrote, quoted or indirectly quoted someone who said :

>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.
--

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
 
Reply With Quote
 
Royan
Guest
Posts: n/a
 
      04-28-2008
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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
reuse HashMap$Entry (or HashMap in total) to avoid millions of allocations Vince Darley Java 4 03-02-2010 07:48 AM
java.util.Properties extending from HashMap<Object, Object> insteadof HashMap<String, String> Rakesh Java 10 04-08-2008 04:22 AM
sorting index-15, index-9, index-110 "the human way"? Tomasz Chmielewski Perl Misc 4 03-04-2008 05:01 PM
In 'HashMap.put', "if (e.hash == hash && eq(k, e.key))" ? Red Orchid Java 3 01-30-2006 07:04 PM



Advertisments