Determining Whether Two Collections Hold Identical Content

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 5.4 Free with a free account

Determining Whether Two Collections Hold Identical Content

Data Structures and Algorithms · Chapter 5: ArraysSection 5.4 · lesson 19 of 878 min · free with a free account

← Rows, Columns, and Higher DimensionsNext lesson: Copying Arrays Safely →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Compare Java arrays by content instead of by reference.

  • Distinguish reference identity from content equality for arrays
  • Use Arrays.equals for flat arrays and Arrays.deepEquals for nested arrays
  • Analyze the cost of an element-by-element comparison with early exit
  • Handle edge cases such as nulls, doubles and arrays of custom objects

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,094 words). Read along, or search it.

Opening Question

Same Sheet or Same Words

Picture two sheets of paper, each carrying the same recipe. They say the same thing, and yet they're two separate sheets. Now picture one sheet, with two names written on it. Ask, are these the same, and you might mean two different things. Is it the same sheet? Or does it say the same thing? With arrays, mixing those up gives wrong answers.

Key Idea

Identity Versus Content

An array variable doesn't hold the numbers. It holds a reference, a kind of address, that leads to the array object. Here, a and b are two arrays that both hold one, two, three. And c is a copy of the variable a, so it holds the same address. Run it. a equals equals b is false: two separate objects. a equals equals c is true: one object, two names. And a dot equals b is false too. Arrays inherit the most general equals, which only compares identity, just like double equals. Only the library method, Arrays dot equals, looks inside. Same length, same value at every index: true.

How It Works

Quick Checks Before the Element Loop

Arrays dot equals makes its decisions in a set order, from the quickest answer to the slowest. Same object? Then true, at once. Is either one null? Then false, unless both are. Different lengths? False. Only then does it compare the elements, index by index, and the first pair that differs means false. The quick checks cost almost nothing, so the slow element-by-element work only happens when the arrays could really match.

Nested Arrays

Why Deep Equals Exists

A two-dimensional array is an array whose elements are references to row arrays. That matters here. Arrays dot equals checks those row references for identity, just like double equals. It sees two different inner arrays, and answers false, even though every number matches. Arrays dot deep equals goes one level further. Whenever an element is itself an array, it compares that array's content too. True. Change one number deep inside q, and deep equals notices: false.

Compile Error

Deep Equals Rejects Flat Int Arrays

Deep equals is only for arrays that hold objects, such as arrays of arrays. Hand it two flat int arrays, and it won't compile. The compiler says an int array cannot be converted to an Object array. For flat arrays, Arrays dot equals is the right tool.

Worked Example

Counting Checks in a Hand-Written Comparison

Writing the comparison yourself shows exactly what the library does, and what it costs. This method follows the same steps, and counts every element check. Identity first, then null, then the lengths. The loop gives up at the first pair that differs. That's called an early exit. The test builds two arrays of a thousand numbers, and compares them in four situations. Same object, or different lengths: the answer comes with zero element checks. A difference at index five hundred costs five hundred one checks: indexes zero through five hundred. And identical content is the expensive case. All one thousand pairs must be checked.

Cost Analysis

Where the First Difference Sits

So the work depends on where the first difference sits. Same object, a null, or different lengths: constant work, whatever the size. A first difference at index k costs k plus one checks. Identical content is the worst case: n checks, growing in step with n. And no method can do better on identical arrays. Skip even one position, and a difference could hide there. That's why the cheap checks come first.

Quick Check

A Difference in the Last Slot

Quick check. Two arrays of two thousand numbers are all zeros, except that b's last slot holds seven. A method with the same steps compares them. How many element checks does it count? Pause and predict. Two thousand. The difference sits at index nineteen ninety-nine, so every pair from zero up to it is checked: nineteen ninety-nine plus one. One check would need the difference at index zero. Nineteen ninety-nine forgets that the last pair is checked too.

Edge Cases

Nulls, Empty Arrays and Different Lengths

A comparison earns trust on the unusual inputs. Arrays of different lengths are not equal. And a null never equals an array. Two null variables count as equal. Two empty arrays are equal too, because there's no pair that could differ. The danger is calling equals on a variable that is null. There's no object to run it on, so the program stops with a null pointer exception. The static form, Arrays dot equals, never fails that way. That's one more reason to prefer it.

Decimal Quirks

Not-a-Number and Negative Zero

Decimal numbers bring two quirks. For arrays of doubles, Arrays dot equals treats two not-a-number values as equal, though double equals says they aren't. And it treats zero and negative zero as different, though double equals calls them the same. It compares the stored bit patterns, not the arithmetic values.

Object Arrays

The Element Type's Equals Decides

When an array holds objects, each slot holds a reference too. So the same two questions come back, one level down. Arrays dot equals settles it by calling equals on each pair of elements. The element type decides what equal means. String compares characters. So these strings aren't the same objects, but they are equal, and so are the arrays. Nulls inside are safe as well. The library uses a null-aware comparison. If you write the loop yourself, call Objects dot equals, not first dot equals.

Custom Types

Teaching Point What Equal Means

A type you write yourself inherits the identity version of equals. Here's a point type, with no equals of its own. Two arrays hold points with identical coordinates, and Arrays dot equals says false. Every point is a different object, and identity can't see coordinates. The fix is to teach the type what equal means. Override equals: the same object is equal, something that isn't a point never is, and otherwise compare both coordinates. Run the same test again, and it prints true. The array code didn't change at all. A type that overrides equals should also override hash code. The reason belongs with hashing, in chapter fourteen.

Quick Check

Two Outer Arrays Sharing One Row

One more check. This program makes one small row, and builds two outer arrays that each hold that same row, twice. It compares them with plain Arrays dot equals, not deep equals. What does it print? Pause and predict. It prints true. Arrays dot equals compares the rows by identity, and here every row is the very same object. False needs separate row arrays, as in the earlier grid. And the call compiles, because an array of int arrays is an array of objects.

Key Takeaways

Comparing Arrays in Summary

To sum up. Double equals and an array's own equals compare references, not content. Arrays dot equals compares length and every value. Deep equals also opens inner arrays. A hand-written comparison exits at the first difference, and needs all n checks for identical arrays. And for arrays of objects, the element type's equals decides, so your own types need one.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Determining Whether Two Collections Hold Identical Content

How do you compare two arrays in Java?
Use Arrays.equals(a, b), which returns true when both arrays have the same length and the same value at every index. Neither a == b nor a.equals(b) works for this, because both compare references, so two separate arrays holding 1, 2, 3 give false. Arrays.equals also handles nulls safely: two null references count as equal, and a null never equals an array.
What is the difference between Arrays.equals and Arrays.deepEquals?
Arrays.equals compares elements one level deep, so for a two-dimensional array it checks whether the row references are the same objects and returns false for separate rows holding identical numbers. Arrays.deepEquals opens any element that is itself an array and compares its content. deepEquals accepts only arrays of objects, so passing it two flat int arrays does not compile.
How long does it take to compare two arrays?
Comparing two arrays of length n takes constant time when they are the same object, one is null or their lengths differ. Otherwise, a comparison with an early exit stops at the first differing pair, so a difference at index k costs k + 1 checks. Identical content is the worst case and needs all n checks, because skipping any position could hide a difference.
Why does Arrays.equals return false for arrays of my own objects?
Arrays.equals calls equals on each pair of elements, and a class that does not override equals inherits the identity version, which is true only for the very same object. Two Point objects with identical coordinates are therefore unequal. Override equals in the class to compare the fields, and override hashCode as well, so that equal objects produce the same hash code.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →