# 19.7 Exercises

## 1. Potpourri

(a) True or False: Resizes are triggered if adding a key-value pair causes the load factor to be greater than or equal to the specified maximum load factor.

<details>

<summary>Answer to Q1(a)</summary>

**False**. A resize will be triggered if adding another key value pair would cause the load factor to **exceed** the specified maximum load factor. A resize is not triggered when the load factor is equal to the specified maximum load factor.

</details>

(b) True or False: The `hashCode()` function can have varied return types.

<details>

<summary>Answer to Q1(b)</summary>

**False**. In Java, the hashCode() function can **only** have an `int` return type to serve as a hash value.

</details>

## 2. hashCode()....

In order for a hash code to be valid, objects that are equivalent to each other (i.e. .equals() returns true) must return equivalent hash codes. If an object does not explicitly override the `hashCode()` method, it will inherit the `hashCode()` method defined in the Object class, which returns the object’s address in memory.

Here are four potential implementations of Integer's `hashCode()` function. Assume that `intValue()` returns the value represented by the Integer object.&#x20;

Categorize each `hashCode()` implementation as either a valid or an invalid hash function. If it is valid, point out a flaw or disadvantage. If it is invalid, explain why.&#x20;

Question (a)

```java
public int hashCode() {
    return -1;
}
```

<details>

<summary>Answer for Q2(a)</summary>

Valid. As required, this hash function returns the same hash code for Integers that are .equals() to each other. However, this is a terrible hash code because collisions are extremely frequent and occur 100% of the time.

</details>

Question (b)

```java
public int hashCode() {
    return intValue() * intValue();
}
```

<details>

<summary>Answer for Q2(b)</summary>

Valid. Similar to (a), this hash function returns the same hash code for Integers that are .equals(). However, Integers that share the same absolute values will collide (for example, x = 5 and x = -5 will both return the same hashcode). A better hash function would be to just return intValue() itself.

</details>

Question (c)

```java
public int hashCode() {
    Random rand = new Random();
    return rand.nextInt();
}
```

<details>

<summary>Answer for Q2(c)</summary>

Invalid. If we call hashCode() multiple times on the same Integer object, we will get different hash codes returned each time.

</details>

Question (d)

```java
public int hashCode() {
    return super.hashCode();
}
```

<details>

<summary>Answer for Q2(d)</summary>

Invalid. This hash function returns some integer corresponding to the Integer object’s location in memory. Different Integer objects will exist in different locations in memory, so even if they represent the same value they will return different hash codes.

</details>

## 3. Hashin' and Resizin'

Given the provided `hashCode()` implementation, hash the items listed below with external chaining (the first item is already inserted for you). Assume the load factor is 1, and the initial underlying array has size of 4. Use geometric resizing with a resize factor of 2. You may draw more boxes to extend the array when you need to resize.

```java
/** Returns 0 if word begins with ’a’, 1 if it begins with ’b’, etc. */
public int hashCode() {
    return word.charAt(0) - 'a';
}
```

```
["apple", "cherry", "fig", "guava", "durian", "apricot", "banana"]
```

<details>

<summary>Answer for Question 3</summary>

Here is what the hash table should look like after inserting `guava`:

![](/files/FEbpJApsLY8QhMrjAI4Y)

Here is what the hash table should look like after inserting `durian`:

![](/files/9UqnbW0LWfWIkLg7x7fP)

Here is what the hash table should look like after all insertions have been completed:

![](/files/PEnFjwRDDOBB6TraZOsG)

</details>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook/19.-hashing-i/19.7-exercises.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.