> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/20.-hashing-ii/20.4-mutable-vs.-immutable-types.md).

# 20.4 Mutable vs. Immutable Types

## Immutable Data Types

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

An immutable data type is one for which an instance cannot change in any observable way after instantiation.

Examples:

* Mutable: ArrayDeque, Percolation.
* Immutable: Integer, String, Date.

```java
public class Date {
   public final int month;
   public final int day;
   public final int year;
   private boolean contrived = true;
   public Date(int m, int d, int y) {
       month = m; day = d; year = y;
   }
}
```

The `final` keyword will help the compiler ensure immutability.

* `final` variable means you may assign a value once (either in the constructor of the class or in the initializer), but after it can never change.
* `final` is neither sufficient nor necessary for a class to be immutable.

### Advantages vs. Disadvantages of Immutability:

Advantage: Less to think about; avoids bugs and makes debugging easier.

* Analogy: Immutable classes have some buttons you can press / windows you can look inside. Results are ALWAYS the same, no matter what.

Disadvantage: Must create a new object anytime anything changes.

* Example: String concatenation is slow!

<figure><img src="/files/qw6FLS6JQxrXS3AwJmJy" alt=""><figcaption></figcaption></figure>

## Mutable Types

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

### **Mutable HashSet Keys**

In principle, we can create a HashSet\<List>.

Weird stuff happens if:

* We insert a List into a HashSet.
* We later mutate that List.

**Key Point**: Never mutate (modify) an object being used as a key. Incorrect results arise, and the item gets lost. [The slides for the Hashing II Lecture ](https://docs.google.com/presentation/d/1U_-RQCJB3j9B-k-kY8I4nS-FuxIvO8EgVIrOthx2InU/edit#slide=id.g2165b69ef3f_0_291)provide a very thorough visual example of this point.

### Actual Implementation of HashSet/Map in Java

In this last section, Professor Hug gives a quick walkthrough of the code for HashSets and HashMaps in Java's official implementation.

{% embed url="<https://youtu.be/pc5SDicUqWo>" %}