Trying to understand the hashmap data structure
I'm working on a homework assignment that deals with building a hashmap data structure and I don't understand the line of code that was provided to us. In the program, the variable is started as follows:
private Map<K,V>[] buckets;
I know what the concept of buckets is when used in a hashmap, but how can I use an array of cards to create buckets? When I look at this code, it seems to me that I need to create an array of hash maps, but that doesn't make any sense.
If you need more information, just let me know.
Any help is greatly appreciated.
Below is the code.
package cs2321;
import net.datastructures.*;
public class HashMap<K, V> implements Map<K, V> {
private Map<K,V>[] buckets;
protected final int mDefaultHashSize = 1021;
/**
* Constructor that takes a hash size
* @param hashsize The number of buckets to initialize
* in the HashMap
*/
public HashMap(int hashsize){
// TODO: Be sure to initialize the bucket array
// using the hashsize given as the number of buckets
}
public HashMap(){
// TODO: Be sure to initialize the bucket array
// using the default hash size provided.
}
public Iterable<Entry<K, V>> entrySet() {
// TODO Auto-generated method stub
return null;
}
public V get(K key) throws InvalidKeyException {
// TODO Auto-generated method stub
return null;
}
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
public Iterable<K> keySet() {
// TODO Auto-generated method stub
return null;
}
public V put(K key, V value) throws InvalidKeyException {
// TODO Auto-generated method stub
return null;
}
public V remove(K key) throws InvalidKeyException {
// TODO Auto-generated method stub
return null;
}
public int size() {
// TODO Auto-generated method stub
return 0;
}
public Iterable<V> values() {
// TODO Auto-generated method stub
return null;
}
}
source to share
Here is the HashMaps array used to demonstrate how HashMap works. Study it and tell us how it works and why HashMaps are so widely used?
public class Test {
static private Map<String,String>[] buckets;
static int numberOfBuckets = 3;
static public void main(String...strings) {
buckets = new Map[numberOfBuckets];
for (int x=0; x!=numberOfBuckets; x++) {
buckets[x]=new HashMap<String,String>();
}
String s1 = "one ijsiji jdj i";
String s2 = "two ijs42i jdj i";
String s3 = "th3 ijsiji 42j i";
String s4 = "i42 ji jdj i";
buckets[(Math.abs(s1.hashCode()) % numberOfBuckets)].put(s1,"");
buckets[(Math.abs(s2.hashCode()) % numberOfBuckets)].put(s2,"");
buckets[(Math.abs(s3.hashCode()) % numberOfBuckets)].put(s3,"");
buckets[(Math.abs(s4.hashCode()) % numberOfBuckets)].put(s4,"");
for (int x=0; x!=numberOfBuckets; x++) {
System.out.println(buckets[x]);
}
}
}
Output
{two ijs42i jdj i=} {one ijsiji jdj i=, i42 ji jdj i=} {th3 ijsiji 42j i=}
source to share
It's hard to say for sure without seeing the broader code base, but from the information provided, I suspect that "Map" in this context does indeed mean "MapEntry" or something similar, and that the entries in the map represent key / value pairs .
Remember that the hashmap bucket must contain both keys and values so that you can distinguish between entries that have different keys but the same hash value.
Note that map entries in Java usually have to conform to the Map.Entry interface . If the class "Map" used in your case supports this interface, then it is pretty well known that it plays this role :-)
Another possibility, of course, is that they are actually hash maps that represent the contents of each bucket. But this seems very strange for two reasons:
- It is not possible to use a hashmap in the same bucket as you already know they have the same hashcode
- If you already have a hashmap implementation, it would be weird to use it to override another hashmap.
I also assume that Maps is a different kind of map (red ebony perhaps?), But again that would be strange - normally a bucket implementation would use an array or linked list rather than a heavyweight data structure.
Update (after posting the code)
From the code already posted, it seems clear that the intent is one of the last two, i.e. to implement a hashmap using a different map structure to represent the content for each bucket. Seems strange for the reasons given above, but I think it's pretty clear from the template code that this is what it is intended to do.
source to share