Attempting to understand the hashmap data structure

Question

I am working on a homework assignment that deals with constructing a hashmap data structure, and I'm not understanding a line of code that was given to us. In the program, a variable is initiated as follows:

private Map<K,V>[] buckets;

I know what the concept of buckets are when used in a hashmap, but how can I use a map array to create buckets? When I look at this code, it seems as though I need to create an array of hashmaps, but that doesn't make sense at all.

If you need any more information, just let me know.

Any help is greatly appreciated.

Below is the code that was provided.

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;
}

}

Answer 1

Hard to say precisely without seeing the wider code base, but from the information given I suspect that "Map" in this context really means "MapEntry" or something similar and that the map entries represent key/value pairs.

Remember, hashmap buckets need to contain both keys and values so that it is possible to distinguish between entries that have different keys but the same hash value.

Note that map entries in Java are normally expected to conform to the Map.Entry interface. If the "Map" class being used in your case supports this interface then that's a pretty good clue that it is playing this role :-)

Of course, another possibility is that they are actually hashmaps that represent the contents of each bucket. But that seems very odd for two reasons:

• There's no benefit of using a hashmap within a single bucket since you already know they have the same hashcode
• If you already have a hashmap implementation, it would be strange to use it to reimplement another hashmap.

I guess it's also possible that the Maps are a different kind of map (red black tree maybe?) but again that would be odd - usually the bucket implementation would use an array or a linked list rather than a heavyweight map data structure.

Update (after code was posted)

From the code now posted, it seems clear that the intention is one of the last two options, i.e. to implement the hashmap using another map structure to represent the contents for each bucket. Seems odd for the reasons given above, but I think it's reasonably clear from the template code that this is what is intended.

Answer 2

Here is an array of HashMaps used to demo how a 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=}