java - 在 Java 中使用哈希值对数组进行排序

标签 java arrays sorting hash disk

我已从文件中读取数据,并从文件中取出每一行,然后将它们插入到数组中。我需要将这些字符串转换为字节并将它们写入基于磁盘的哈希文件。

我想要做的是将具有相同哈希值的每个字符串写入磁盘上的同一扇区。到目前为止,我所做的是根据它们的哈希值对它们进行排序,这在数组末尾的效果并​​不好,因为有 1000 个元素,而我的函数返回的最大哈希值是 249。

线性探测导致很多字符串错位,因此使用此数组写入我的扇区效果不太好。我该怎么办?

如果我没有说清楚的话,这是我到目前为止所做的代码:

private void importFile(String dataFile) {
  String line = null;
  theDisk.clearDisk();

  try {
    BufferedReader bufferedReader = new BufferedReader(new FileReader(dataFile));

    // List to hold the lines 
    List<String> list = new ArrayList<>();

    while((line = bufferedReader.readLine()) != null){
      list.add(line);
    }

    String[] strArray = list.toArray(new String[0]);
    String[] orderedArray = new String[strArray.length];

    for(int i = 0; i < strArray.length; i++) {
      String current = strArray[i];
      // Use email as key
      String key = current.substring(0,current.indexOf(','));
      int index = hashFunc3(key);

      if(orderedArray[index] == null) {
        orderedArray[index] = current;
      } else {
        while(orderedArray[index] != null) {
          index = index+1;
        }
        orderedArray[index] = current;
      }
    }

    // Always close files.
    bufferedReader.close();     
  }

  catch(FileNotFoundException ex) {
    System.out.println("Unable to open file '" + dataFile + "'");
  }

  catch(IOException ex) {
    System.out.println("Error reading file '" + dataFile + "'");
  }
}

最佳答案

我建议使用 ArrayListArrayList 而不是数组。这将允许您将具有相同散列的行放入相同的内部 ArrayList 中。使用哈希作为外部 ArrayList 中的索引来查找正确的内部列表。为了初始化,用空的 ArrayList 填充外部列表(以避免填充内部列表时出现 IndexOutOfBoundsException 或 NPE)。

        // No need to put the lines into a list first;
        // just sort them by hash as we read them
        List<List<String>> orderedList = new ArrayList<>(maxHash3 + 1);
        // add empty array lists to ordered list to hold the lines
        for (int ix = 0; ix <= maxHash3; ix++) {
            orderedList.add(new ArrayList<>());
        }

        while((line = bufferedReader.readLine()) != null){
              // Use email as key
              String key = line.substring(0,line.indexOf(','));
              int index = hashFunc3(key);
              // add line to inner ArrayList
              orderedList.get(index).add(line);
        }

以上用途:

private static final int maxHash3 = 249;

现在你可以这样做:

        // to write the lines to disk you may for instance do something like this:
        for (List<String> bucket : orderedList) {
            for (String currentLine : bucket) {
                // write currentLine to file
            }
        }

我们可能会使用 ArrayList 数组来代替,但混合数组和集合并不总是效果很好。

关于java - 在 Java 中使用哈希值对数组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39929815/

相关文章:

ruby-on-rails - 从数据行中堆叠带有 id 的列对

java - 解码在打开的套接字上挂起

javascript - 通过嵌套数组进行过滤

C 从函数返回 const char 指针或 char 指针

java - 数组意外行为

wpf - 根据 Group ItemCount 对组进行排序

java - 如何在 Java Swing 中创建一个 hello world?我的代码有什么问题?

java - 如何将 ArrayList 中的最后一个元素存储到另一个 ArrayList (Java)

java - 如何从指定位置获取附件并将​​其存储到文件系统?

algorithm - 二叉搜索树与排序双向链表