Best way to check if all elements in a List are unique
in [Java Programming]
|
From: Roedy Green on 1 Mar 2010 22:03 On Mon, 1 Mar 2010 14:29:29 -0800 (PST), laredotornado <laredotornado(a)zipmail.com> wrote, quoted or indirectly quoted someone who said : > >I"m using Java 1.5. Given a java.util.List that I know to have at >least one element, what is the best way to check that all elements in >the list are unique ? http://mindprod.com/jgloss/hashset.html -- Roedy Green Canadian Mind Products http://mindprod.com The major difference between a thing that might go wrong and a thing that cannot possibly go wrong is that when a thing that cannot possibly go wrong goes wrong it usually turns out to be impossible to get at or repair. ~ Douglas Adams (born: 1952-03-11 died: 2001-05-11 at age: 49)
From: John B. Matthews on 1 Mar 2010 23:33 In article <hmhim4$n8d$1(a)news.eternal-september.org>, "Mike Schilling" <mscottschilling(a)hotmail.com> wrote: > John B. Matthews wrote: > > In article > > <95bd0b1b-e372-4981-a6cf-eed5a58e4461(a)u19g2000prh.googlegroups.com>, > > laredotornado <laredotornado(a)zipmail.com> wrote: > > > >> I'm using Java 1.5. Given a java.util.List that I know to have at > >> least one element, what is the best way to check that all elements > >> in the list are unique ? > > > > You should be able to construct a Set, say TreeSet, of the List > > elements and see if the sizes match. > > TreeSet requires the elements be comparable. HashSet will work for > any element type. Good points; but if the elements are Comparable (or admit a Comparator), TreeMap won't require re-hashing. The Set interface promises "no duplicate elements," but there are a number of implementations that I've never used. Dave: Any requirements that might suggest a preference? -- John B. Matthews trashgod at gmail dot com <http://sites.google.com/site/drjohnbmatthews>
From: Mike Schilling on 2 Mar 2010 00:06 John B. Matthews wrote: > In article <hmhim4$n8d$1(a)news.eternal-september.org>, > "Mike Schilling" <mscottschilling(a)hotmail.com> wrote: > >> John B. Matthews wrote: >>> In article >>> <95bd0b1b-e372-4981-a6cf-eed5a58e4461(a)u19g2000prh.googlegroups.com>, >>> laredotornado <laredotornado(a)zipmail.com> wrote: >>> >>>> I'm using Java 1.5. Given a java.util.List that I know to have at >>>> least one element, what is the best way to check that all elements >>>> in the list are unique ? >>> >>> You should be able to construct a Set, say TreeSet, of the List >>> elements and see if the sizes match. >> >> TreeSet requires the elements be comparable. HashSet will work for >> any element type. > > Good points; but if the elements are Comparable (or admit a > Comparator), TreeMap won't require re-hashing. But the HashSet shouldn't require expansion, since it knows the maximum number of elements it will hold, while the TreeSet may require rebalancing. And rehashing is more or less free if the objects precompute their hash (like Strings) or use the default "identity" hash. I'd like to see numbers before concluding that TreeMap is cheaper.
From: John B. Matthews on 2 Mar 2010 01:34 In article <hmi6dh$cjm$1(a)news.eternal-september.org>, "Mike Schilling" <mscottschilling(a)hotmail.com> wrote: > John B. Matthews wrote: > > In article <hmhim4$n8d$1(a)news.eternal-september.org>, > > "Mike Schilling" <mscottschilling(a)hotmail.com> wrote: > > > >> John B. Matthews wrote: > >>> In article > >>> <95bd0b1b-e372-4981-a6cf-eed5a58e4461(a)u19g2000prh.googlegroups.com>, > >>> laredotornado <laredotornado(a)zipmail.com> wrote: > >>> > >>>> I'm using Java 1.5. Given a java.util.List that I know to have > >>>> at least one element, what is the best way to check that all > >>>> elements in the list are unique ? > >>> > >>> You should be able to construct a Set, say TreeSet, of the List > >>> elements and see if the sizes match. > >> > >> TreeSet requires the elements be comparable. HashSet will work > >> for any element type. > > > > Good points; but if the elements are Comparable (or admit a > > Comparator), TreeMap won't require re-hashing. > > But the HashSet shouldn't require expansion, since it knows the > maximum number of elements it will hold, That makes sense. The API even promises "an initial capacity sufficient to contain the elements in the specified collection." > while the TreeSet may require rebalancing. And rehashing is more or > less free if the objects precompute their hash (like Strings) or use > the default "identity" hash. Or the OP may need some feature of another implementation, making it the preferred choice. > I'd like to see numbers before concluding that TreeMap is cheaper. I'd like to see a problem before resorting to that! -- John B. Matthews trashgod at gmail dot com <http://sites.google.com/site/drjohnbmatthews>
From: Eric Sosman on 2 Mar 2010 08:59
On 3/1/2010 5:29 PM, laredotornado wrote: > Hi, > > I"m using Java 1.5. Given a java.util.List that I know to have at > least one element, what is the best way to check that all elements in > the list are unique ? As others have said, it depends on what you mean by "best." It *also* depends on what you mean by "unique!" For example, how many "unique" elements are in List<String> list = new ArrayList<String>(); for (int i = 0; i < 100; ++i) list.add(new String("unique")); ? Both "one" and "one hundred" are reasonable answers. -- Eric Sosman esosman(a)ieee-dot-org.invalid |