Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

about hashmap implementation of arraylist

 
Sekhar Chand
Ranch Hand
Posts: 73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 10336
Eclipse IDE Hibernate Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Not an advanced question. Moving...
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 125
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:


J
 
Devesh H Rao
Ranch Hand
Posts: 687
Hibernate jQuery Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Devesh H Rao
Ranch Hand
Posts: 687
Hibernate jQuery Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:


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
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The solutions would only work till the time we have a unique key. Uniqueness of the key should also be checked.
 
Anupam Sinha
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 201
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Use a multi dimensional array
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic