创建一个字谜字典
Creating an anagram dictionary
我必须使用哈希表创建一个字谜字典。我从用户那里输入一个词,然后必须从我的变位词词典中输出该词的所有变位词。
这是我当前的程序,我正在创建一个哈希函数来计算每个单词的哈希值,并且作为彼此变位词的单词将具有相同的哈希值并被放入哈希表中的相同位置。
我遇到困难的部分是,当我创建此映射并对用户输入的词执行哈希函数以获取哈希表的索引时,我如何能够 return 所有该指数的价值?
到目前为止,这是我的代码
fis = new FileInputStream(file);
BufferedReader br = new BufferedReader(new InputStreamReader(fis));
System.out.println("Total file size to read (in bytes) : " + fis.available());
String content = new String();
while ((content = br.readLine()) != null) {
singleAddress.add(content);
}
for(int i = 0; i<singleAddress.size(); i++)
{
char[] chars = singleAddress.get(i).toCharArray();
Arrays.sort(chars);
int hash = 0;
for(int j = 0; j<chars.length; j++)
{
hash = 2*hash + (int)chars[j];
}
numbers.put(singleAddress.get(i), hash);
System.out.println(hash + " " + i);
}
我相信这会在哈希表中创建变位词字典,但我不确定如何 return 给定索引处的所有值。
我会使用 Map<String, List<String>
(或者更好的 Google Guava Multimap<String, String>
),然后应用您的逻辑:
- 把你的词写成小写版本
- 将小写版本的字符排序为一个键
- 使用该键将单词放入地图
当用户提供输入时,您重复第 1 步和第 2 步,但在第 3 步中使用 get(key)
,瞧,您就有了字谜列表。
示例:
Word = Anna -> key = aann
用户输入 = nana -> key = aann
然后你做 dictionary.get("aann")
并且应该得到包含元素 "Anna".
的列表
编辑:您的代码有问题
- 您没有显示
singleAddress
和 numbers
的声明,但我认为它是 Set<String>
和 Map<String, Integer>
。
- 在
numbers
中,键是单词,值是散列。您必须遍历该映射中的所有条目,然后才能使用相同的哈希检索所有条目。最好换个地方。
- 散列函数可能导致冲突,即非字谜的散列值相同(例如"ac"和"ba", "ac" 的散列为
2 * 64 + 66 = 194
,"ba" 的散列为 2 * 65 + 64 = 194
)。这就是为什么 Java 中的哈希集和映射总是使用 ´hashCode()_and_
equals().
hashCode()is used to get the bucket which is a list in the map while
equals()` 来检查是否键值其实是一样的
我会用
Map<String, Collection<String>>
其 KEY 将是特定单词的 "sorted String",其值将是所有单词的集合,可以使用字典中的关键字
例如
关键字:EILNST
值:[ELINTS、ENLIST、INLETS、LISTEN、SILENT、TINSEL]
因此,如果您想搜索单词 "Listen",请对单词进行排序,您将得到它的所有变位词,并且您必须从检索到的列表中排除该单词。
参考解决方案:
Best algorithm to find anagram of word from dictonary
我必须使用哈希表创建一个字谜字典。我从用户那里输入一个词,然后必须从我的变位词词典中输出该词的所有变位词。
这是我当前的程序,我正在创建一个哈希函数来计算每个单词的哈希值,并且作为彼此变位词的单词将具有相同的哈希值并被放入哈希表中的相同位置。
我遇到困难的部分是,当我创建此映射并对用户输入的词执行哈希函数以获取哈希表的索引时,我如何能够 return 所有该指数的价值? 到目前为止,这是我的代码
fis = new FileInputStream(file);
BufferedReader br = new BufferedReader(new InputStreamReader(fis));
System.out.println("Total file size to read (in bytes) : " + fis.available());
String content = new String();
while ((content = br.readLine()) != null) {
singleAddress.add(content);
}
for(int i = 0; i<singleAddress.size(); i++)
{
char[] chars = singleAddress.get(i).toCharArray();
Arrays.sort(chars);
int hash = 0;
for(int j = 0; j<chars.length; j++)
{
hash = 2*hash + (int)chars[j];
}
numbers.put(singleAddress.get(i), hash);
System.out.println(hash + " " + i);
}
我相信这会在哈希表中创建变位词字典,但我不确定如何 return 给定索引处的所有值。
我会使用 Map<String, List<String>
(或者更好的 Google Guava Multimap<String, String>
),然后应用您的逻辑:
- 把你的词写成小写版本
- 将小写版本的字符排序为一个键
- 使用该键将单词放入地图
当用户提供输入时,您重复第 1 步和第 2 步,但在第 3 步中使用 get(key)
,瞧,您就有了字谜列表。
示例:
Word = Anna -> key = aann
用户输入 = nana -> key = aann
然后你做 dictionary.get("aann")
并且应该得到包含元素 "Anna".
编辑:您的代码有问题
- 您没有显示
singleAddress
和numbers
的声明,但我认为它是Set<String>
和Map<String, Integer>
。 - 在
numbers
中,键是单词,值是散列。您必须遍历该映射中的所有条目,然后才能使用相同的哈希检索所有条目。最好换个地方。 - 散列函数可能导致冲突,即非字谜的散列值相同(例如"ac"和"ba", "ac" 的散列为
2 * 64 + 66 = 194
,"ba" 的散列为2 * 65 + 64 = 194
)。这就是为什么 Java 中的哈希集和映射总是使用 ´hashCode()_and_
equals().
hashCode()is used to get the bucket which is a list in the map while
equals()` 来检查是否键值其实是一样的
我会用
Map<String, Collection<String>>其 KEY 将是特定单词的 "sorted String",其值将是所有单词的集合,可以使用字典中的关键字
例如
关键字:EILNST
值:[ELINTS、ENLIST、INLETS、LISTEN、SILENT、TINSEL]
因此,如果您想搜索单词 "Listen",请对单词进行排序,您将得到它的所有变位词,并且您必须从检索到的列表中排除该单词。
参考解决方案: Best algorithm to find anagram of word from dictonary