Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #35457 > unrolled thread

ArrayList vs HashMap

Back to article view | Back to comp.lang.java.programmer

Contents

  ArrayList vs HashMap Roedy Green <inquiry@mindprod.com> - 2016-08-25 09:42 -0700
    Re: ArrayList vs HashMap Roedy Green <inquiry@mindprod.com> - 2016-08-25 09:43 -0700
      Re: ArrayList vs HashMap Eric Douglas <e.d.programmer@gmail.com> - 2016-08-25 10:06 -0700
        Re: ArrayList vs HashMap Roedy Green <inquiry@mindprod.com> - 2016-08-30 16:34 -0700
          Re: ArrayList vs HashMap Andreas Leitgeb <avl@logic.at> - 2016-08-31 12:55 +0000
            Re: ArrayList vs HashMap Eric Sosman <esosman@comcast-dot-net.invalid> - 2016-08-31 13:05 -0400
              Re: ArrayList vs HashMap Andreas Leitgeb <avl@logic.at> - 2016-08-31 17:34 +0000
    Re: ArrayList vs HashMap j4n bur53 <janburse@fastmail.fm> - 2016-08-31 09:15 +0200

#35457 — ArrayList vs HashMap

Hash anyone ever experimented to find a rule of thumb about what sizes
lookup should be done with ArrayList and which with HashMap?

[toc] | [next] | [standalone]

#35458

On Thu, 25 Aug 2016 09:42:04 -0700, Roedy Green <inquiry@mindprod.com>
wrote:

>Hash anyone ever experimented to find a rule of thumb about what sizes
>lookup should be done with ArrayList and which with HashMap?
 I guess I really mean ArrayList vs HashSet.

[toc] | [prev] | [next] | [standalone]

#35459

On Thursday, August 25, 2016 at 12:43:43 PM UTC-4, Roedy Green wrote:
> >Hash anyone ever experimented to find a rule of thumb about what sizes
> >lookup should be done with ArrayList and which with HashMap?
>  I guess I really mean ArrayList vs HashSet.

Sizes?  Can you be more specific?  Generally these classes are for very different purpose.  An ArrayList is just a list of items.  A HashSet is a list of unique items.  A HashMap is a list of unique items with correlated values...

[toc] | [prev] | [next] | [standalone]

#35499

On Thu, 25 Aug 2016 10:06:37 -0700 (PDT), Eric Douglas
<e.d.programmer@gmail.com> wrote:

>Sizes?  Can you be more specific?  Generally these classes are for very different purpose.
  An ArrayList is just a list of items.  A HashSet is a list of unique
items.  A HashMap is a list of unique items with correlated values...

 Lets say the only operation you will do is .contains to see if a
element is in the set.

[toc] | [prev] | [next] | [standalone]

#35521

Stefan Ram <ram@zedat.fu-berlin.de> wrote:
>   A HashSet, on the other hand, has a nicer interface for
>   programmers, so one should write an »ArraySet implements Set«
>   wrapper for ArrayLists (unless such a thing should already exist).

Unless I missed something, the interface Set doesn't add any method,
that isn't already in Collection.

If it weren't for Set's specific semantics of add(o) where o was
already contained, then ArrayList would "already be a Set".

[toc] | [prev] | [next] | [standalone]

#35526

On 8/31/2016 8:55 AM, Andreas Leitgeb wrote:
> Stefan Ram <ram@zedat.fu-berlin.de> wrote:
>>   A HashSet, on the other hand, has a nicer interface for
>>   programmers, so one should write an »ArraySet implements Set«
>>   wrapper for ArrayLists (unless such a thing should already exist).
>
> Unless I missed something, the interface Set doesn't add any method,
> that isn't already in Collection.
>
> If it weren't for Set's specific semantics of add(o) where o was
> already contained, then ArrayList would "already be a Set".

     There's also the matter of equals() and hashCode() semantics:

	Set<String> s1 = new HashSet<>();
	Set<String> s2 = new TreeSet<>();
	s1.add("Hello");  s1.add("World");
	s2.add("World");  s2.add("Hello");
	assert s1.equals(s2);
	assert s1.hashCode() == s2.hashCode();

	List<String> l1 = new ArrayList<>();
	List<String> l2 = new LinkedList<>();
	l1.add("Hello");  l1.add("World");
	l2.add("World");  l2.add("Hello");
	assert !l1.equals(l2);
	assert l1.hashCode() != l2.hashCode();  // probably

-- 
esosman@comcast-dot-net.invalid
The Tooth Fairy has gone high-tech, now pays in Bitecoin.

[toc] | [prev] | [next] | [standalone]

#35528

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:
> On 8/31/2016 8:55 AM, Andreas Leitgeb wrote:
>> Stefan Ram <ram@zedat.fu-berlin.de> wrote:
>>>   A HashSet, on the other hand, has a nicer interface for
>>>   programmers, so one should write an »ArraySet implements Set«
>>>   wrapper for ArrayLists (unless such a thing should already exist).
>>
>> Unless I missed something, the interface Set doesn't add any method,
>> that isn't already in Collection.
>>
>> If it weren't for Set's specific semantics of add(o) where o was
>> already contained, then ArrayList would "already be a Set".
>
>      There's also the matter of equals() and hashCode() semantics:
>
> 	Set<String> s1 = new HashSet<>();
> 	Set<String> s2 = new TreeSet<>();
> 	s1.add("Hello");  s1.add("World");
> 	s2.add("World");  s2.add("Hello");
> 	assert s1.equals(s2);
> 	assert s1.hashCode() == s2.hashCode();
>
> 	List<String> l1 = new ArrayList<>();
> 	List<String> l2 = new LinkedList<>();
> 	l1.add("Hello");  l1.add("World");
> 	l2.add("World");  l2.add("Hello");
> 	assert !l1.equals(l2);
> 	assert l1.hashCode() != l2.hashCode();  // probably

True - my mistake. The "add" method isn't the only one with a Set-specific
contract.

But as long as only containment is of interest, one could just work with
any collection (rather than demanding a set).

PS: for sets of ints of limited range there is also the BitSet.

[toc] | [prev] | [next] | [standalone]

#35513

Roedy Green schrieb:
> Hash anyone ever experimented to find a rule of thumb about what sizes
> lookup should be done with ArrayList and which with HashMap?

The Java compiler implements some rule of thumbs
in its switch statement compilation. It has two
options to emit a scan or an index lookup byte
code instruction.

Similarly you can use an array list to scan
and implement a map. Just store key value pairs
or distribute the keys and values along array
elements, resulting in an array of double size.

Here is the Java heuristic:
http://stackoverflow.com/a/31032054/502187

This doesn't directly answer your question, but
I have a similar case between ArrayList
and HashSet, and simply used threshold on the number
of key value pairs which I determined empirically.
There is not only a time tradeoff but also a
space tradeoff.

Since using less space was also important for
me I was choosing a higher threshold of 12
key value pairs or so. Otherwise I would use 8
key value pairs or so.

Bye

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web