Удаление повторов из очереди LinkedList

233

11 марта 2017, 01:56

Есть следующий код:

short[][] test = new short[6][2];
Queue<short[]> arr = new LinkedList<short[]>();

Массив test заполнен следующим образом:

[[1,2],[3,4],[1,2],[3,4],[1,2],[3,4]]

Есть функция добавления элемента в LinkedList:

private static void AddElement(short[] in, Queue<short[]> link_arr, int max_size)
{
    // удалить самый старый элемент если очередь больше max_size
    if (link_arr.size() > max_size)
    {
       link_arr.poll();
    }
    link_arr.add(in);
    Set<short[]> set_arr = new LinkedHashSet<short[]>(link_arr);
    link_arr.clear();
    link_arr.addAll(set_arr);
}

Вызывается следующим образом:

for (int i = 0; i < test.length; i++)
{
    AddElement(test[i], arr, max_size);
}

В итоге после выполнения программы в arr всё равно лежат повторяющиеся элементы. Если arr является просто списком из short, то всё работает.

Можно ли средствами Java библиотек получить уникальный список, или придется всё писать самому?

Answer 1

Использовать массив в качестве ключа в Map плохая затея, потому что нельзя рассчитывать на то, что два массива, содержащие одинаковые элементы, будут иметь одинаковый hash code и возвращать true при сравнении с помощью equals.

Одним из вариантов решения проблемы является создание для массива класса-обёртки, реализующего методы hashCode и equals:

private static class Element
{
    public final short[] values;
    public Element(short[] values)
    {
        this.values = values;
    }
    @Override
    public boolean equals(Object obj)
    {
        if (obj instanceof Element)
        {
            return Arrays.equals(values, ((Element)obj).values);
        }
        return false;
    }
    @Override
    public int hashCode()
    {
        return Arrays.hashCode(values);
    }
}
public static void main(String[] args)
{
    short[][] test = { { 1,2 }, { 3,4 }, { 1,2 }, { 3,4 }, { 1,2 }, { 3,4 } };
    Set<Element> uniqueElements = new HashSet<>();
    for (short[] group : test)
    {
        uniqueElements.add(new Element(group));
    }
    List<short[]> result = new ArrayList<>();
    for (Element element : uniqueElements)
    {
        result.add(element.values);
    }
}

Вместо HashSet можно использовать LinkedHashSet, равно как и LinkedList вместо ArrayList, - для получения уникальных элементов это не принципиально.

В Java 8 метод main может выглядеть так:

short[][] test = { { 1,2 }, { 3,4 }, { 1,2 }, { 3,4 }, { 1,2 }, { 3,4 } };
List<short[]> result = Stream.of(test)
        .map(Element::new)
        .distinct()
        .map(e -> e.values)
        .collect(Collectors.toList());

Если обязательно нужно добавлять элементы в очередь по одному в отдельном методе, то можно преобразовать исходный код так:

public static void main(String[] args)
{
    short[][] test = { { 1,2 }, { 3,4 }, { 1,2 }, { 3, 4 }, { 5,6 }, { 3,4 } };
    Queue<Element> queue = new LinkedList<>();
    for (short[] group : test)
    {
        addElement(group, queue, 10);
    }
}
private static void addElement(short[] array, Queue<Element> queue, int maxSize)
{
    Element element = new Element(array);
    if (queue.contains(element))
    {
        return;
    }
    while (queue.size() >= maxSize)
    {
        queue.poll();
    }
    queue.add(element);
}

Есть вместо блокировки добавления дубля нужно добавлять элемент заново в конец очереди, то вместо

if (queue.contains(element)) { return; }

достаточно использовать

queue.remove(element);

Answer 2

Так как добавляются разные объекты массивов, без переопределенного equals(), то set сравнивает хеш-коды (ссылки) обращаясь к родителю Object, а они отличаются у разных объектов. Если хочешь удалять семантически разные значения на уровне логики приложения, то условие сравнения объектов должен прописать сам (переопределить equals())