How to implement a hash table in Java (Part 2)
Tags: java, testing, algorithms, programming
Published: 2022-10-14 10:34:36

In the [first post](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd) of this series we've implemented the initial version of our hash table. The current implementation allows for "putting" and "getting" mappings. But it is only possible to do so in a very limited set of conditions; the previous post focused on implementing [happy path](https://en.wikipedia.org/wiki/Happy_path) test cases.

In this second post of the series we'll start to deviate from that path. We will do it in a incremental manner, as we have been working so far.

In this post we will add test cases that:

- uses keys having negative hash code values;
- replaces the value of an existing mapping; and
- have the `get` method handle non-existing keys. 

Let's continue.

## Before we continue

While not strictly required, I recommend reading the [first part](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd) of this series if you haven't already. The ["Writing style"](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#writing-style) section, in particular, explains why the examples are written the way they are.

## Iteration 05: support negative hash code values

Up until this point, we have been working with keys having positive hash code values.

Let's introduce keys with negative hash code values.

### Iteration 05: test case

Let's start with a test case:

```java
public class HashTableTest {
  @Test(description = """
  put() & get() methods

  - negative hash code
  """)
  public void iter05() {
    var ht = new HashTable<Integer, String>();
    assertEquals(ht.size(), 0);

    assertEquals(ht.put(-1, "Minus One"), null);
    assertEquals(ht.size(), 1);
    assertEquals(ht.get(-1), "Minus One");

    assertEquals(ht.put(-2, "Minus Two"), null);
    assertEquals(ht.size(), 2);
    assertEquals(ht.get(-2), "Minus Two");
  }
}
```

