about hashmap implementation of arraylist

[Sekhar Chand]

Hi,
when i faced interview , i was asked one question
how to implement HashMap functionality by using the ArrayList.
If any body knows the solution please let me know
Thanks and regards
Ratna Sekhar

[Paul Sturrock]

Not an advanced question. Moving...

[Stan James]

I think this means to write a class that works like Map but uses ArrayList internally. I was actually fool enough to do this with Vector my first week of Java because I hadn't thought to look in the API and find maps. What does a map have? Keys and values. How would you store a bunch of keys and a bunch of values to make these two methods work:

public Object get( key )
public void put( key, value )

[Minh Tran]

I guess you can. in ArrayList, index might be a key as in HashTable and using get(int index); will return the object

[Sekhar Chand]

Yeah you can use index in List as an Key in hashmap. But if they give any object, so we have to store that one also.
Here i got an idea , when ever you are writting your own put method, you have to use two array lists, in which one takes key and another takes value objects. So, the index of the one key and value pair will be the same. In get method , you will get a key, by taking that keys list and by iterating you can get the index of that key and by using the same index you can get the object from the another list(because the indexes of the key and value are same). So you can return that value from your get method.

But instead of this logic there is something, means using one or two method we can implement the Hasmap by using the list.
That i want,


if any body knows please let me know

Thanks and regards
Ratna sekhar

[Jeremy Botha]

personally, I think the easiest (and most inefficient way) to do this is to
use the hashcode of the key as the index to the value in the arrayList.

that is, something like this:

  class myMap {
     ArrayList al = new ArrayList(SOME_VERY_BIG_NUMBER);
 
     public void put(Object key, Object value) {
       al.insert(key.hashCode(), value);
     }
 
     public Object get(Object key) {
       al.get(key.hashCode());
     }
  } 

J

[Devesh H Rao]

  
 
        private ArrayList keyList = new ArrayList();
private ArrayList valueList = new ArrayList();

public void put(Object key, Object value){
keyList.add(key);
valueList.add(keyList.indexOf(key),value);
}

public Object get(Object key){
return valueList.get(keyList.indexOf(key));
}
 

[Devesh H Rao]

Originally posted by Jeremy Botha:
personally, I think the easiest (and most inefficient way) to do this is to
use the hashcode of the key as the index to the value in the arrayList.

that is, something like this:

  class myMap {
     ArrayList al = new ArrayList(SOME_VERY_BIG_NUMBER);
 
     public void put(Object key, Object value) {
       al.insert(key.hashCode(), value);
     }
 
     public Object get(Object key) {
       al.get(key.hashCode());
     }
  } 

J

ArrayList al = new ArrayList(SOME_VERY_BIG_NUMBER);

public void put(Object key, Object value) {
al.insert(key.hashCode(), value);
}


It actually translates to a veryyyyyyyyyyyyyyy big number....

A random object creation threw up these numbers

17523401
8567361
9584176
19972507
32942009
8222510
18581223
3526198
7699183
14285251
[ June 14, 2007: Message edited by: Devesh H Rao ]

[Anupam Sinha]

The solutions would only work till the time we have a unique key. Uniqueness of the key should also be checked.

[Anupam Sinha]

Infact Jeremy's solution would solve the uniqueness problem. The size of the arrayList should be 2*Integer.MAX_VALUE. Which isn't possible.
[ June 14, 2007: Message edited by: Anupam Sinha ]

[Minh Tran]

Originally posted by Sekhar Chand:

But instead of this logic there is something, means using one or two method we can implement the Hasmap by using the list.

Impossible to use it as standard JDK, please have a look at Java Collection Framework

You can inherit them for your own Collection

[Jay Dilla]

Use a multi dimensional array

[Stan James]

you have to use two array lists, in which one takes key and another takes value objects

Yeah, that's what I did before I found the Map interface. Then ... well, we don't have a smack self on forehead smiley.

Of course we have to ask if the original question of implementing hashmap required using hashes. This two-list approach would be fine if he said replace HashMap or implement Map, but there's no hash in sight.