基于字符串键合并排序哈希表对
Merge Sorting HashTable pairs based on String key
我正在编写一个程序来计算文本文件中的单词出现次数,然后按字母顺序打印它们。我的计数部分工作正常,但我需要使用合并排序来按字母顺序排列单词。为此,我编写了以下方法:
public static HashPair<String, Integer>[] mergeSort(HashPair<String, Integer>[] data)
{
HashPair<String, Integer>[] sortedData = null;
if (data.length >= 2) {
HashPair<String, Integer>[] left = new HashPair[data.length / 2];
HashPair<String, Integer>[] right = new HashPair[data.length - data.length / 2];
for (int i = 0; i < left.length; i++) {
if(data[i] != null)
{
left[i] = data[i];
}
}
for (int i = 0; i < right.length; i++) {
if(data[i + data.length / 2] != null)
{
right[i] = data[i + data.length / 2];
}
}
mergeSort(left);
mergeSort(right);
sortedData = merge(data, left, right);
}
return sortedData;
}
/**
* Helper method to merge the data back into one array
* Based on code found at:
*
* @param names
* @param left
* @param right
*/
public static HashPair<String, Integer>[] merge(HashPair<String, Integer>[] data, HashPair<String, Integer>[] left, HashPair<String, Integer>[] right)
{
int a = 0;
int b = 0;
for (int i = 0; i < data.length; i++)
{
try
{
if (b >= right.length || (a < left.length && left[a].getFirst().compareToIgnoreCase(right[b].getFirst()) < 0))
{
data[i] = left[a];
a++;
}
else
{
data[i] = right[b];
b++;
}
}
catch(NullPointerException e)
{
continue;
}
}
return data;
}
要在 main 中调用这些方法并打印出 table 我使用以下 3 行
HashPair<String, Integer>[] unsortedData = wordTable.getData(); //Getting unsorted data to be sorted
HashPair<String, Integer>[] sortedData = mergeSort(unsortedData);
HashTable<String, Integer> sortedWordTable = new HashTable(sortedData);
sortedWordTable.dump(); //Printing all the words found with their respective counts
然而,这些词未按字母顺序打印,就好像从来没有排序过一样运行,我不明白为什么
当您使用 sortedData 作为参数创建新的 HashTable 时,它们将不会按顺序排列。哈希表用于效率而不是排序。添加元素时,它们基本上以随机顺序散列到 table 中。
找到一种不同于哈希表的方式来保存排序后的数据。就像一个数组列表。
您可以使用 TreeMap 代替 HashTable;在这种情况下,单词已经排序。每次遇到一个新单词时,您只需使用代码:
if(!map.containsKey(word)) map.put(word,0);
map.put(word, map.get(word)+1);
我正在编写一个程序来计算文本文件中的单词出现次数,然后按字母顺序打印它们。我的计数部分工作正常,但我需要使用合并排序来按字母顺序排列单词。为此,我编写了以下方法:
public static HashPair<String, Integer>[] mergeSort(HashPair<String, Integer>[] data)
{
HashPair<String, Integer>[] sortedData = null;
if (data.length >= 2) {
HashPair<String, Integer>[] left = new HashPair[data.length / 2];
HashPair<String, Integer>[] right = new HashPair[data.length - data.length / 2];
for (int i = 0; i < left.length; i++) {
if(data[i] != null)
{
left[i] = data[i];
}
}
for (int i = 0; i < right.length; i++) {
if(data[i + data.length / 2] != null)
{
right[i] = data[i + data.length / 2];
}
}
mergeSort(left);
mergeSort(right);
sortedData = merge(data, left, right);
}
return sortedData;
}
/**
* Helper method to merge the data back into one array
* Based on code found at:
*
* @param names
* @param left
* @param right
*/
public static HashPair<String, Integer>[] merge(HashPair<String, Integer>[] data, HashPair<String, Integer>[] left, HashPair<String, Integer>[] right)
{
int a = 0;
int b = 0;
for (int i = 0; i < data.length; i++)
{
try
{
if (b >= right.length || (a < left.length && left[a].getFirst().compareToIgnoreCase(right[b].getFirst()) < 0))
{
data[i] = left[a];
a++;
}
else
{
data[i] = right[b];
b++;
}
}
catch(NullPointerException e)
{
continue;
}
}
return data;
}
要在 main 中调用这些方法并打印出 table 我使用以下 3 行
HashPair<String, Integer>[] unsortedData = wordTable.getData(); //Getting unsorted data to be sorted
HashPair<String, Integer>[] sortedData = mergeSort(unsortedData);
HashTable<String, Integer> sortedWordTable = new HashTable(sortedData);
sortedWordTable.dump(); //Printing all the words found with their respective counts
然而,这些词未按字母顺序打印,就好像从来没有排序过一样运行,我不明白为什么
当您使用 sortedData 作为参数创建新的 HashTable 时,它们将不会按顺序排列。哈希表用于效率而不是排序。添加元素时,它们基本上以随机顺序散列到 table 中。
找到一种不同于哈希表的方式来保存排序后的数据。就像一个数组列表。
您可以使用 TreeMap 代替 HashTable;在这种情况下,单词已经排序。每次遇到一个新单词时,您只需使用代码:
if(!map.containsKey(word)) map.put(word,0);
map.put(word, map.get(word)+1);