用 Java 中的哈希值排序数组

Question

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

我想做的是将每个具有相同散列值的字符串写入我磁盘上的相同扇区。到目前为止，我所做的是根据它们的哈希值对它们进行排序，这在数组末尾的效果不是很好，因为有 1000 个元素，而我的函数 returns 的最大哈希值是 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 + "'");
  }
}

Answer 1

只需使用您自己的比较器对列表进行排序：

Collections.sort(list, new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
      return Integer.compare(o1.hashCode(), o2.hashCode());
      //or use your own hashcode functions here
    }
}); //now list is sorted by hashcode
String[] orderedArray = list.toArray(new String[0]);

Answer 2

我建议使用 ArrayList 的 ArrayList 而不是数组。这将允许您将具有相同散列的行放入相同的内部 ArrayList。使用散列作为外部 ArrayList 中的索引来找到正确的内部列表。对于初始化，用空 ArrayLists 填充外部列表（以避免在填充到内部列表时出现 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 中的哈希值排序数组

Ordering an Array with Hash Values in Java

java

arrays

sorting

hash

disk