# 20.3 Contains & Duplicate Items

## Contains

{% embed url="https://www.youtube.com/watch?index=4&list=PL8FaHk7qbOD637Q-6p7nn5dKz1tK6WAjJ&v=O6UlxmISOx4" %}

### The `equals()` Method for a ColoredNumber Object

Suppose the `equals()` method for ColoredNumber is as below, i.e. two ColoredNumbers are equal if they have the same num.

```java
@Override
public boolean equals(Object o) {
   if (o instanceof ColoredNumber otherCn) {
       return this.num == otherCn.num;
   }
   return false;
}
```

### HashSet Behavior for Checking `contains()`

Suppose the `equals()` method for ColoredNumber is on the previous slide, i.e. two ColoredNumbers are equal if they have the same num.&#x20;

```java
int N = 20;
HashSet<ColoredNumber> hs = new HashSet<>();
for (int i = 0; i < N; i += 1) {
    hs.add(new ColoredNumber(i));
}
```

Suppose we now check whether 12 is in the hash table.

```java
ColoredNumber twelve = new ColoredNumber(12);
hs.contains(twelve); //returns true
```

{% hint style="info" %}
What do we **expect** to be returned by `contains`?
{% endhint %}

<details>

<summary>Answer</summary>

We expect the `contains` call to be true, all `12`s are created equal!

</details>

### Finding an Item Using the Default Hashcode

Suppose we are using the default hash function (uses memory address):

```java
int N = 20;
HashSet<ColoredNumber> hs = new HashSet<>();
for (int i = 0; i < N; i += 1) {
   hs.add(new ColoredNumber(i));
}
ColoredNumber twelve = new ColoredNumber(12);
hs.contains(twelve); // returns ??
```

which yields the table below:

![](https://lh4.googleusercontent.com/cFvLVhOYg31lSg1a8moftrr30qpThw3Bc7drJWVLNrSTCgTdO4yxjis1epmRlRMLWIkh73alL6OrblQxqGGrjMo1XMoOfPjSFH3tPDDbaxSbLXe1-HXJcfQOglsU4Dp74PiDDqMWXNOmYeQu_D7-l_B2SBcdTVohYMYLZdnzzMVn8_hAbvSKDAKyC-_ev3nN=s2048)

Suppose equals returns true if two ColoredNumbers have the same num (as we've defined previously).

{% hint style="info" %}
What is actually returned by `contains`?
{% endhint %}

<details>

<summary>Answer</summary>

Returns false with probability 5/6ths.

Default `hashCode()` is based on memory address. equals is based on `num`.

There are two ColoredNumber objects with `num = 12`. One of them is in the HashSet and one of them was created by the code above.

Each memory address is random, with only a 1/6th chance they modulo to the same bucket.

Example: If the `ColoredNumber` object `twelve` created by the code above is in memory location 6000000, its hashCode % 6 is 0. HashSet looks in bucket zero, and doesn't find 12.

</details>

{% hint style="info" %}
Hard Question: If the default hash code achieves a good spread, why do we even bother to create custom hash functions?&#x20;
{% endhint %}

<details>

<summary>Answer</summary>

It is necessary to have consistency between `equals()` and `hashCode()` for the hash table's operations to function.

</details>

**Basic rule (also definition of deterministic property of a valid hashcode):** If two objects are equal, they **must** have the same hash code so the hash table can find it.

## Duplicate Values

{% embed url="https://www.youtube.com/watch?index=5&list=PL8FaHk7qbOD637Q-6p7nn5dKz1tK6WAjJ&v=3HmCkRYsAGg" %}

### Overriding `equals()` but Not `hashCode()`

Suppose we have the same `equals()` method (comparing `num`), but we do not override `hashCode()`.

```java
public boolean equals(Object o) {
   ...  return this.num == otherCn.num; ...
}
```

The result of adding 0 through 19 is shown below:

![](https://content.gitbook.com/content/17YWK4wlHXK38A55HuVr/blobs/9C2aQBmw8JnTnVNjDbf3/image.png)

```java
ColoredNumber zero = new ColoredNumber(0);
hs.add(zero); // does another zero appear?
```

{% hint style="info" %}
Which can happen when we call add(zero)?

Answer Choices:

1. We get a 0 to bin zero.
2. We add another 0 to bin one.
3. We add a 0 to some other bin.
4. We do not get a duplicate zero
{% endhint %}

<details>

<summary>Answer </summary>

3 Choices are Correct:&#x20;

\#1, #3, #4.

We get a 0 to bin zero, We add a 0 to some other bin, and we do not get a duplicate zero.

The new zero ends up in a random bin.

* 5/6ths chance: In bin 0, 2, 3, 4, or 5. Duplicate!
* 1/6 chance: In bin 1, no duplicate! (`equals()` blocks it)

</details>

## Key Takeaway: `equals()` and `hashCode()`

Bottom line: If your class override equals, you should also override hashCode in a consistent manner.

* If two objects are equal, they must always have the same hash code.\


If you don’t, everything breaks:

* `Contains` can’t find objects (unless it gets lucky).
* `Add` results in duplicates.

