8

I was working with a HashSet the other day, which has this written in the spec:

[add()] adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2))

I was using char[] in the HashSet until I realized that, based on this contract, it was no better than an ArrayList! Since it's using the non-overridden .equals(), my arrays will only be checked for reference equality, which is not particularly useful. I know that Arrays.equals() exists, but that doesn't help when one is using collections such as HashSet.

So my question is, why would Java arrays not override equals?

  • 3
    mixing native arrays and collection isn't really advisable – ratchet freak May 15 '14 at 11:17
  • 1
    It's the principle of the matter, I think. An array is the second most primitive imperative data structure after mutable variables. It's merely n memory slots big enough to each hold some value of type T glued sequentially. They're the building blocks for more sophisticated ephemeral collections. What you wanted was a List. – Doval May 15 '14 at 11:24
  • 1
    @ratchetfreak I've often heard people say that, but never why. Why is it a bad idea? – Richard Tingle May 15 '14 at 12:36
  • @RichardTingle Arrays don't always mix well with generics, arrays aren't Iterable, their toString() representation is mostly useless, and there's almost no advantage to ever using one over an ArrayList. – Doval May 15 '14 at 12:39
  • @Doval But those are all reasons to not use arrays at all (which I would agree with 95% of the time). Sometimes I need to use arrays because they play nice with 3D graphics but I want to map a key to them. So Map<Key, int[]> has always felt natural. But I'm always nervous that there is something horrible waiting for me – Richard Tingle May 15 '14 at 12:43
8

There was a design decision to make early on in Java:

Are arrays primitives? or are they Objects?

The answer is, neither really... or both if you look at it another way. They work fairly closely with the system itself and the backend of the jvm.

One example of this is the java.lang.System.arraycopy() method which needs to take an array of any type. Thus, the array needs to be able to inherit something and thats an Object. And arraycopy is a native method.

Arrays are also funny in that they can hold primitives (int, char, double, etc... while the other collections can only hold Objects. Look, for example, at java.util.Arrays and the ugly of the equals methods. This was put in as an after thought. deepEquals(Object[], Object[]) wasn't added until 1.5 while the rest of the Arrays class was added in 1.2.

Because these objects are arrays, they let you do some things that are at the memory or near memory level - something that Java often hides from the coder. This allows certain things to be done faster at the expense of mostly breaking the object model.

There was a trade off early in the system between flexibility and some performance. Performance won out and the lack of flexibility was wrapped in the various collections. Arrays in Java are a thinly implemented Object on top of a primitive type (originally) intended for working with the system when you need it.

For the most part, raw arrays were things that it appears that the original designers tried to ignore and tuck away only in the system. And they wanted it to be fast (early Java had some issues with speed). It was a wart on the design that arrays aren't nice Arrays, but its one that was needed when you wanted to expose something as close to the system as possible. For that matter, the contemporary languages of early Java also have this wart - one can't do a .equals() on C++'s array.

Java and C++ both took the same path for arrays - an external library that does the operations as needed on arrays rather than Arrays... and suggesting the coders to use better, native types unless they really know what they are doing and why they are doing it that way.

Thus, the approach implanting .equals in an array is wrong, but its the same wrong that coders coming from C++ knew of. So chose the least wrong thing in terms of the performance - leave it as the implementation of Object: two Objects are equal if and only if they are referring to the same object.

You need the array to be a primitive like structure for being able to communicate with native bindings - something as close to the classic C array as possible. But unlike the other primitives, you need the array to be able to be passed as a reference, and thus an Object. So its more of a primitive with some Object hacks on the side and some bounds checking.

  • +1 and thanks for the answer. This was what I was really looking for, the design perspective behind the decision, not just that it's a bad idea. – Azar May 15 '14 at 17:18
  • 1
    @Azar there is some discussion at C2: Java Arrays Should Be First Class Objects which has some code that shows some of the hackery that goes on behind the scenes with an array... along with others bemoaning that arrays aren't nice Objects. – user40980 May 15 '14 at 17:33
  • 2
    Fortunately for C++ making a smarter array class does not require boxing. Java is not so fortunate. – Thomas Eding May 16 '14 at 0:13
3

In Java, arrays are pseudo-objects. Object references can hold arrays, and they do have the standard Object methods, but they are very lightweight compared to a true collection. Arrays do just enough to meet the contract of an Object and use the default implementations of equals, hashCode, and toString quite deliberately.

Consider an Object[]. An element of this array can be anything that fits in an object, which includes another array. It could be a boxed primitive, a socket, anything. What does equality mean in that case? Well, it depends on what is actually in the array. That is not something known in the general case when the language was being designed. Equality is defined both by the array itself as well as its contents.

This is the reason why there is an Arrays helper class that has methods to compute equality (including deep equals), hash codes, etc. However, those methods are well-defined as far as what they do. If you need different functionality, write your own method to compare two arrays for equality based on the needs of your program.


While not strictly an answer to your question, I think it is relevant to say that you really should be using collections instead of arrays. Only convert to an array when interfacing with an API that requires arrays. Otherwise, collections offer better type safety, more well-defined contracts, and are generally easier to use than arrays.

  • Arrays are real objects. The fact that they are the only multi-element aggregate type means any other forms variable-sized collection must be backed by either arrays or else O(N) objects outside itself, so by comparison arrays will be "lightweight". I think the more fundamental issue is not that arrays are lightweight, but rather that there are so many ways of using them. See my answer below. – supercat Jun 14 '14 at 16:42
  • 1
    "What does equality mean in that case?"- um, how about that the arrays have to the same length, plus every object at every index in both the source and target must be equal according to the contract of equals()? seems like what you'd expect, and is the exact contract implemented by Arrays.equals(). – Jeffrey Blattman Sep 18 '14 at 19:52
  • @JeffreyBlattman - what happens, then, if an Object array contains itself? – Jules Sep 27 '15 at 19:58
  • @JeffreyBlattman then take it up with the authors of the language who implemented reference equality for arrays, but provided Arrays.equals() for deep equality. – user22815 Sep 28 '15 at 2:05
  • @Jules "what happens, then, if an Object array contains itself?" the same thing that happens if an object contains itself. if you implement a naive equals, then you'll get stack overflow. – Jeffrey Blattman Sep 28 '15 at 16:16
1

The fundamental difficulty with arrays overriding equals is that a variable of a type like int[] may be used in at least three fundamentally different ways, and the meaning of equals should vary depending upon usage. In particular, a field of type int[]...

  1. ...may encapsulate a sequence of values in an array which will never be modified, but may be shared freely with code that won't modify it.

  2. ...may encapsulate exclusive ownership of an integer-holding container which may be mutated at will by its owner.

  3. ...may identify an integer-holding container which some other entity is using to encapsulate its state, and thus serve as a connection to the state of that other entity.

If a class has an int[] field foo which is used for either of the first two purposes, then instances x and y should regard x.foo and y.foo as encapsulating the same state if they hold the same sequence of numbers; if the field is used for the third purpose, however, then x.foo and y.foo would only encapsulate the same state if they identify the same array [i.e. they're reference equal]. If Java had included different types for the three usages above, and if equals took a parameter identifying how the reference was being used, then it would have been appropriate for int[] to use sequence equality for the first two usages and reference equality for the third. No such mechanism exists, however.

Note also that the int[] case was the simplest kind of array. For arrays containing references to classes other than Object or array types, there would be additional possibilities.

  1. A reference to a sharable unchanging array which encapsulates things that will never change.

  2. A reference to a sharable unchanging array which identifies things owned by other entities.

  3. A reference to an exclusively-owned array which encapsulates references to things that will never change.

  4. A reference to an exclusively-owned array which encapsulates references to exclusively-owned items.

  5. A reference to an exclusively-owned array which identifies things owned by other entities.

  6. A reference that identifies an array owned by some other entity.

In cases 1, 3, and 4, two array references should be considered equal if corresponding items are "value-equal". In cases 2 and 5, two array references should be considered equal if they identify the same sequence of objects. In case 6, two array references should be considered equal only if they identify the same array.

For equals to behave sensibly with aggregate types, they need to have some way of knowing how references will be used. Unfortunately, Java's type system has no way of indicating that.

-2

Overriding array equals() and hashCode() to depend on content would make them similar to collections - mutable types with non-constant hashCode(). Types with changing hashCode() behave poorly when stored in hash-tables and other applications relying on hashCode() fixed value.

Set<List<Integer>> data = new HashSet<List<Integer>>();
List<Integer> datum = new ArrayList<Integer>();
datum.add(1);
data.add(datum);
assert data.contains(datum); // true
datum.add(2);
assert data.contains(datum); // false, WAT???

Arrays on other hand has trivial hashCode(), can be used as hash-table keys and are still mutable.

Set<int[]> data = new HashSet<int[]>(67);
int[] datum = new int[]{1, 2};
data.add(datum);
System.out.println(data.contains(datum)); //true
datum[0] = 78;
System.out.println(data.contains(datum)); //true
//PROFIT!!!
  • 3
    There is no array in there. The int[] type array. – user40980 May 15 '14 at 14:20
  • @MichaelT, that's the point. – Basilevs May 15 '14 at 14:27
  • Why the downvotes? The answerer did a lot of work. Is something wrong? – Tom Au May 15 '14 at 16:00
  • 3
    @TomAu the question is about the design of the array in java, and its psuedo-object nature and the design decisions behind that choice (to make the array only use referential equality rather than a deep equality). This answer, on the other hand, tries to present a code solution for how the code could be rewritten - which isn't what the question asks. – user40980 May 15 '14 at 16:27
  • @MichaelT, this illustrates identity-based equality logic proficiency over state-dependent one. – Basilevs May 15 '14 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.