Какая структура данных лучше всего подходит для баланса порядка и скорости поиска ⇐ JAVA

[Anonymous]

Вопрос:
Меня попросили написать простого менеджера магазина, который отслеживает текущий объем продаж различных товаров и способен распечатывать самое продаваемое количество товаров - по сути, реализуя эти два метода:

Код: Выделить всё

public void addSale(String itemName, int quantity) {
// Either add a new entry or increment current quantity.
}

public void print(int mostSold) {
// Print the mostSold sold items and their quantities.
}

1 — Наивно
Игнорируя синхронизацию, я придумал следующую наивную реализацию, сопоставляя имя с общим количеством и упорядочивая записи во время вызова печати.

Код: Выделить всё

private final Map m_sales = new HashMap();

public void addSale(final String itemName, final int quantity) {
final int currentQuantity = m_sales.getOrDefault(itemName, 0);
m_sales.put(itemName, currentQuantity + quantity);
}

public void print(final int mostSold) {
m_sales.entrySet().stream()
.sorted(Comparator.comparingInt(Map.Entry::getValue))
.limit(mostSold)
.forEach(entry -> {
IO.println(entry.getKey() + ": " + entry.getValue());
});
}

Временная сложность addSale составляет O(1), а print — O(n log(n)) в среднем и худшем времени.
2 — Улучшение
В качестве следующего шага мне сказали, что оба метода будут вызываться одинаково часто и, следовательно, смогу ли я сократить время печати.
/>Моей первой мыслью было посмотреть, смогу ли я избежать повторной сортировки записей карты снова и снова и выполнить некоторую служебную работу во время вставки, чтобы поддерживать некоторый порядок внутри самой структуры данных. В Java есть TreeMap, но его можно упорядочить только по ключу. Поэтому я решил создать собственный объект и использовать TreeSet для поддержания порядка в зависимости от количества.

Код: Выделить всё

private final Set m_sales = new TreeSet(Comparator.comparingInt(item -> item.m_quantity));

public void addSale(final String itemName, final int quantity) {
Item item = null;
for (final Item currentItem : m_sales) {
if (currentItem.m_name.equals(itemName)) {
item = currentItem;
break;
}
}
if (item == null) {
item = new Item(itemName);
}
item.m_quantity += quantity;
m_sales.add(item);
}

public void print(final int mostSold) {
m_sales.stream()
.limit(mostSold)
.forEach(item -> {
IO.println(item.m_name + ": " + item.m_quantity);
});
}

private static class Item {

private final String m_name;

private int m_quantity = 0;

private Item(final String name) {
m_name = name;
}

@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()){
return false;
}
Item item = (Item) o;
return Objects.equals(m_name, item.m_name);
}

@Override
public int hashCode() {
return Objects.hashCode(m_name);
}
}

Код: Выделить всё

print

теперь равен O(n), но addSale изменился с O(1) на O(n), так как мы больше не можем полагаться на операции Map с постоянным временем и в худшем случае приходится перебирать полный набор.
3 - Моя оптимизация
Поэтому я объединил их, чтобы использовать карту в качестве своего рода поиска. index.

Код: Выделить всё

private final Set m_sales = new TreeSet(Comparator.comparingInt(item -> item.m_quantity));

private final Map m_index = new HashMap();

public void addSale(final String itemName, final int quantity) {
Item item = m_index.get(itemName);
if (item == null) {
item = new Item(itemName, quantity);
m_index.put(itemName, item);
} else {
item.m_quantity += quantity;
}
m_sales.add(item);
}

public void print(final int mostSold) {
m_sales.stream()
.limit(mostSold)
.forEach(item -> {
IO.println(item.m_name + ": " + item.m_quantity);
});
}

private static class Item {

private final String m_name;

private int m_quantity;

private Item(final String name, final int quantity) {
m_name = name;
m_quantity = quantity;
}

@Override
public boolean equals(Object o) {
if (o == null || getClass() != o.getClass()){
return false;
}
Item item = (Item) o;
return Objects.equals(m_name, item.m_name);
}

@Override
public int hashCode() {
return Objects.hashCode(m_name);
}
}

Поскольку у нас есть дополнительная карта, нам не нужно перебирать TreeSet, чтобы увидеть, есть ли у нас существующий элемент для обновления, а не вводить новый. Я думаю, что это делает addSale O(log(n)), а не O(n). Однако это может привести к несоответствиям, если управление между картой и набором не осуществляется тщательно. Я также не учел, как сюда вписывается синхронизация, и понимаю, что это может сделать эту реализацию далеко не идеальной.
Мой вопрос
Есть ли лучший способ сделать это? Есть ли структура данных, которая могла бы лучше объединить необходимость упорядочивания и поиска, которую я пропустил? Я чувствую, что, возможно, я слишком усложняю это. Спасибо!