It is a variation of [the test](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#iteration-04-test-case) written in the previous iteration. The difference is that the keys are guaranteed to produce negative hash code values.

### Iteration 05: running our test

Let's run this new test with the implementation from the previous iteration:

```
java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 4
	at iter03.HashTable.put0(HashTable.java:33)
	at iter02.HashTable.put(HashTable.java:25)
	at iter05.HashTableTest.iter05(HashTableTest.java:32)
```

It fails as it tries to insert the key at a negative array index.

This is expected. We [mentioned it](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#iteration-03-the-raw-bucket-endraw-method) during iteration #03.

The problem is in our current `bucket` method implementation:

```java
// current implementation
protected int bucket(Object key) {
  var hc = key.hashCode();

  return hc % keys.length;
}
```

If a key's hash code is negative then the method result will also be negative.

### Iteration 05: implementation

To prevent the method from returning a negative value, we can use the absolute value of the key's hash code instead: 

```java
public class HashTable<K, V> extends iter04.HashTable<K, V> {
  @Override
  protected int bucket(Object key) {
    int hc = key.hashCode();

    return Math.abs(hc) % keys.length;
  }
}
```

It works. Our test passes.

## Iteration 06: distinct hash code values having the same absolute value

As mentioned in this post's introduction, our objective is to incrementally deviate from the happy path. 

In the previous iteration, the keys of both mappings we added to our map:

- had the same sign, both were negative; and
- had different absolute values.
 
Let's, in this iteration, do something a little different. We will, once more, add two mappings. But the key's hash code values:

- will have distinct signs, i.e., one will be positive and the other negative; and
- will have the _same_ absolute value.

### Iteration 06: test case

Here's our test case:

```java
public class HashTableTest {
  @Test(description = """
  put() & get() methods

  - negative hash code
  - positive hash code
  """)
  public void iter06() {
    var ht = new HashTable<Integer, String>();
    assertEquals(ht.size(), 0);

    assertEquals(ht.put(-3, "Minus Three"), null);
    assertEquals(ht.size(), 1);
    assertEquals(ht.get(-3), "Minus Three");

    assertEquals(ht.put(3, "Three"), null);
    assertEquals(ht.size(), 2);
    assertEquals(ht.get(3), "Three");
  }
}
```

It is very similar to the last few tests. Except the keys were selected so their hash code values meet our requirements.  

### Iteration 06: running our test

Let's run this test with the implementation from the previous iteration:

```
java.lang.UnsupportedOperationException: Implement me
	at iter03.HashTable.put1(HashTable.java:43)
	at iter03.HashTable.put0(HashTable.java:39)
	at iter02.HashTable.put(HashTable.java:25)
	at iter06.HashTableTest.iter06(HashTableTest.java:37)
```

It fails as it reaches a branch of our code we did not implement yet. We can see from the stack trace it is a code written during iteration #03.

### Iteration 06: hash collision

The current test failure is expected. We mentioned it in the ["same key or collision?"](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#iteration-03-same-key-or-collision) section of the previous post.

Remember that, in the previous iteration, we fixed the negative array index issue by using the absolute value of the key's hash code. But, in doing so, it caused a positive and a negative hash code having the same absolute value to yield the same "bucket".

Take, for example, two distinct keys `A` and `B` having the following hash code values:

- `A = +2`
- `B = -2`

As the following is our current `bucket` implementation:

```java
int hc = key.hashCode();

return Math.abs(hc) % keys.length;
```

Both keys will be put in the same "bucket". When `keys.length` is `4`, for example, both keys will be put at the `bucket = 2`.

When two _distinct keys_ produce the same "bucket" it configures a situation called [hash collision](https://en.wikipedia.org/wiki/Hash_collision).

Any hash table __must__ handle hash collisions. At the same time, a "good" hash function will try to minimize hash collisions.

### Iteration 06: implementation

We will handle hash collisions. As mentioned, we _must_.

But not right now. We can make our test pass by improving our hash function. 

The following implementation makes our test pass:

```java
public class HashTable<K, V> extends iter05.HashTable<K, V> {
  @Override
  protected int bucket(Object key) {
    int hc = key.hashCode();

    return Math.floorMod(hc, keys.length);
  }
}
```

Our solution uses the [`Math.floorMod`](https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/lang/Math.html#floorMod(int,int)) static method. From its Javadocs we can see that:

- as the divisor, `keys.length`, is always positive the result of `floorMod` is guaranteed to be positive. Therefore, the `bucket` method is guaranteed to return a positive value (or zero);
- when the hash code value `hc` is positive, the `bucket` return value is equivalent to:

  ```java
  return hc % keys.length;
  ```
  
- when the hash code value `hc` is negative, it _might_ give a distinct result than:

  ```java
  return Math.abs(hc) & keys.length;
  ```

Put in other words, when two distinct keys produce different hash code values having the same absolute value, our new solution causes fewer hash collisions than the previous solution.

The following listing tries to illustrate this fact for an array of length `4`:

```
Math.floorMod( 1, 4) = 1
Math.floorMod(-1, 4) = 3

Math.floorMod( 2, 4) = 2
Math.floorMod(-2, 4) = 2

Math.floorMod( 3, 4) = 3
Math.floorMod(-3, 4) = 1

Math.floorMod( 4, 4) = 0
Math.floorMod(-4, 4) = 0

Math.floorMod( 5, 4) = 1
Math.floorMod(-5, 4) = 3
```

The previous solution would cause hash collisions for all of listed positive/negative pairs. The new solution, on the other hand, causes hash collisions only for the `(2, -2)` and `(4, -4)` pairs.

A small improvement. An improvement nonetheless.

This technique is used by:

- [java.util.ImmutableCollections.MapN](https://github.com/openjdk/jdk/blob/5e7e2da227cd2b5e2d3d1e2f59fb74ddd1835abb/src/java.base/share/classes/java/util/ImmutableCollections.java#L1321)
- [java.util.ImmutableCollections.SetN](https://github.com/openjdk/jdk/blob/5e7e2da227cd2b5e2d3d1e2f59fb74ddd1835abb/src/java.base/share/classes/java/util/ImmutableCollections.java#L1007)

## Iteration 07: replace the value mapped to an existing key

When the `put` method is invoked with a key-value pair such that:

- the map already contains a mapping for the specified key; and
- the existing mapped value is distinct from the specified value. 

Then the `put` method must replace the existing mapped value to the specified one.

We will implement this use-case in this iteration.

### Iteration 07: test case

And here's the test case for this iteration:

```java
public class HashTableTest {
  @Test(description = """
  put() method

  - replace the value mapped to an existing key
  """)
  public void iter07() {
    var ht = new HashTable<Integer, String>();
    assertEquals(ht.size(), 0);

    assertEquals(ht.put(1, "Won"), null);
    assertEquals(ht.size(), 1);

    assertEquals(ht.put(1, "One"), "Won");
    assertEquals(ht.size(), 1);

    assertEquals(ht.put(2, "Two"), null);
    assertEquals(ht.size(), 2);

    assertEquals(ht.get(1), "One");
    assertEquals(ht.get(2), "Two");
  }
}
```

We start by associating the `Won` string to the `1` key.

Next, we replace the `Won` value to the "correct" `One` value. As it is a replacement, we verify that the `put` returns the old value. We additionally verify that the map size remains the same.

Finally we add the `2 = Two` mapping. And, for completeness, we verify that we can correctly "get" both mappings from the map.

### Iteration 07: running our test

The test fails when run against the implementation of the previous iteration:

```
java.lang.UnsupportedOperationException: Implement me
	at iter03.HashTable.put1(HashTable.java:43)
	at iter03.HashTable.put0(HashTable.java:39)
	at iter02.HashTable.put(HashTable.java:25)
	at iter07.HashTableTest.iter07(HashTableTest.java:35)
```

As in the previous iteration, our test fails as it reaches a branch of our code we did not implement yet. The stack trace indicates it is the code written during [iteration #03](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#iteration-03-same-key-or-collision).

### Iteration 07: implementation

Here's an implementation that make our test pass:

```java
public class HashTable<K, V> extends iter06.HashTable<K, V> {
  @Override
  protected final V put1(K key, V value, int bucket, Object existing) {
    if (existing.equals(key)) {
      return putReplace(key, value, bucket);
    }

    return put2(key, value, bucket);
  }

  protected V put2(K key, V value, int bucket) {
    throw new UnsupportedOperationException("Implement me");
  }

  @SuppressWarnings("unchecked")
  protected final V putReplace(K key, V value, int bucket) {
    var oldValue = values[bucket];

    keys[bucket] = key;

    values[bucket] = value;

    return (V) oldValue;
  }
}
```

It starts by overriding the `put1` method defined during [iteration #03](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#iteration-03-same-key-or-collision).
Remember, the `put1` parameters are:

- `key` = the key the `put` method was invoked with;
- `value` = the value the `put` method was invoked with;
- `bucket` = the computed array index for `key`; and 
- `existing` = the existing key, if one exists, found at the computed `bucket` index.

If the `existing` key is equal to the specified `key` it means the current mapped value must be replaced.

### Iteration 07: the `putReplace` method

The actual replacement is done by the `putReplace` method:

```java
@SuppressWarnings("unchecked")
protected final V putReplace(K key, V value, int bucket) {
  var oldValue = values[bucket];

  keys[bucket] = key;

  values[bucket] = value;

  return (V) oldValue;
}
```

It starts by assigning the current mapped value to the `oldValue` variable.

Next, both the `key` and the `value` are stored at their respective arrays.

Finally, the `oldValue` is returned, as required by the `put` method contract.

Note that, since the `put` method only allows values of type `V` to be associated, the cast operation is safe. As the cast is safe, we can safely suppress the unchecked conversion warning. 

### Iteration 07: hash collision

If the `existing` key is _not equal_ to the specified `key` it means we have hit a hash collision.

We will handle it eventually, but, for now, we simply invoke the _yet to be implemented_ `put2` method:

```java
protected V put2(K key, V value, int bucket) {
  throw new UnsupportedOperationException("Implement me");
}
```

## Iteration 08: querying for a non-existing mapping

Let's focus once more on the `get` method.

In this iteration we will try to `get` the mapping of a non-existing key. We expected the `get` method to return `null` in this case.

### Iteration 08: test case

We write a minimal test exercising our use-case:

```java
public class HashTableTest {
  @Test(description = """
  get() method

  - non-existing key should return null
  """)
  public void iter08() {
    var ht = new HashTable<Integer, String>();

    assertEquals(ht.get(1), null);

    assertEquals(ht.put(1, "One"), null);

    assertEquals(ht.get(1), "One");
  }
}
```

We start by immediately querying for a non-existing key. We assert that the `get` method returns `null` in this case. 

For completeness, we associate a value to the previously queried key and verify that the `get` method now returns the associated value.

### Iteration 08: running our test

Let's run our new test against the implementation of the previous iteration: 

```
java.lang.UnsupportedOperationException: Implement me
	at iter04.HashTable.get0(HashTable.java:37)
	at iter04.HashTable.get(HashTable.java:33)
	at iter08.HashTableTest.iter08(HashTableTest.java:31)
```

It fails at the code written during [iteration #04](https://dev.to/marcioendo/how-to-implement-a-hash-table-in-java-part-1-4jfd#iteration-04-implementation). To be more precise, it fails because it reaches a branch left unimplemented during that iteration:

```java
if (key.equals(candidate)) {
  return (V) values[bucket];
}

// method get0 just throws UOE
return get0(key, bucket, candidate);
```

It reaches this path as the key `candidate` found at the `bucket` index is not equal to the `key` that was supplied to the `get` method.  

### Iteration 08: implementation

Here is an implementation that make the test pass:

```java
public class HashTable<K, V> extends iter07.HashTable<K, V> {
  @Override
  protected final V get0(Object key, int bucket, Object candidate) {
    if (candidate == null) {
      return null;
    }

    return get1(key, bucket);
  }

  protected V get1(Object key, int bucket) {
    throw new UnsupportedOperationException("Implement me");
  }
}
```

It is somewhat trivial.

If `candidate` is null it means there was not key found at the `bucket` index. In other words, the map does not contain the specified key. In this case, and as required by the `get` method contract, it must return `null`.

On the other hand, if `candidate` is not null then we have hit a hash collision once again. Except, this time, it occurs during a "read" operation.

We will handle hash collisions in the next post of this series. For now, we invoke a `get1` method that just throws `UnsupportedOperationException`. 

## In the next blog post of this series

In this second blog post of the series we started to deviate from the "happy path". In doing so we have incrementally improved our hash table implementation:

- it now supports keys with negative hash code values;
- the hash function produces fewer hash collisions when two distinct hash code values have the same absolute value;
- the `put` method now supports replacing an existing value mapping; and
- the `get` method now properly handles a non-existing key mapping.  

In the next blog posts of this series we will:

- handle hash collisions; and
- perform a rehash operation, i.e., resize the inner arrays so our hash table can hold more mappings

Stay tuned!

The source code for all of the examples in this post can be found at this [GitHub repository](https://github.com/objectos/blog-examples/tree/master/p016-hash-table/src).