Структура данных Java, которая индексирует идентичные элементы только один раз

Question

Следующий код Java:

public static void main(String args[]) {

    int[] x = new int[] {1, 2, 3};
    int[] y = new int[] {1, 2, 3};

    LinkedList<int[]> list = new LinkedList<int[]>();

    list.add(x);

    System.out.println("List contains y: " + list.contains(y));

}

дает вывод

    List contains y: false

, что имеет смысл, поскольку x и y являются ссылками на различные области памяти, однако естьтакже в том смысле, что они равны (они имеют одинаковые элементы в одном и том же порядке).

Существует ли структура данных, которая в данном примере вернула бы true запросу list.contains(y)?

Answer 1

Я не верю, что существует структура данных Java, которая выдает true для contains(), как вы описали.

Проблема, как вы, вероятно, знаете, в том, что для массивов Java, equals() проверяет только идентичность объекта, а не «равенство», как его определяет большинство.

Поскольку contains() в этом случае полагается на equals() (и большую часть времени), вы застряли сданное поведение.

Вы должны будете реализовать List, который специально отменяет contains(), чтобы обеспечить желаемое поведение для массивов Java, возможно, с использованием Arrays.equals().

.используйте List вместо массива;тогда у вас будет List<List<Integer>>.contains() должен работать в этом сценарии, поскольку он будет использовать equals() в реализации базового List.

Answer 2

Похоже, вы действительно ищете реализацию Set.

Коллекция, не содержащая дублирующихся элементов.Более формально, наборы не содержат пары элементов e1 и e2, таких как e1.equals(e2), и не более одного null элемента.Как следует из его названия, этот интерфейс моделирует абстракцию математического набора.

Если вы хотите хранить наборы значений int, вы можете использовать this Tuple class Iнедавно написал для еще один вопрос по SO .

Set<Tuple> myTuples = new HashSet<Tuple>();
Tuple<Integer> x = Tuple.create(1, 2, 3);
Tuple<Integer> y = Tuple.create(1, 2, 3);

myTuples.add(x);
System.out.println("Set contains y: " + myTuples.contains(y)); // prints true

Если порядок имеет значение, вы можете использовать SortedSet.

Answer 3

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

public static void main (Строковые аргументы []) {

int[] x = new int[] {1, 2, 3};
int[] y = new int[] {1, 2, 3};

LinkedList<int[]> list = new LinkedList<int[]>(new Comparator<int[]>() {
  @Override
  public int compare(int[] a1, int[] a2) {
    if(a1 == a2) return 0;
    if(a1 == null && a2 != null) return -1;
    if(a1 != null && a2 == null) return 1;
    if(a1.size() < a2.size()) return -1;
    if(a1.size() > a2.size()) return 1;
    for(int i = 0; i < a1.size(); i++) {
      int comp = a1[i] - a2[i];
      if(comp < 0) return -1;
      if(comp > 0) return 1;
    }
    return 0;
  }
});

list.add(x);

System.out.println("List contains y: " + list.contains(y));

}

Answer 4

LinkedList использует equals для реализации contains, поэтому это должно работать:

public static void main(String args[]) {
    static class Ints {
        int[] array;
        public Ints(int[] array) {
            this.array = array;
        }
        public boolean equals(Object other) {
            if (other instanceof Ints) {
                return arraysEqual((Ints) other);
            }
        }
        public boolean arraysEqual(Ints other) {
            // check that this.array and other.array are same length and
            // have same values. Do a null check somewhere too. :)
        }
    }

    Ints x = new Ints(new int[] {1, 2, 3});
    Ints y = new Ints(new int[] {1, 2, 3});

    LinkedList<Ints> list = new LinkedList<int[]>();

    list.add(x);

    System.out.println("List contains y: " + list.contains(y));

}

Answer 5

Если бы вы могли использовать Set вместо массива, это могло бы быть проще. Посмотрите здесь или здесь

Answer 6

Возможно, вы захотите расширить LinkedList в свою собственную пользовательскую структуру данных и определить пользовательский метод равенства, если вы хотите что-то вне установленной стандартной проверки.