Блог

В большинстве языков, включая Java, есть API, что-то вроде java.util.Map которого разработано, чтобы упростить циклическую обработку значения, учитывая ключ, который к нему привязан. Но не всегда существует удобный способ поиска ключа, учитывая ключ (я почти уверен, что Python усложняет его, C упрощает (просто попросите итератор), этот вопрос о Java, который, как я подозреваю, так же плох, как и Python). Сначала это может показаться глупым: зачем вам нужно искать ключ, который у вас уже есть? Но подумайте о чем-то подобном (в примере ниже используется Set вместо Map , но та же идея):

 TreeSet<String> dictionary = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
dictionary.add("Monday"); // populate dictionary
String word = "MONDAY"; // user input, or something
if(dictionary.contains(word)) System.out.println(word   " already in dictionary");
 

Приведенный выше фрагмент кода будет напечатан MONDAY already in dictionary . Это, конечно, неправильно, потому что «ПОНЕДЕЛЬНИК» нет в словаре; скорее, «понедельник» есть. Как мы можем сделать сообщение более точным? В этом случае мы можем создать функцию справки, которая использует тот факт, что a TreeSet есть a NavigableSet (на самом деле аналогичный трюк работает SortedSet , хотя он немного менее удобен).:

 String lookup(NavigableSet<String> set, String key) {
    assert set.contains(key) : key   " not in set";
    return set.floor(key);
}
 

Теперь мы можем исправить последнюю строку предыдущего фрагмента кода:

 if(dictionary.contains(word)) System.out.println(lookup(word)   " already in dictionary");
 

Который напечатает правильную вещь. Но теперь давайте попробуем пример с набором хэшей:

 import java.util.HashSet;
/** Maintains a set of strings; useful as a replacement for String.intern() */
class StringInterner {
    private final HashSet<String> set = new HashSet<>();
    /** use this instead of String.intern() */
    String intern(String s) {
         if(!set.contains(s)) {
             s.add(s);
             return s;
         }
         for(String str : set) // linear scan!!
             if(str.equals(s)) return str;
         throw new AssertionError("something went very wrong");
    }
}
 

Приведенный выше код прибегает к линейному сканированию, чтобы найти то, о чем он уже знает, что там есть. Обратите внимание, что это HashSet может легко дать нам то, что мы ищем, потому что оно должно уметь это делать только для реализации contains() . Но для этого нет API, поэтому мы даже не можем задать этот вопрос. (На самом деле, HashMap есть внутренний метод, называемый getNode , который в значительной степени является тем, что мы хотим, но он является внутренним.) Простой обходной путь в этом случае-использовать карту вместо набора: вместо этого set.add(s) мы могли бы использовать map.put(s,s) . Но что, если мы уже используем карту, потому что у нас уже есть данные, которые мы хотим связать с нашим ключом? Затем мы можем либо использовать две карты и тщательно синхронизировать их, либо сохранить кортеж размером 2 в качестве «значения» на нашей карте, где первый элемент в кортеже-это просто ключ карты. Оба эти решения кажутся излишне неловкими.

Есть ли лучший способ?

Есть ли лучший способ?

Нет, это не так.

Для хэш-карт это не имеет значения, потому что ваш аргумент «два эквивалентных ключа» не имеет смысла для HashMap . Эти два ключа всегда должны быть equals , что с точки зрения Java означает, что они должны быть заменяемыми во всех отношениях.