Как я выбираю между хеш-таблицей и Trie (дерево префикса)?
Другое событие NullPointerException возникает, когда объявляется массив объектов, а затем сразу же пытается разыменовать его внутри.
String[] phrases = new String[10];
String keyPhrase = "Bird";
for(String phrase : phrases) {
System.out.println(phrase.equals(keyPhrase));
}
Этот конкретный NPE можно избежать, если порядок сравнения отменяется ; а именно, использовать .equals для гарантированного непустого объекта.
Все элементы внутри массива инициализируются их общим начальным значением ; для любого типа массива объектов, это означает, что все элементы null.
Вы должны инициализировать элементы в массиве перед доступом или разыменованием их.
String[] phrases = new String[] {"The bird", "A bird", "My bird", "Bird"};
String keyPhrase = "Bird";
for(String phrase : phrases) {
System.out.println(phrase.equals(keyPhrase));
}
3 ответа
Преимущества попыток:
основы:
- Предсказуемый O (k) время поиска, где k является размером ключа
- , Поиск может взять меньше, чем k время, если это не там
- Поддержки, заказанные обход
- , Никакая потребность в Удалении хеш-функции
- не проста
Новые операции:
- можно быстро искать префиксы ключей, перечислить все записи с данным префиксом, и т.д.
Преимущества связанной структуры:
- , Если существует много общих префиксов, пространство, они требуют, совместно используется.
- Неизменные попытки могут совместно использовать структуру. Вместо того, чтобы обновить trie на месте, можно создать новый, это отличается только вдоль одного ответвления, в другом месте указывающего в старый trie. Это может быть полезно для параллелизма, нескольких одновременных версий таблицы, и т.д.
- , неизменный trie сжимаем. Таким образом, это может совместно использовать структуру на эти суффиксы также хешем-consing.
Преимущества хеш-таблиц:
- Все знают хеш-таблицы, правильно? Ваша система будет уже иметь хорошую хорошо оптимизированную реализацию, быстрее, чем попытки большинства целей.
- Ваши ключи не должны иметь никакой специальной структуры.
- более эффективный пространством, чем очевидное связался, trie структура ( см. комментарии ниже )
Все это зависит, на какой проблеме Вы пытаетесь решить. Если все, что необходимо сделать, является вставками и поисками, пойдите с хеш-таблицей. Если необходимо решить более сложные проблемы, такие как связанные с префиксом запросы, то trie мог бы быть лучшим решением.
Некоторые (обычно встраиваемый, в реальном времени) приложения требуют, чтобы время обработки было независимо от данных. В этом случае хеш-таблица может гарантировать известное время выполнения, в то время как trie варьируется на основе данных.