Java (basic) 多线程与 Hashmap 问题

Question

我正在研究如何进行多线程，主要来自这个网站：http://www.tutorialspoint.com/java/java_multithreading.htm

我正在尝试将它实现到我自己的哈希映射实现中。我的想法是，当我重新调整我的散列图大小时，我可以使用多线程，以便在它向较大的散列图添加条目时，我可以使用另一个线程将较小的散列图重新散列为较大的散列图。

我的 Hash Map 实现工作正常 - 但是我正在努力掌握多线程，所以我想知道是否有人可以看一下我的代码并看看我哪里出错了？

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

目前我已将其设置为一次将 5 个小哈希映射条目复制到较大的哈希映射中 - 但是考虑一下，一次复制一个可能会更好？否则主线程将空闲，而第二个线程完成复制剩余的 4 个？

我目前在尝试执行我的程序时遇到此错误：

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 结果：1

第 119 行 = if (newArray[index] == null)

Answer 1

看看你的 HashFunction 方法的结尾：

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

如果您计算的 code 恰好有值 Integer.MIN_VALUE，则没有 int 值来表示 -Integer.MIN_VALUE 并且发生数值溢出，结果是仍然是负面的 Integer.MIN_VALUE.

如果您改用 Math.abs(…)，阅读 its documentation 会为您指明正确的方向：

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.

如果您的 HashFunction 结果可能为负，那么 index % data.length 的结果也可能为负，这就解释了您如何收到 ArrayIndexOutOfBoundsException 报告负指数。

请注意，这与多线程无关。我认为您还没有准备好实施多线程代码。这并不是说您未能使您的代码线程安全，没有丝毫尝试这样做。因此，只要您没有了解线程安全构造的必要性，就应该继续学习本教程，而不是尝试实现并发代码来操作共享数据。

此外，我不确定您是否理解代码的含义，例如当你使用

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

运算符 ++ 将变量递增 1，而运算符 <<1 相当于将 int 值加倍。换句话说，您基本上是通过增加 even 数字进行迭代，并且由于每次容量增加时您的数组大小都是 double，因此您可以进行迭代仅到达数组条目的一半，所有偶数或所有奇数条目取决于它开始的索引。

更糟糕的是，由于您正在增加增量，因此您将跳过越来越多的条目，直到您的增量大于数组本身，因此您将重复检查相同的条目，此时增量无效。

因此，根据您的哈希图的填充状态，您在这里玩俄罗斯轮盘赌，在搜索免费 (none-null) 条目时冒着无限循环的风险。

您应该注意的另一件事是，您正在根据精确的 char 值计算哈希码，但将其与 compareToIgnoreCase 的使用结合起来确定两个键是否相等。您应该决定是否要匹配不区分大小写的内容，在这种情况下您必须调整哈希码计算，或者您想要进行精确匹配，在这种情况下您不应该使用 compareToIgnoreCase 而只是 equals（您可以使用 compareTo，但当您只需要测试是否相等时，没有理由这样做）。否则，这种不一致迟早会适得其反……

Java (basic) 多线程与 Hashmap 问题

Java (basic) Multithreading with Hashmap issues

java

multithreading

hashmap