Java (basic) Multithreading with Hashmap issues

Question

I'm researching how to do Multithreading, mainly from this website: http://www.tutorialspoint.com/java/java_multithreading.htm

I'm trying to implement it into my own Hash Map Implementation. My thought is, when I re-size my hashmap I can multi thread so that while it adds in the entry to the larger hash map, I can use the other thread to re-hash the smaller hash map into the larger one.

My implementation of the Hash Map works correctly - however I'm struggling to get to grips with the Multithreading, so I was wondering if anyone could take a look at my code and see where I'm going wrong?

public class HashMap extends Thread
{
  private Thread t;
  private String threadName;
  private long noofitems;
  private HashPair[] data;
  HashPair[] newArray;

  private int copyCounter = 0;

  public HashMap(int initlen)
  {
    noofitems=0;
    data=new HashPair[initlen];
    threadName = "t1";
  }

  public void run()
  {
      for (int i = 0; i < 5 && copyCounter < noofitems; i++)
            {
               if (data[copyCounter] != null)
               {
                    int test1=HashFunction(data[copyCounter].key);
//                    newArray[test1] = data[copyCounter];                     
                    int index = test1 % newArray.length;
                    boolean tempInserted = false;
                    int tempIncrement = 1;
                    while (!tempInserted)
                    {            
                        if (newArray[index] == null)
                        {
                            newArray[index] = data[copyCounter];
                            noofitems++;
                            System.out.println("Thread Added");
                            tempInserted = true;
                        }

                    }
                    copyCounter++;
               }
               else
               {
                   copyCounter++;
               }                               
            }
  }

  //make data point to newArray
  //null newArray
  //if copyCounter >= data.length { do null thing}
  public void AddItem(String key, String value)
  {
//    System.out.println("Adding: "+key+" "+value);
    int index=HashFunction(key);
    //++hits[index%data.length];

    HashPair item=new HashPair(key, value);

    // Task 3: Check load factor here and resize if over 0.7
        if ((noofitems/(float)data.length) > 0.7 && newArray == null)
        {
            newArray = new HashPair[data.length*2];   
            //copyCounter = 0;
        }    


    // Task 2 Code: Insert item into the data, but check and resolve collisions first
    // When you have this, implement the GetValue method
        if (newArray == null)
        {
            index = index % data.length;
            boolean inserted = false;
            int increment = 1;
            while (!inserted)
            {            
                if (data[index] == null)
                {
                    data[index] = item;
                    noofitems++;
                    inserted = true;
                }


            }  
        }
        else
        {
            if (t == null)
            {
                t = new Thread(this, threadName);
                t.start();
            }

            index = index % newArray.length;
            boolean inserted = false;
            int increment = 1;
            while (!inserted)
            {   
                if (index < 0)
                    System.out.println();
                if (newArray[index] == null)
                {
                    newArray[index] = item;
                    noofitems++;
                    inserted = true;
                }

            }

        }       
  }

  private int HashFunction(String key)
  {
    // Task 1 code: Hash the key and return a long value
    int code = 38;     
    for (int i=0; i < key.length(); i++) 
    {
        code = code*3+(key.charAt(i));
    }
    return (code>0?code:-code);
  }

At the moment I've set it to copy 5 of the small hash maps entries into the larger hash map at a time - however thinking about it, it'll probably be better to copy one at a time? Otherwise the main thread will idle while the 2nd thread finishes copying the remaining 4 across?

I currently get this error when trying to execute my program:

Thread Added
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1583
at hashmaps.HashMap.AddItem(HashMap.java:119)
at hashmaps.Dictionary.CreateDictionary(Dictionary.java:71)
at hashmaps.Dictionary.main(Dictionary.java:15)

Java Result: 1

Line 119 = if (newArray[index] == null)

Answer 1

Look at the end of your HashFunction method:

return (code>0?code:-code);

If your computed code happens to have the value Integer.MIN_VALUE, there is no int value to represent -Integer.MIN_VALUE and a numerical overflow occurs and the result is the still negative Integer.MIN_VALUE.

Had you used Math.abs(…) instead, reading its documentation had pointed you into the right direction:

Note that if the argument is equal to the value of Integer.MIN_VALUE, the most negative representable int value, the result is that same value, which is negative.

If the result of your HashFunction can be negative, the result of index % data.length can be negative as well which explains how you could receive an ArrayIndexOutOfBoundsException reporting a negative index.

---

Note that this has nothing to do with multi-threading. I don’t think that you are ready for implementing multi-threaded code. It’s not that you failed to make your code thread-safe, there is not the slightest attempt to do so. So as long as you didn’t learn about the need for thread-safe constructs, you should proceed with the tutorial instead of trying to implement concurrent code manipulating shared data.

---

Further, I’m not sure whether you understand the implications of your code, e.g. when you use

tempIncrement++;
index = index + (tempIncrement<<1);
index = index % newArray.length;

the operator ++ increments the variable by one while the operation <<1 is equivalent to doubling an int value. In other words, you are basically iterating by an increasing even number and since your array size is doubled on each capacity increase, you’re iteration can only reach one half of the array entries, either all even or all odd entries depending on the index it starts.

Even worse, since you are increasing the increment, you are skipping more and more entries until your increment is larger than the array itself, thus you will repeatedly check the same entry with the increment having no effect then.

So depending on the fill state of your hashmap you are playing Russian roulette here, risking an infinite loop while searching for a free (none-null) entry.

---

Another thing you should pad attention to is that you are calculating the hash code based on exact char values but combine it with the use of compareToIgnoreCase to decide whether two keys are equal. You should decide whether you want to match case insensitive, in that case you would have to adapt the hash code calculation, or you want to do an exact match, in that case you shouldn’t use compareToIgnoreCase but simply equals (you may use compareTo but there’s no reason to do so when you just need a test for equality). Otherwise, this inconsistency will backfire sooner or later…