Хранение массивов в Set и избежание дубликатов - PullRequest
Новая
       26

Хранение массивов в Set и избежание дубликатов

25 голосов
/ 20 сентября 2011 
HashSet<String[]> boog = new HashSet<String[]>();
boog.add(new String[]{"a", "b", "c"});
boog.add(new String[]{"a", "b", "c"});
boog.add(new String[]{"a", "b", "d"});

приводит к 

[a, b, c]
[a, b, d]
[a, b, c]

, где [a,b,c] повторяется, поэтому хэш-функция не работает должным образом.Как бы я переопределил метод Hash для массивов String.Или в этом отношении универсальный массив?Есть ли лучший способ выполнить то, что я пытаюсь сделать?

Ответы [ 5 ]

32 голосов
/ 20 сентября 2011

Вы не можете. массивы используют стандартную реализацию Object.hashCode (), основанную на идентичности, и вы не можете переопределить это. Не используйте массивы в качестве ключей в HashMap / HashSet!

Вместо этого используйте набор списков.

24 голосов
/ 20 сентября 2011

«Лучшим способом» является использование коллекций.Используйте List вместо String[]: 

Set<List<String>> boog = //...
boog.add(Arrays.asList("a", "b", "c"));
boog.add(Arrays.asList("a", "b", "c"));
boog.add(Arrays.asList("a", "b", "d"));

System.out.println(boog.size()); // 2

Edit

Если вам абсолютно необходимо использовать массивы в качестве ключей, вы можете построить прозрачную оболочку вокруг каждого ключа и поместить этона карте.Некоторые библиотеки помогут вам в этом.Например, вот как вы можете сделать Set<String[]>, используя Trove : 

Set<String[]> boog = new TCustomHashSet<String[]>(new ArrayHashingStrategy());

boog.add(new String[]{"a", "b", "c"});
boog.add(new String[]{"a", "b", "c"});
boog.add(new String[]{"a", "b", "d"});

System.out.println(boog.size()); // 2

//...
public class ArrayHashingStrategy extends HashingStrategy<Object[]> {

   public int computeHashCode(Object[] array) {
      return Arrays.hashCode(array);
   }

   public boolean equals(Object[] arr1, Object[] arr2) {
      return Arrays.equals(arr1, arr2);
   }
}
4 голосов
/ 20 сентября 2011

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

Вместо этого вы можете использовать List, с hashCode() рассчитывается на основе хеш-кодов его элементов.ArrayList (как и в большинстве реализаций) использует такую ​​функцию.

В качестве альтернативы (но менее предпочтительно, если вы не вынуждены каким-либо образом использовать массивы), вы можете использовать «специальный» HashSet, где вместовызов key.hashCode() вызов Arrays.hashCode(array).Для реализации этого расширения HashMap, а затем используйте Collections.newSetFromMap(map)

1 голос
/ 20 сентября 2011

Вы на самом деле используете метод hashCode по умолчанию, возвращающий разные значения для всех ваших разных массивов!

Лучший способ решить эту проблему - использовать Collection (например, List или Set) или определить собственный класс-оболочку, например: 

public class StringArray {
    public String[] stringArray;

    [...] // constructors and methods

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        for(String string : stringArray){
            result = prime * result + ((string == null) ? 0 : string.hashCode());
        }
    }
}

Этот класс на самом деле использует тот же самый метод hashCode, что и метод для List.

Теперь вы обрабатываете: 

HashSet<StringArray> boog = new HashSet<StringArray>();
0 голосов
/ 23 апреля 2015

На самом деле, вы можете.Вы можете использовать TreeSet при условии Comparator.В вашем случае это будет что-то вроде: 

Set<String[]> boog = new TreeSet<>((o1, o2) -> {
    for (int i = 0; i < o1.length; i++){
        int cmp = o1[i].compareTo(o2[i]);
        if (cmp != 0) {
            return cmp;
        }
    }
    return o1.length - o2.length;
});

Под капотом будет выглядеть сортированное по алфавиту дерево.

...