HashMap problem: insert with hash code retrieve by index

Discussion in 'Java' started by Royan, Apr 27, 2008.

  1. Royan

    Royan Guest

    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?
     
    Royan, Apr 27, 2008
    #1
    1. Advertising

  2. On Apr 27, 4:50 pm, 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);
    >     }
    >
    > }
    >
    > 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.
     
    Owen Jacobson, Apr 27, 2008
    #2
    1. Advertising

  3. 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
     
    Patricia Shanahan, Apr 28, 2008
    #3
  4. Royan

    Roedy Green Guest

    On Sun, 27 Apr 2008 13:50:59 -0700 (PDT), Royan <>
    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
     
    Roedy Green, Apr 28, 2008
    #4
  5. Royan

    Royan Guest

    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.
     
    Royan, Apr 28, 2008
    #5
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vince Darley
    Replies:
    4
    Views:
    4,551
    emilchacko
    Mar 2, 2010
  2. Red Orchid
    Replies:
    3
    Views:
    1,092
  3. Rakesh
    Replies:
    10
    Views:
    12,267
    Mike Schilling
    Apr 8, 2008
  4. rp
    Replies:
    1
    Views:
    587
    red floyd
    Nov 10, 2011
  5. Tomasz Chmielewski

    sorting index-15, index-9, index-110 "the human way"?

    Tomasz Chmielewski, Mar 4, 2008, in forum: Perl Misc
    Replies:
    4
    Views:
    357
    Tomasz Chmielewski
    Mar 4, 2008
Loading...

Share This Page