同时搜索多个HashMap
Search multiple HashMaps at the same time
tldr: 如何同时在多个（只读）Java HashMap 中搜索条目？
长版：
我有几个不同大小的词典存储为 HashMap< String, String >。一旦读入，就永远不能更改（严格只读）。
我想检查是否以及哪个字典已经用我的密钥存储了一个条目。
我的代码最初是在寻找这样的密钥：
public DictionaryEntry getEntry(String key) {
for (int i = 0; i < _numDictionaries; i++) {
HashMap<String, String> map = getDictionary(i);
if (map.containsKey(key))
return new DictionaryEntry(map.get(key), i);
}
return null;
}
然后事情变得有点复杂：我的搜索字符串可能包含拼写错误，或者是已存储条目的变体。例如，如果存储的密钥是 "banana"，我可能会查找 "bannana" 或 "a banana"，但仍然希望返回 "banana" 的条目。使用 Levenshtein-Distance，我现在遍历所有词典和其中的每个条目：
public DictionaryEntry getEntry(String key) {
for (int i = 0; i < _numDictionaries; i++) {
HashMap<String, String> map = getDictionary(i);
for (Map.Entry entry : map.entrySet) {
// Calculate Levenshtein distance, store closest match etc.
}
}
// return closest match or null.
}
到目前为止一切正常，我得到了我想要的条目。不幸的是，我必须在五个不同大小的词典中查找大约 7000 个字符串（约 30 - 70k 个条目），这需要一段时间。从我的处理输出来看，我有一个强烈的印象，我的查找主导了整个运行时间。
我改进运行时的第一个想法是并行搜索所有词典。由于要更改 none 个词典，并且同时访问一本词典的线程不超过一个，因此我没有看到任何安全问题。
问题只是：我该怎么做？我以前从未使用过多线程。我的搜索只找到了 Concurrent HashMaps（但据我所知，我不需要这个）和 Runnable-class，我必须将我的处理放在方法 run() 中。我想我可以重写我当前的 class 以适应 Runnable，但我想知道是否有更简单的方法来做到这一点（或者我怎样才能简单地使用 Runnable 来做到这一点，现在我有限的理解认为我有进行大量重组）。
自从我被要求分享 Levenshtein-Logic 以来：它真的没什么特别的，但是给你：
private int _maxLSDistance = 10;
public Map.Entry getClosestMatch(String key) {
Map.Entry _closestMatch = null;
int lsDist;
if (key == null) {
return null;
}
for (Map.Entry entry : _dictionary.entrySet()) {
// Perfect match
if (entry.getKey().equals(key)) {
return entry;
}
// Similar match
else {
int dist = StringUtils.getLevenshteinDistance((String) entry.getKey(), key);
// If "dist" is smaller than threshold and smaller than distance of already stored entry
if (dist < _maxLSDistance) {
if (_closestMatch == null || dist < _lsDistance) {
_closestMatch = entry;
_lsDistance = dist;
}
}
}
}
return _closestMatch
}
为了在您的情况下使用多线程，可能是这样的：
"monitor"class，主要是存储结果和协调线程；
public class Results {
private int nrOfDictionaries = 4; //
private ArrayList<String> results = new ArrayList<String>();
public void prepare() {
nrOfDictionaries = 4;
results = new ArrayList<String>();
}
public synchronized void oneDictionaryFinished() {
nrOfDictionaries--;
System.out.println("one dictionary finished");
notifyAll();
}
public synchronized boolean isReady() throws InterruptedException {
while (nrOfDictionaries != 0) {
wait();
}
return true;
}
public synchronized void addResult(String result) {
results.add(result);
}
public ArrayList<String> getAllResults() {
return results;
}
}
Thread是自己的，可以设置搜索特定的字典：
public class ThreadDictionarySearch extends Thread {
// the actual dictionary
private String dictionary;
private Results results;
public ThreadDictionarySearch(Results results, String dictionary) {
this.dictionary = dictionary;
this.results = results;
}
@Override
public void run() {
for (int i = 0; i < 4; i++) {
// search dictionary;
results.addResult("result of " + dictionary);
System.out.println("adding result from " + dictionary);
}
results.oneDictionaryFinished();
}
}
以及演示的主要方法：
public static void main(String[] args) throws Exception {
Results results = new Results();
ThreadDictionarySearch threadA = new ThreadDictionarySearch(results, "dictionary A");
ThreadDictionarySearch threadB = new ThreadDictionarySearch(results, "dictionary B");
ThreadDictionarySearch threadC = new ThreadDictionarySearch(results, "dictionary C");
ThreadDictionarySearch threadD = new ThreadDictionarySearch(results, "dictionary D");
threadA.start();
threadB.start();
threadC.start();
threadD.start();
if (results.isReady())
// it stays here until all dictionaries are searched
// because in "Results" it's told to wait() while not finished;
for (String string : results.getAllResults()) {
System.out.println("RESULT: " + string);
}
我认为最简单的方法是在条目集上使用流：
public DictionaryEntry getEntry(String key) {
for (int i = 0; i < _numDictionaries; i++) {
HashMap<String, String> map = getDictionary(i);
map.entrySet().parallelStream().foreach( (entry) ->
{
// Calculate Levenshtein distance, store closest match etc.
}
);
}
// return closest match or null.
}
当然前提是你用的是java8。您也可以将外部循环包装到 IntStream 中。您也可以直接使用 Stream.reduce 来获取距离最小的条目。
也许试试线程池：
ExecutorService es = Executors.newFixedThreadPool(_numDictionaries);
for (int i = 0; i < _numDictionaries; i++) {
//prepare a Runnable implementation that contains a logic of your search
es.submit(prepared_runnable);
}
我相信你也可以尝试找到一个快速估计完全不匹配的字符串（即长度上的显着差异），并用它尽快完成你的逻辑，移动到下一个候选。
我强烈怀疑 HashMaps 是否是合适的解决方案，特别是如果你想要一些模糊和停用词。您应该使用适当的全文搜索解决方案，例如 ElaticSearch or Apache Solr or at least an available engine like Apache Lucene.
也就是说，您可以使用穷人的版本：创建一个映射数组和一个 SortedMap，遍历该数组，获取当前 HashMap 的键并将它们存储在 SortedMap 中，并使用它们的索引哈希图。要检索键，首先在 SortedMap 中搜索所述键，使用索引位置从数组中获取相应的 HashMap，然后仅在一个 HashMap 中查找键。应该足够快，而不需要多个线程来挖掘 HashMap。但是，您可以将下面的代码变成可运行的，并且可以并行进行多个查找。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class Search {
public static void main(String[] arg) {
if (arg.length == 0) {
System.out.println("Must give a search word!");
System.exit(1);
}
String searchString = arg[0].toLowerCase();
/*
* Populating our HashMaps.
*/
HashMap<String, String> english = new HashMap<String, String>();
english.put("banana", "fruit");
english.put("tomato", "vegetable");
HashMap<String, String> german = new HashMap<String, String>();
german.put("Banane", "Frucht");
german.put("Tomate", "Gemüse");
/*
* Now we create our ArrayList of HashMaps for fast retrieval
*/
List<HashMap<String, String>> maps = new ArrayList<HashMap<String, String>>();
maps.add(english);
maps.add(german);
/*
* This is our index
*/
SortedMap<String, Integer> index = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
/*
* Populating the index:
*/
for (int i = 0; i < maps.size(); i++) {
// We iterate through or HashMaps...
HashMap<String, String> currentMap = maps.get(i);
for (String key : currentMap.keySet()) {
/* ...and populate our index with lowercase versions of the keys,
* referencing the array from which the key originates.
*/
index.put(key.toLowerCase(), i);
}
}
// In case our index contains our search string...
if (index.containsKey(searchString)) {
/*
* ... we find out in which map of the ones stored in maps
* the word in the index originated from.
*/
Integer mapIndex = index.get(searchString);
/*
* Next, we look up said map.
*/
HashMap<String, String> origin = maps.get(mapIndex);
/*
* Last, we retrieve the value from the origin map
*/
String result = origin.get(searchString);
/*
* The above steps can be shortened to
* String result = maps.get(index.get(searchString).intValue()).get(searchString);
*/
System.out.println(result);
} else {
System.out.println("\"" + searchString + "\" is not in the index!");
}
}
}
请注意，这是一个相当幼稚的实现，仅供说明之用。它没有解决几个问题（例如，您不能有重复的索引条目）。
使用此解决方案，您基本上是在用启动速度换取查询速度。
好的！！..
因为您关心的是获得更快的响应。
我建议你在线程之间分配工作。
让您拥有 5 个词典 可以将三个词典保留在一个线程中，其余两个将由另一个线程处理。
然后 找到匹配项的线程将停止或终止另一个线程。
可能您需要额外的逻辑来完成划分工作...但这不会影响您的表演时间。
并且您可能需要对代码进行更多更改才能获得接近的匹配：
for (Map.Entry entry : _dictionary.entrySet()) {
您正在使用 EntrySet 但是您无论如何都没有使用值，似乎获取条目集有点贵。我建议你只使用 keySet 因为你对该地图
中的 values 并不感兴趣
for (Map.Entry entry : _dictionary.keySet()) {
有关地图性能的更多详细信息请阅读此link Map performances
Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.
tldr: 如何同时在多个（只读）Java HashMap 中搜索条目？
长版：
我有几个不同大小的词典存储为 HashMap< String, String >。一旦读入，就永远不能更改（严格只读）。
我想检查是否以及哪个字典已经用我的密钥存储了一个条目。
我的代码最初是在寻找这样的密钥：
public DictionaryEntry getEntry(String key) {
for (int i = 0; i < _numDictionaries; i++) {
HashMap<String, String> map = getDictionary(i);
if (map.containsKey(key))
return new DictionaryEntry(map.get(key), i);
}
return null;
}
然后事情变得有点复杂：我的搜索字符串可能包含拼写错误，或者是已存储条目的变体。例如，如果存储的密钥是 "banana"，我可能会查找 "bannana" 或 "a banana"，但仍然希望返回 "banana" 的条目。使用 Levenshtein-Distance，我现在遍历所有词典和其中的每个条目：
public DictionaryEntry getEntry(String key) {
for (int i = 0; i < _numDictionaries; i++) {
HashMap<String, String> map = getDictionary(i);
for (Map.Entry entry : map.entrySet) {
// Calculate Levenshtein distance, store closest match etc.
}
}
// return closest match or null.
}
到目前为止一切正常，我得到了我想要的条目。不幸的是，我必须在五个不同大小的词典中查找大约 7000 个字符串（约 30 - 70k 个条目），这需要一段时间。从我的处理输出来看，我有一个强烈的印象，我的查找主导了整个运行时间。
我改进运行时的第一个想法是并行搜索所有词典。由于要更改 none 个词典，并且同时访问一本词典的线程不超过一个，因此我没有看到任何安全问题。
问题只是：我该怎么做？我以前从未使用过多线程。我的搜索只找到了 Concurrent HashMaps（但据我所知，我不需要这个）和 Runnable-class，我必须将我的处理放在方法 run() 中。我想我可以重写我当前的 class 以适应 Runnable，但我想知道是否有更简单的方法来做到这一点（或者我怎样才能简单地使用 Runnable 来做到这一点，现在我有限的理解认为我有进行大量重组）。
自从我被要求分享 Levenshtein-Logic 以来：它真的没什么特别的，但是给你：
private int _maxLSDistance = 10;
public Map.Entry getClosestMatch(String key) {
Map.Entry _closestMatch = null;
int lsDist;
if (key == null) {
return null;
}
for (Map.Entry entry : _dictionary.entrySet()) {
// Perfect match
if (entry.getKey().equals(key)) {
return entry;
}
// Similar match
else {
int dist = StringUtils.getLevenshteinDistance((String) entry.getKey(), key);
// If "dist" is smaller than threshold and smaller than distance of already stored entry
if (dist < _maxLSDistance) {
if (_closestMatch == null || dist < _lsDistance) {
_closestMatch = entry;
_lsDistance = dist;
}
}
}
}
return _closestMatch
}
为了在您的情况下使用多线程，可能是这样的：
"monitor"class，主要是存储结果和协调线程；
public class Results {
private int nrOfDictionaries = 4; //
private ArrayList<String> results = new ArrayList<String>();
public void prepare() {
nrOfDictionaries = 4;
results = new ArrayList<String>();
}
public synchronized void oneDictionaryFinished() {
nrOfDictionaries--;
System.out.println("one dictionary finished");
notifyAll();
}
public synchronized boolean isReady() throws InterruptedException {
while (nrOfDictionaries != 0) {
wait();
}
return true;
}
public synchronized void addResult(String result) {
results.add(result);
}
public ArrayList<String> getAllResults() {
return results;
}
}
Thread是自己的，可以设置搜索特定的字典：
public class ThreadDictionarySearch extends Thread {
// the actual dictionary
private String dictionary;
private Results results;
public ThreadDictionarySearch(Results results, String dictionary) {
this.dictionary = dictionary;
this.results = results;
}
@Override
public void run() {
for (int i = 0; i < 4; i++) {
// search dictionary;
results.addResult("result of " + dictionary);
System.out.println("adding result from " + dictionary);
}
results.oneDictionaryFinished();
}
}
以及演示的主要方法：
public static void main(String[] args) throws Exception {
Results results = new Results();
ThreadDictionarySearch threadA = new ThreadDictionarySearch(results, "dictionary A");
ThreadDictionarySearch threadB = new ThreadDictionarySearch(results, "dictionary B");
ThreadDictionarySearch threadC = new ThreadDictionarySearch(results, "dictionary C");
ThreadDictionarySearch threadD = new ThreadDictionarySearch(results, "dictionary D");
threadA.start();
threadB.start();
threadC.start();
threadD.start();
if (results.isReady())
// it stays here until all dictionaries are searched
// because in "Results" it's told to wait() while not finished;
for (String string : results.getAllResults()) {
System.out.println("RESULT: " + string);
}
我认为最简单的方法是在条目集上使用流：
public DictionaryEntry getEntry(String key) {
for (int i = 0; i < _numDictionaries; i++) {
HashMap<String, String> map = getDictionary(i);
map.entrySet().parallelStream().foreach( (entry) ->
{
// Calculate Levenshtein distance, store closest match etc.
}
);
}
// return closest match or null.
}
当然前提是你用的是java8。您也可以将外部循环包装到 IntStream 中。您也可以直接使用 Stream.reduce 来获取距离最小的条目。
也许试试线程池：
ExecutorService es = Executors.newFixedThreadPool(_numDictionaries);
for (int i = 0; i < _numDictionaries; i++) {
//prepare a Runnable implementation that contains a logic of your search
es.submit(prepared_runnable);
}
我相信你也可以尝试找到一个快速估计完全不匹配的字符串（即长度上的显着差异），并用它尽快完成你的逻辑，移动到下一个候选。
我强烈怀疑 HashMaps 是否是合适的解决方案，特别是如果你想要一些模糊和停用词。您应该使用适当的全文搜索解决方案，例如 ElaticSearch or Apache Solr or at least an available engine like Apache Lucene.
也就是说，您可以使用穷人的版本：创建一个映射数组和一个 SortedMap，遍历该数组，获取当前 HashMap 的键并将它们存储在 SortedMap 中，并使用它们的索引哈希图。要检索键，首先在 SortedMap 中搜索所述键，使用索引位置从数组中获取相应的 HashMap，然后仅在一个 HashMap 中查找键。应该足够快，而不需要多个线程来挖掘 HashMap。但是，您可以将下面的代码变成可运行的，并且可以并行进行多个查找。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
public class Search {
public static void main(String[] arg) {
if (arg.length == 0) {
System.out.println("Must give a search word!");
System.exit(1);
}
String searchString = arg[0].toLowerCase();
/*
* Populating our HashMaps.
*/
HashMap<String, String> english = new HashMap<String, String>();
english.put("banana", "fruit");
english.put("tomato", "vegetable");
HashMap<String, String> german = new HashMap<String, String>();
german.put("Banane", "Frucht");
german.put("Tomate", "Gemüse");
/*
* Now we create our ArrayList of HashMaps for fast retrieval
*/
List<HashMap<String, String>> maps = new ArrayList<HashMap<String, String>>();
maps.add(english);
maps.add(german);
/*
* This is our index
*/
SortedMap<String, Integer> index = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
/*
* Populating the index:
*/
for (int i = 0; i < maps.size(); i++) {
// We iterate through or HashMaps...
HashMap<String, String> currentMap = maps.get(i);
for (String key : currentMap.keySet()) {
/* ...and populate our index with lowercase versions of the keys,
* referencing the array from which the key originates.
*/
index.put(key.toLowerCase(), i);
}
}
// In case our index contains our search string...
if (index.containsKey(searchString)) {
/*
* ... we find out in which map of the ones stored in maps
* the word in the index originated from.
*/
Integer mapIndex = index.get(searchString);
/*
* Next, we look up said map.
*/
HashMap<String, String> origin = maps.get(mapIndex);
/*
* Last, we retrieve the value from the origin map
*/
String result = origin.get(searchString);
/*
* The above steps can be shortened to
* String result = maps.get(index.get(searchString).intValue()).get(searchString);
*/
System.out.println(result);
} else {
System.out.println("\"" + searchString + "\" is not in the index!");
}
}
}
请注意，这是一个相当幼稚的实现，仅供说明之用。它没有解决几个问题（例如，您不能有重复的索引条目）。
使用此解决方案，您基本上是在用启动速度换取查询速度。
好的！！..
因为您关心的是获得更快的响应。
我建议你在线程之间分配工作。
让您拥有 5 个词典 可以将三个词典保留在一个线程中，其余两个将由另一个线程处理。 然后 找到匹配项的线程将停止或终止另一个线程。
可能您需要额外的逻辑来完成划分工作...但这不会影响您的表演时间。
并且您可能需要对代码进行更多更改才能获得接近的匹配：
for (Map.Entry entry : _dictionary.entrySet()) {
您正在使用 EntrySet 但是您无论如何都没有使用值，似乎获取条目集有点贵。我建议你只使用 keySet 因为你对该地图
values 并不感兴趣
for (Map.Entry entry : _dictionary.keySet()) {
有关地图性能的更多详细信息请阅读此link Map performances
Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.