DEV Community: Marcio Endo

Creating a static site using pure Java. Objectos 0.5.1 released

Marcio Endo — Mon, 20 Mar 2023 22:24:44 +0000

Welcome to Objectos Weekly issue #018.

I have released Objectos 0.5.1! Most of the work done on this release was internal. In other words, it contains just a few of user-facing changes. I expect the next few releases to follow suit.

In any case, I will show what's new in Objectos 0.5.1.

Let's begin.

Before we begin

I use Objectos in production. This very page was generated using Objectos HTML (and a few other Objectos libraries).

Having said that, please know that Objectos is alpha software. In particular:

it is far from being stable: deviate slightly from the shown use-case and it will probably fail;
API might change substantially between minor/patch releases; and
documentation is a work in progress.

Creating a static site using pure Java

The following were introduced to Objectos HTML in version 0.5.1:

the HtmlSink class;
the HtmlSink::toDirectory(HtmTemplate, Path) method;
the pathName instruction of the HtmlTemplate class; and
the pathTo instruction of the HtmlTemplate class.

They are all related. Let's look at an example to see how they work together.

Our template

Suppose the following Objectos HTML template:

public class MyTemplate extends HtmlTemplate {
  String pathName;

  @Override
  protected final void definition() {
    pathName(pathName);

    doctype();
    html(
      head(
        title("Objectos HTML example")
      ),
      body(
        p(
          a(pathTo("/index.html"), t("Home"))
        ),
        dl(
          dt("Path name:"),
          dd(pathName)
        )
      )
    );
  }
}

Notice the pathName instruction at the top of the definition method:

@Override
protected final void definition() {
  pathName(pathName);

  ...
}

It represents the path of generated HTML file.

The pathTo instruction was used inside the anchor in the template's body:

a(pathTo("/index.html"), t("Home"))

It is a link that takes you back to the site's home. The pathTo instruction generates a href attribute. But it uses the pathName information to generate a relative link.

Generating our static site

We will use the HtmlSink class to generate our static site to a pre-defined directory.

The following code does that:

var tmpdir = System.getProperty("java.io.tmpdir");

var target = Path.of(tmpdir, "objectos-html-example");

var pathNames = List.of(
  "/index.html",
  "/blog/index.html",
  "/blog/2023/03/17/objectos-html-is-cool.html"
);

var htmlSink = new HtmlSink();

var template = new MyTemplate();

for (var pathName : pathNames) {
  template.pathName = pathName;

  htmlSink.toDirectory(template, target);
}

We start by defining our target directory:

var tmpdir = System.getProperty("java.io.tmpdir");

var target = Path.of(tmpdir, "objectos-html-example");

I am running Linux, so I expect the target directory to be /tmp/objectos-html-example

Next, we define the structure of our static site:

var pathNames = List.of(
  "/index.html",
  "/blog/index.html",
  "/blog/2023/03/17/objectos-html-is-cool.html"
);

Note that the pathnames must start with the '/' slash character. Our hypothetical site contains three files. In a real site the structure could come e.g. from your AsciiDoc or Markdown files.

Next, we generate our site using HtmlSink and our MyTemplate class from before:

var htmlSink = new HtmlSink();

var template = new MyTemplate();

for (var pathName : pathNames) {
  template.pathName = pathName;

  htmlSink.toDirectory(template, target);
}

So, for each pathName defined, we set the pathName instance variable of our template.

Then, we invoke the HtmlSink::toDirectory method. Please note that it throws an IOException.

Running our example

After running our example, here's the structure generated:

$ find /tmp/objectos-html-example -type f
/tmp/objectos-html-example/blog/2023/03/17/objectos-html-is-cool.html
/tmp/objectos-html-example/blog/index.html
/tmp/objectos-html-example/index.html

So the HtmlSink class used the pathName to generate the directory hierarchy automatically.

Let's look at generate HTML of our home page:

<!doctype html>
<html>
<head>
<title>Objectos HTML example</title>
</head>
<body>
<p><a href="index.html">Home</a></p>
<dl><dt>Path name:</dt><dd>/index.html</dd></dl></body>
</html>

Notice the href in the anchor: it is not absolute.

The reason becomes clearer in the blog index page:

<!doctype html>
<html>
<head>
<title>Objectos HTML example</title>
</head>
<body>
<p><a href="../index.html">Home</a></p>
<dl><dt>Path name:</dt><dd>/blog/index.html</dd></dl></body>
</html>

Remember we used the pathTo instruction in the anchor (instead of a href).

The pathTo instruction uses the template's pathName value to generate a relative link.

For completeness, let's look at the generated HTML of the blog article:

<!doctype html>
<html>
<head>
<title>Objectos HTML example</title>
</head>
<body>
<p><a href="../../../../index.html">Home</a></p>
<dl><dt>Path name:</dt><dd>/blog/2023/03/17/objectos-html-is-cool.html</dd></dl></body>
</html>

So, during development, there's no need for a web server. In other words, you can point your browser to:

file:///tmp/html-sink-example/blog/index.html

And links should work fine.

Objectos Code: allow annotations in field declarations

I continue to work on the Objectos Code documentation.

While documenting field declarations I realized that Objectos Code did not allow for fields to be annotated. So I implemented that. And also wrote the documentation for it.

So the following Objectos Code:

import objectos.code.ClassTypeName;
import objectos.code.JavaTemplate;

public class FieldAnnotations extends JavaTemplate {
  static final ClassTypeName ANNO_A
      = ClassTypeName.of("com.example.annotations", "AnnotationA");
  static final ClassTypeName ANNO_B
      = ClassTypeName.of("com.example.annotations", "AnnotationB");
  static final ClassTypeName ANNO_C
      = ClassTypeName.of("com.example.annotations", "AnnotationC");

  @Override
  protected final void definition() {
    autoImports();

    classDeclaration(
      name("FieldAnnotations"),

      field(
        annotation(ANNO_A),
        annotation(ANNO_B),
        annotation(ANNO_C),
        PUBLIC, INT, name("multiple")
      )
    );
  }
}

Generates the following Java code:

import com.example.annotations.AnnotationA;
import com.example.annotations.AnnotationB;
import com.example.annotations.AnnotationC;

class FieldAnnotations {
  @AnnotationA
  @AnnotationB
  @AnnotationC
  public int multiple;
}

Until the next issue of Objectos Weekly

So that's it for today. I hope you enjoyed reading.

The source code of all of the examples are in this GitHub repository.

Objectos Weekly #005: Java's contextual keywords, class names and method names

Marcio Endo — Sat, 17 Dec 2022 12:57:13 +0000

Welcome to Objectos Weekly issue #005.

This is the first issue sent via the email newsletter. If you have received this issue in your email and had any troubles opening it, I apologize in advance. I would really appreciate it if you sent me a few words explaining what went wrong. And thank you in advance.

Please know that I will be open for Java freelancing work in 2023. You can find my contacts on this page. All work will be provided via Objectos Software LTDA based in São Paulo, Brazil.

Contextual keywords

Java 9 introduced the concept of restricted keywords. Since Java 17 they are called contextual keywords.

Contextual keywords allow for the same token to be interpreted as either a keyword or as a different token, an identifier typically. It depends on where the token appears in a compilation unit.

Reserved keywords

To understand contextual keywords, let's first discuss reserved keywords.

In Java, identifiers cannot have the same character sequence of a reserved keyword. You cannot name a method try because try is a reserved keyword.

// does not compile!
// 'try' is a reserved keyword
public void try() {
  ...
}

The same rule applies to other declarations having one or more identifiers. Examples include package names, module names, field names, local variable names, class names and others.

Backward compatibility

Reserved keywords represent a problem when evolving the language. As an example, let's take the introduction of records in Java 14.

Suppose that you are responsible for an application that currently targets Java 11. It contains a class called Record. So spread throughout your codebase you have many fields, methods and local variables named record:

class Foo {
  private Record record;

  public static Record of(int value) {
    var record = Record.create();
    record.set(value);
    return record;
  }

  public Record record() {
    return record;
  }
}

Suppose now that you want to upgrade to Java 17.

If the language designers decided to make record a reserved keyword, your application would not compile anymore.

So they made record a contextual keyword instead.

List of contextual keywords

As of Java 19, the contextual keywords are the following:

exports      opens      requires     uses
module       permits    sealed       var
non-sealed   provides   to           with
open         record     transitive   yield

We can use them in almost any place an identifier is required. As an example, consider the following:

package post.yield;

public class Contextual {
  public static void main(String[] uses) {
    var var = "Contextual keywords example";

    exports(var);
  }

  private static void exports(String record) {
    System.out.println(record);
  }
}

The Java program above uses contextual keywords:

yield in the package name;
uses in the main method parameter name;
var as the name of the local variable;
exports as the name of the private method; and
record as the name of the parameter of the private method.

The program compiles and runs. It prints:

Contextual keywords example

Contextual keywords and class names

In the last section I emphasized that contextual keywords can be used in almost any place an identifier is required.

A place where a few of the contextual keywords are restricted is class names. To be precise, by 'class name' I mean the name of any type declaration, i.e, a class, an interface (annotation included), an enum or a record.

The following jshell session illustrates all of the contextual keywords that are not allowed as class names. I have edited the output slightly so it is easier to read:

jshell> interface permits {}
|  Error:
|  'permits' not allowed here
|    as of release 15, 'permits' 
|      is a restricted type name 
|      and cannot be used for type declarations
|  interface permits {}
|            ^

jshell> record record(int value){}
|  Error:
|  'record' not allowed here
|    as of release 14, 'record' 
|      is a restricted type name 
|      and cannot be used for type declarations
|  record record(int value){}
|         ^

jshell> enum sealed {INSTANCE;}
|  Error:
|  'sealed' not allowed here
|    as of release 15, 'sealed'
|      is a restricted type name 
|      and cannot be used for type declarations
|  enum sealed {INSTANCE;}
|       ^

jshell> class var {}
|  Error:
|  'var' not allowed here
|    as of release 10, 'var'
|      is a restricted type name 
|      and cannot be used for type declarations
|  class var {}
|        ^

jshell> @interface yield {}
|  Error:
|  'yield' not allowed here
|    as of release 14, 'yield'
|      is a restricted type name 
|      and cannot be used for type declarations
|  @interface yield {}
|             ^

So the following contextual keywords are not allowed: permits, record, sealed, var and yield.

As usual, this is defined by the JLS section 3.8. It defines the production TypeIdentifier:

TypeIdentifier:
  Identifier but not permits, record, sealed, var, or yield

So class names can be any identifier except those five contextual keywords.

Let's try with contextual keywords not listed in the TypeIdentifier production:

jshell> class opens {}
|  created class opens

jshell> class exports {}
|  created class exports

Other keywords work.

Contextual keywords and method names

Method names do not suffer from the same restriction of class names.

However, if you name a method yield you must observe one thing. The following class does not compile:

// does not compile!
public class YieldMethod {
  public void callYield() {
    yield(); // <-- compilation error here
  }

  void yield() {
    System.out.println("yield() called!");
  }
}

The problem is in the method callYield. Defining the class above in jshell causes the following error message:

|  Error:
|  invalid use of a restricted identifier 'yield'
|    (to invoke a method called yield, 
|        qualify the yield with a receiver or type name)
|      yield();
|      ^---^

So, to fix the compilation error, we must rewrite the callYield method to:

public void callYield() {
  this.yield();
}

Let's test this fix using jshell:

jshell> public class YieldMethod {
   ...>   public void callYield() {
   ...>     this.yield();
   ...>   }
   ...> 
   ...>   void yield() {
   ...>     System.out.println("yield() called!");
   ...>   }
   ...> }
   ...> 
|  created class YieldMethod

jshell> new YieldMethod().callYield();
yield() called!

Why though?

I don't know the reason why. But, as usual, this is defined in the Java Language Specification.

Section 15.12 defines method invocation expressions:

MethodInvocation:
  MethodName ( [ArgumentList] )
  TypeName . [TypeArguments] Identifier ( [ArgumentList] )
  ExpressionName . [TypeArguments] Identifier ( [ArgumentList] )
  Primary . [TypeArguments] Identifier ( [ArgumentList] )
  super . [TypeArguments] Identifier ( [ArgumentList] )
  TypeName . super . [TypeArguments] Identifier ( [ArgumentList] )

Notice that, except for the first form, the method name is given by an Identifier token. The first is the form of the unqualified method invocation. In the unqualified form the method name is given by:

MethodName:
  UnqualifiedMethodIdentifier

UnqualifiedMethodIdentifier:
  Identifier but not yield

So you cannot invoke a method named yield using the unqualified form.

This is the reason why, in our previous example, we had to qualify the yield method invocation.

Until the next issue of Objectos Weekly

So that's it for today. I hope you enjoyed reading.

The source code of all of the examples are in this GitHub repository.

P.S. Thank you Dr. Heinz M. Kabutz for the encouragement to start the newsletter

Objectos Weekly #004: Type annotations, canonical names and inner classes

Marcio Endo — Fri, 09 Dec 2022 13:27:41 +0000

Welcome to Objectos Weekly issue #004.

I was writing this issue when the power in my apartment went out and I heard a loud noise outside. I looked outside from my balcony and I saw that the tree in front of my building had fallen taking a power line with it. Scary: a live power line was exposed right at the sidewalk. It burned a hole through the pavement. Luckily, there was no one there when it happened.

The power was restored later the same day. But it was already too late to do any meaningful work; I finished this issue the next day.

Type annotations, canonical names and inner classes

I have recently learned a detail regarding type annotations, canonical names and inner classes.

Suppose a class Example which is a subclass of the Super type:

package post;

import post.util.Super;

public class Example extends Super {}

Notice that the superclass is in a different package of the subclass. For this reason, a import declaration was required.

Let's annotate the superclass with a Nullable annotation.

package post;

import post.annotation.Nullable;
import post.util.Super;

public class Example extends @Nullable Super {}

The annotation might indicate to a hypothetical static analysis tool that the superclass fields can hold null values.

The code above compiles without errors.

Referring to the superclass by its canonical name

What happens if we use the canonical name of the superclass instead? We can remove the import declaration, like so:

package post;

import post.annotation.Nullable;

// does not compile!
public class Example extends @Nullable post.util.Super {}

After this change, the code no longer compiles! javac issues the following error message:

$ javac -d /tmp src/main/java/post/{,annotation,util}/*.java
src/main/java/post/Example.java:10: error: cannot find symbol
public class Example extends @Nullable post.util.Super {
                                       ^
  symbol: class post
1 error

It seems javac was expecting a class right after the Nullable annotation. Eclipse JDT error message gives more information:

Illegally placed annotation: type annotations must directly precede the simple name of the type they are meant to affect (or the [] for arrays)

OK, let's try to fix it then.

Fixing the compilation error

We must write the annotation right before the simple name of the class, like so:

package post;

import post.annotation.Nullable;

public class Example extends post.util. @Nullable Super {}

Notice how the annotation is after the trailing dot character of the package name.

The code now compiles without errors:

$ javac -d /tmp src/main/java/post/{,annotation,util}/*.java

[no errors emitted]

Well, I didn't know about that.

Why though?

I don't know for sure. But I think inner classes are one of the reasons.

In the previous issue I talked about inner classes and qualified superclass constructor invocations. The main takeaway to remember is:

in order to have an instance of the inner class we must provide an instance of the outer class.

Extending an inner class of `Super`

Let's say our superclass Super declares an inner class called Inner.

Let's have our Example class extend Inner instead of Super:

package post;

public class Example extends post.util.Super.Inner {
  public Example(post.util.Super outer) {
    outer.super();
  }
}

As Inner is an inner class, we must provide an instance of Super. That is why we had to add the constructor and use the qualified superclass constructor invocation.

Let's get back to our hypothetical static analysis tool. Let's say we would like to:

allow null values to the Super fields; but
disallow null values to the Inner fields.

We can annotate our class like so:

import post.annotation.NotNull;
import post.annotation.Nullable;

public class Example extends post.util.@Nullable Super.@NotNull Inner {
  public Example(post.util.Super outer) {
    outer.super();
  }
}

That's peculiar. I can definitely say I don't see it everyday.

It compiles without errors:

$ javac -d /tmp src/main/java/post/{,annotation,util}/*.java

[no errors emitted]

Objectos Code Weekly

Work on Objectos Code is still in progress. Please note that the syntax is still subject to change. In fact I experimented a bit with names that are reserved keywords.

For instance, to write a package declaration in Objectos you write:

_package("com.example.model");

As package is a reserved keyword, the name of the method has a leading underscore character. I tried the following variations:

packageDeclaration("com.example.model");

packageDecl("com.example.model");

package_("com.example.model");

package$("com.example.model");

But I was not pleased with any of them. So I decided to stick with the leading underscore version.

Method type parameters and type variables

You can declare a method with type parameters. The following Objectos Code:

public class TypeParams extends JavaTemplate {
  @Override
  protected final void definition() {
    _package("objectos.example");

    autoImports();

    _class(
      _public(), _final(), id("Util"),

      constructor(_private()),

      method(
        _public(), _static(),
        tparam("T", t("com.example", "Foo")),
        _void(),
        id("sort"),
        param(t(t("java.util", "List"), tvar("T")), id("list")),

        invoke(t(Collections.class), "sort", n("list"))
      )
    );
  }
}

Generates:

package objectos.example;

import com.example.Foo;
import java.util.Collections;
import java.util.List;

public final class Util {
  private Util() {}

  public static <T extends Foo> void sort(List<T> list) {
    Collections.sort(list);
  }
}

Parameterized types

You might have noticed in the previous example that you can write type arguments of a generic type. The following Objectos Code:

public class ParameterizedTypes extends JavaTemplate {
  @Override
  protected final void definition() {
    _package("objectos.example");

    autoImports();

    _class(
      _public(), id("ParameterizedTypesExample"),

      field(
        t(t("java.util", "Map"), t(String.class), t("java.lang", "Integer")),
        id("map")
      ),

      field(t(t(Set.class), t(OpenOption.class)), id("set")),

      field(
        t(
          t("java.util", "List"),
          t(t(Map.class), t(String.class), t(String.class))
        ), id("list")
      )
    );
  }
}

Generates:

package objectos.example;

import java.nio.file.OpenOption;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ParameterizedTypesExample {
  Map<String, Integer> map;

  Set<OpenOption> set;

  List<Map<String, String>> list;
}

Until the next issue of Objectos Weekly

So that's it for today. I hope you've enjoyed reading.

The source code of all of the examples are in this GitHub repository.

If you liked this content please consider subscribing to the blog via email.

OW #003: A type annotation curiosity, the qualified superclass constructor invocation and more

Marcio Endo — Thu, 01 Dec 2022 11:37:12 +0000

Hi, welcome to the third issue of Objectos Weekly.

I decided to rename this project. The old name, Last Week in Objectos, is no more. This is now called Objectos Weekly. I will sometime refer it as "OW" for short.

Let's begin.

Does this an annotation apply to the type or to the declaration?

In the last issue, I wrote that, syntactically speaking, annotations are just modifiers.

While the example focused on method declarations, the same principle applies to all declarations where annotations are allowed. For example, the following is valid Java code:

public class TypeAnnotationsExample {

  @Target(ElementType.FIELD)
  @Retention(RetentionPolicy.RUNTIME)
  @interface F {}

  @Target(ElementType.TYPE_USE)
  @Retention(RetentionPolicy.RUNTIME)
  @interface U {}

  @Target({ElementType.FIELD, ElementType.TYPE_USE})
  @Retention(RetentionPolicy.RUNTIME)
  @interface X {}

  private @U volatile @F transient @X int a;

}

Remember that annotations can go on declarations such as a class, a method or a field declaration. And, since Java 8, you can also annotate the types themselves.

So, in the example above, annotations might be annotating:

the field declaration; and/or
the type of the field, i.e., the int type.

But how can we know which annotation is being applied to what?

The answer lies in the @Target meta information of each of the annotations:

annotation @F applies to the field as its @Target is defined as FIELD only;
annotation @U applies to the int type as its @Target is defined as TYPE_USE only; and
annotation @X applies to both the field and the int type as its @Target is defined as both FIELD and TYPE_USE.

To confirm we write a small program:

public static void main(String[] args) throws NoSuchFieldException, SecurityException {
  var exampleClass = TypeAnnotationsExample.class;

  var field = exampleClass.getDeclaredField("a");

  var fieldAnnotations = field.getDeclaredAnnotations();

  System.out.println("Field annotations are:");

  printAnnotations(fieldAnnotations);

  var annotatedType = field.getAnnotatedType();

  System.out.println("Type annotations are:");

  printAnnotations(annotatedType.getDeclaredAnnotations());
}

private static void printAnnotations(Annotation[] annotations) {
  for (var annotation : annotations) {
    System.out.println(annotation);
  }
}

And when we run it, it prints:

Field annotations are:
@post.TypeAnnotationsExample.F()
@post.TypeAnnotationsExample.X()
Type annotations are:
@post.TypeAnnotationsExample.U()
@post.TypeAnnotationsExample.X()

The qualified superclass constructor invocation

An inner class instance must be associated to an instance of its enclosing class. In other words, to create an instance of an inner class, we must first create an instance of the outer class.

To illustrate the previous paragraph, consider the following jshell session.

First, we create the Inner class nested in the Outer class:

jshell> class Outer {
   ...>     class Inner {}
   ...> }
|  created class Outer

Let's try to create an Inner instance as if it were a static nested class:

jshell> var inner = new Outer.Inner();
|  Error:
|  an enclosing instance that contains Outer.Inner is required
|  var inner = new Outer.Inner();
|              ^---------------^

We can't. We must first create an instance of the outer class:

jshell> var outer = new Outer();
outer ==> Outer@3941a79c

jshell> var inner = outer.new Inner();
inner ==> Outer$Inner@4fca772d

We could have also written it in a one-liner:

jshell> var inner = new Outer().new Inner();
inner ==> Outer$Inner@b1bc7ed

The takeaway here is:

in order to have an instance of the Inner we must provide an instance of the Outer.

What if we subclass the `Inner` class?

If we create a subclass of the Inner class the previous requirement must still hold true. In other words, if we create a subclass InnerChild like so:

class InnerChild extends Outer.Inner {}

We must somehow provide an instance of Outer to InnerChild. And things get a little more complicated if we need to invoke a specific Inner constructor from InnerChild.

Let's start a new jshell session. Next, let's write a new version of Outer and Inner:

jshell> class Outer {
   ...>     Outer() { System.out.println("Outer()"); }
   ...>     Outer(boolean ignore) { System.out.println("Outer(bool)"); }
   ...>     
   ...>     class Inner {
   ...>         Inner() { System.out.println("Inner()"); }
   ...>         Inner(boolean ignore) { System.out.println("Inner(bool)"); }
   ...>     }
   ...> }
|  created class Outer

Next, we define the InnerChild as a subclass of Inner:

jshell> class InnerChild extends Outer.Inner {
   ...>     InnerChild() {
   ...>         new Outer().super();
   ...> 
   ...>         System.out.println("InnerChild()");
   ...>     }
   ...> 
   ...>     InnerChild(Outer outer) {
   ...>         outer.super(true);
   ...> 
   ...>         System.out.println("InnerChild(Outer)");
   ...>     }
   ...> }
|  created class InnerChild

As mentioned, we must, somehow, provide an instance of Outer to InnerChild. The first statement in the first constructor does exactly that:

new Outer().super();

It explicitly create an Outer instance and immediately invokes the Inner constructor that takes no arguments.

In the second constructor, the Outer instance is passed as a parameter:

InnerChild(Outer outer) {
  outer.super(true);

  ...
}

And from the Outer instance, it invokes the Inner constructor that takes the boolean argument.

These two super statements are examples of qualified superclass constructor invocation.

Let's see them in action. First, we create an InnerChild with no arguments:

jshell> new InnerChild();
Outer()
Inner()
InnerChild()
$7 ==> InnerChild@7cd84586

Let's now create an InnerChild with the Outer argument. First we create an Outer instance:

jshell> var outer = new Outer(true);
Outer(bool)
outer ==> Outer@30dae81

Then we create the InnerChild instance:

jshell> new InnerChild(outer);
Inner(bool)
InnerChild(Outer)
$9 ==> InnerChild@4edde6e5

I have never used them in "real-life" code. And, in fact, I have just learned about them. So I thought it would be interesting to share.

Objectos Code Weekly

Work on Objectos Code is still in progress. Here are a few examples of what is already possible.

Simple `Box` type

You can already write simple classes. The following Objectos Code:

public class BoxObjectosCodeExample extends JavaTemplate {
  public @interface TypeAnnotation {}

  @Override
  protected final void definition() {
    _package("com.example");

    autoImports();

    _class(
      annotation(TypeAnnotation.class),
      _public(), id("Box"),

      field(
        _private(), _final(), _int(), id("value")
      ),

      constructor(
        _public(),
        param(_int(), id("value")),
        assign(n(_this(), "value"), n("value"))
      ),

      method(
        _public(), _final(), _int(), id("get"),
        _return(n("value"))
      )
    );
  }
}

Generates:

package com.example;

import post.BoxObjectosCodeExample.TypeAnnotation;

@TypeAnnotation
public class Box {
  private final int value;

  public Box(int value) {
    this.value = value;
  }

  public final int get() {
    return value;
  }
}

Nested classes

You can also have nested classes:

public class NestedClassObjectosCodeExample extends JavaTemplate {
  @Override
  protected final void definition() {
    _package("com.example");

    autoImports();

    _class(
      _public(), id("Outer"),

      _class(
        id("Inner")
      )
    );
  }
}

Generates:

package com.example;

public class Outer {
  class Inner {}
}

Chained methods

You can already declare chained method invocations:

public class ChainedMethodsExample extends JavaTemplate {
  class User {}

  @Override
  protected final void definition() {
    _package("com.example");

    autoImports();

    _class(
      _public(), id("ChainedMethods"),

      method(
        _public(), _static(), _void(), id("main"),
        param(t(t(String.class), dim()), id("args")),

        var("user", chain(
          invoke(t(User.class), "builder"), nl(),
          invoke("id", i(123)), nl(),
          invoke("login", s("foo")), nl(),
          invoke("build")
        )),

        invoke(n(ClassName.of(System.class), "out"), "println", n("user"))
      )
    );
  }
}

Generates:

package com.example;

import post.ChainedMethodsExample.User;

public class ChainedMethods {
  public static void main(String[] args) {
    var user = User.builder()
        .id(123)
        .login("foo")
        .build();
    System.out.println(user);
  }
}

Until the next issue of Objectos Weekly

So that's it for today. I hope you've enjoyed reading.

You can subscribe to this blog via RSS. You can also follow me on Twitter.

The source code of all of the examples are in this GitHub repository.

LWO #002: Annotations are just modifiers, array access curiosity, faux code generators and more

Marcio Endo — Thu, 24 Nov 2022 10:23:08 +0000

Hi, welcome to the second edition of Last Week in Objectos (LWO).

In this edition I will discuss:

a few of my findings about the Java language while working on Objectos Code; and
the last week's work on Objectos Code itself.

Let's begin.

Annotations are just modifiers (grammatically speaking)

I didn't know that, grammatically (syntactically?) speaking, annotations are just modifiers to the Java language. In other words, I have always thought that the only way to annotate, say a method, would be:

@Override
public final String toString() {
  return "Annotations are just modifiers";
}

But, in fact, you can write:

public @Override final String toString() ...

Or, if you prefer:

public final @Override String toString() ...

I always thought that the last two examples would fail to compile. But they do not; all of the three declarations are syntactically correct.

Additionally, all of the three declarations are equivalent. Well, there is a small caveat in the last example regarding type annotations, which we'll look into at another time.

I found out about it when reading the grammar production of method declarations:

MethodDeclaration:
  {MethodModifier} MethodHeader MethodBody

It means that a method declaration can contain zero or more MethodModifier. The MethodModifier production is defined as:

MethodModifier:
  (one of)
  Annotation public protected private
  abstract static final synchronized native strictfp

So any of the modifiers can appear in any order. Cool!

An Array Access Expression curiosity

Array access expressions are expressions to, well, access a component of an array.

A simple example can be:

String[] a = { "array", "access" };
System.out.println(a[1]);

The argument to the println method, i.e. the a[1], is an array access expression.

The following is wrong and does not compile:

System.out.println(this[1]);

But why does it not compile? Well, that's what is curious to me. I thought it failed to compile simply because the "syntax is invalid". But that is not exactly what happens in this case.

Let's try to compile and run the following program:

public class Test {
  public static void main(String[] args) {
    new Test().execute();
  }

  public void execute() {
    System.out.println(this[1]);
  }
}

When I try to run it:

$ java Test.java
Test.java:7: error: array required, but Test found
  System.out.println(this[1]);
                         ^
1 error
error: compilation failed

It fails to compile because this does not evaluate to an array type. So, in some ways, the syntax itself is valid. But, as this resolves to a non-array type, it fails to compile.

This is expected as it is defined in the language specification. The ArrayAccess production is given by the following:

ArrayAccess:
  ExpressionName [ Expression ]
  PrimaryNoNewArray [ Expression ]
  ArrayCreationExpressionWithInitializer [ Expression ]

We are interested in the second form, the one with PrimaryNoNewArray. PrimaryNoNewArray is defined as:

Literal
ClassLiteral
this
TypeName . this
( Expression )
ClassInstanceCreationExpression
FieldAccess
ArrayAccess
MethodInvocation
MethodReference

So the following (wrong) examples:

1234[0];
Object.class[1];
this[2];
Outer.this[3];

All fail to compile. But not because the "syntax is invalid". Instead, they fail to compile because the part to left of the brackets do not evaluate to an array type.

Faux code generators

I am creating Objectos Code because I write a lot of code generators. But parts of Objectos Code itself might benefit of having them being generated. What to do in this case?

Well, I write a plain "faux" (ad-hoc?) code generator. It looks a bit like this:

import static java.lang.System.out;

public class ByteCodeFauxGenerator {
  private int value = -1;

  public static void main(String[] args) {
    var gen = new ByteCodeFauxGenerator();

    gen.execute();
  }

  public final void execute() {
    comment("class");

    value("CLASS");
    value("MODIFIER");
    value("IDENTIFIER");

    comment("statements");

    value("LOCAL_VARIABLE");
    value("RETURN_STATEMENT");
  }  

  private void comment(String string) {
    out.println();
    out.println("// " + string);
    out.println();
  }

  private void value(String string) {
    out.println("static final int " + string + " = " + value-- + ";");
  }  
}

This code resides in the src/test/java directory of the project. It has a main method, so I can just run it. It prints:

// class

static final int CLASS = -1;
static final int MODIFIER = -2;
static final int IDENTIFIER = -3;

// statements

static final int LOCAL_VARIABLE = -4;
static final int RETURN_STATEMENT = -5;

Then I copy this output and paste it into the actual class, located in src/main/java:

final class ByteCode {
  // class

  static final int CLASS = -1;
  static final int MODIFIER = -2;
  static final int IDENTIFIER = -3;

  // statements

  static final int LOCAL_VARIABLE = -4;
  static final int RETURN_STATEMENT = -5;

  private ByteCode() {}
}

I call it a "faux" code generator because the process is manual. Even though it is manual, it is still effective.

Last week in Objectos Code

And here is a summary of the work I have done in Objectos Code.

Lambda inclusion support

To generate a class with a single field you write the following in Objectos Code:

_class(
  id("Example"),
  field(_int(), id("a"))
);

It generates the following:

class Example {
  int a;
}

What if you don't know beforehand the number and names of the fields to be generated?

To this use-case, Objectos Code offers the include directive:

public class IncludeExample extends JavaTemplate {
  private final List<String> fieldNames = List.of("a", "b", "c");

  @Override
  protected final void definition() {
    _class(
      id("Example"),
      include(this::generateFields)
    );
  }

  private void generateFields() {
    for (var fieldName : fieldNames) {
      field(_int(), id(fieldName));
    }
  }
}

Which should generate:

class Example {
  int a;

  int b;

  int c;
}

Remember that Objectos Code is a pure Java template. So the previous example is equivalent to the following string-based template:

class Example {
  {{#fieldNames}
  int {{.}};
  {{/fieldNames}
}

Constructor declarations, assignment expressions, and field access expressions

I have started the implementation of constructor declarations. The following Objectos Code:

_class(
  id("Foo"),
  field(_final(), _int(), id("a")),
  constructor(
    param(_int(), id("a"),
    assign(n(_this(), "a"), n("a"))
  )
);

Generates the following Java code:

class Foo {
  final int a;

  Foo(int a) {
    this.a = a;
  }
}

More enum declarations

I have also continued the work on enum declarations. Enum class declarations are currently required in Objectos HTML.

The following Objectos Code:

var test = PackageName.of("test");
var iface = ClassName.of(test, "Iface");

_enum(
  _public(), id("Test"), _implements(iface),
  enumConstant(id("A"), s("a")),
  enumConstant(id("B"), s("b")),
  field(_private(), _final(), t(String.class), id("value")),
  constructor(
    _private(),
    param(t(String.class), id("value")),
    assign(n(_this(), "value"), n("value"))
  ),
  method(
    annotation(Override.class),
    _public(), _final(), t(String.class), id("toString"),
    _return(n("value"))
  )
);

Generates:

public enum Test implements test.Iface {
  A("a"),

  B("b");

  private final java.lang.String value;

  private Test(java.lang.String value) {
    this.value = value;
  }

  @java.lang.Override
  public final java.lang.String toString() {
    return value;
  }
}

Until the next edition

So that's it for today. I hope you've enjoyed reading.

You can find the source code in this GitHub repository.

Please send me an e-mail if you have comments, questions or corrections regarding this post.

If you liked this content you can follow me on Twitter.

LWO #001: Objectos Code API revamp, and a use of Java's sealed interfaces

Marcio Endo — Fri, 18 Nov 2022 11:29:24 +0000

Hi, welcome to the first edition of "Last Week in Objectos" (LWO), my new writing project.

I enjoy writing. But the deep technical writings of the blog are very time consuming. Time spent in the writing itself, of course, but also spent on figuring out what to write about.

This is an attempt to solve this; spend less time on writing related tasks while still providing value to readers.

I will write about what happened the previous week in Objectos. The idea is to share the things I learned, the problems I faced and how I solve them. Or how I didn't solve them...

Also, the idea is for this to become a newsletter. Once I sort out the software, that is. It will have a different name though.

All right, enough of this introduction. Let's begin.

Objectos Code API revamp

Objectos Code is a Java library for generating Java source code. Later, it will also provide utilities for writing annotation processors.

I am currently working on revamping its API.

The new API

My idea is to provide a "template engine" for generating Java source code. However, unlike traditional template engines, the template itself is not string based. Templates in Objectos Code are written in pure Java instead.

You create a template by extending the JavaTemplate class. The following is a sort-of hello world example:

import objectos.code.JavaTemplate;

class HelloTemplate extends JavaTemplate {
  String pkgName = "com.example";

  String name = "HelloWorld";

  String message = "Hello world!";

  @Override
  protected final void definition() {
    _package(pkgName);

    _class(
      _public(), id(name),

      _method(
        _public(), _void(), id("sayHello"),
        invoke(n(System.class, "out"), "println", s(message))
      )
    );
  }
}

The template can be used like the following:

var hello = new HelloTemplate();
hello.pkgName = "objectos.example";
System.out.println(hello);

Which prints:

package objectos.example;

public class HelloWorld {
  public void sayHello() {
    System.out.println("Hello world!");
  }
}

The new API is a work in progress. It does not support array types yet, nor can you declare method parameters. This is the reason why the example is not a "proper" hello world.

Consistent API across Objectos' libraries

So, why am I creating a new API? Was there something wrong with the old one?

There are a few things I dislike about the old API. But the main reason for the new API is to have a consistent API throughout all of the Objectos' libraries.

For example, Objectos HTML is an unreleased Java library to generate HTML using pure Java:

class MyTemplate extends HtmlTemplate {
  @Override
  protected final void definition() {
    doctype();
    html(
      lang("en"),
      head(
        meta(charset("utf-8")),
        meta(httpEquiv("x-ua-compatible"), content("ie=edge")),
        meta(
          name("viewport"),
          content("width=device-width, initial-scale=1, shrink-to-fit=no")
        )
      ),
      body(
        p("Hello world!")
      )
    );
  }
}

As you can see, it uses the same idea of "a template in pure Java".

Objectos CSS, used to generate CSS style sheets, also uses the same idea.

Work on Objectos Code

Now that I've given an introduction to Objectos Code, here's what I've actually work on this past week.

Initial enum declaration support

I've started adding the enum declaration support to Objectos Code.

You can generate a simple enum like the following:

public enum Suit {
  CLUBS,

  DIAMONDS,

  HEARTS,

  SPADES
}

Using this code:

_enum(
  _public(), id("Suit"),
  enunConstant(id("CLUBS")),
  enunConstant(id("DIAMONDS")),
  enunConstant(id("HEARTS")),
  enunConstant(id("SPADES"))
);

Initial field declaration support

I also started migrating field declarations to the new API.

The following class:

class Fields {
  Integer a;

  final String b = "b";

  private static final String C = "C";

  String d, e = b; 
}

Can be generated with:

_class(
  id("Fields"),

  field(t(Integer.class), id("a")),

  field(_final(), t(String.class), id("b"), s("b")),

  field(_private(), _static(), _final(), t(String.class), id("C"), s("C")),

  field(t(String.class), id("d"), id("e"), n("b"))
);

You should note that:

the id method, which is short for identifier, is for naming declarations, i.e., the class name, the enum class name, the field name, etc.
the t method is for types
the s method is for string literals
the n method is for expression names

A (somewhat) type-safe API

The examples might give the impression that the Objectos Code API is free-form. But it is not.

As an example, the following does not compile:

// does not compile!!
_class(
  enumConstant(id("FAIL"))
);

As the _class method does not accept as argument the return value of the enumConstant method. Similarly, the following does not compile either:

// does not compile!!!
_enum(
  _public(), _final(), id("Fail")
);

As the _enum method does not accept as argument the return value of the _final() method.

Using Java's sealed interfaces

To provide the type-safety of the Objectos Code API I am using Java's sealed interfaces.

The _class method is an instance method of the JavaTemplate class. The signature of the method is the following:

protected final ClassDeclaration _class(
    ClassDeclarationElement... elements);

So it only accepts instances of the ClassDeclarationElement interface. But it cannot accept any implementation of said interface. In fact, it must only accept implementations provided by Objectos Code itself.

So there are two conflicting problems:

the ClassDeclarationElement interface must be accessible to subclasses of the JavaTemplate; and
the _class method cannot accept arbitrary implementations of the ClassDeclarationElement interface.

The way I solved it (I think) is by using sealed interfaces. Here's a simplified version of the InternalApi class. The InternalApi class declares all of the sealed hierarchy:

public final class InternalApi {
  public sealed interface ClassDeclaration {}

  public sealed interface ClassDeclarationElement {}

  public sealed interface Identifier
      extends ClassDeclarationElement {}

  public sealed interface PublicModifier
      extends ClassDeclarationElement {}

  public sealed interface VoidInvocation {}    

  private static final class Ref 
      implements
      ClassDeclaration,
      Identifier,
      PublicModifier,
      VoidInvocation {
    private Ref() {}      
  }

  public static final Ref REF = new Ref();  
}

And, in the JavaTemplate class, we write:

protected final ClassDeclaration _class(
    ClassDeclarationElement... elements) {
  // actual impl...  
  return InternalApi.REF;
}

protected final PublicModifier _public() {
  // actual impl...  
  return InternalApi.REF;
}

protected final VoidInvocation _void() {
  // actual impl...  
  return InternalApi.REF;
}

protected final Identifier id(String value) {
  // actual impl...  
  return InternalApi.REF;
}

So it means that the following invocation is valid:

_class(_public(), id("Foo"));

While the following is not:

_class(_void(), id("Foo"));

Until the next edition

So that's it for today. I hope you've enjoyed reading.

You can subscribe to the blog via RSS.

If you liked this content you can follow me on Twitter.

In-depth look: the Java try-with-resources statement

Marcio Endo — Fri, 04 Nov 2022 12:12:40 +0000

Sometime ago I started writing a JNI wrapper around libgit2.

I quickly gave up on it. I was not confident on my very little C knowledge nor my very little JNI knowledge. So instead I started writing a pure Java GIT (partial) implementation.

A main takeaway from my brief JNI experience was my newfound appreciation of:

Java's error signaling via exceptions. Checked exceptions included (as opposed to return codes); and
Java's exception handling and resource releasing via try and try-with-resources statements (as opposed to a combination of if and goto statements).

What problems did the `try-with-resources` solve?

As mentioned we handle exceptional conditions in Java via the try and the try-with-resources Java statements. The former exists since the first release of the language. The latter was introduced in Java 7.

At time of writing Java 7 is almost 11 years old. So let's remember why the try-with-resources statement was introduced.

I was not there with the language designers. Nor did I research the mailing lists. So this section is about my assumptions. I just want this to be clear.

Anyways, what problems did the try-with-resources solve? Wasn't the plain try statement enough?

Let's investigate.

Our running example

For our investigations we will use a class that simulates a resource that needs to be released after it has been used.

For all purposes, think of it being like a java.io.FileWriter.

Here is the code:

public class Resource implements Closeable {
  final String name;

  Resource(String name) {
    this.name = name;

    print0("created");
  }

  public static Resource create(String name) throws IOException {
    return new Resource(name);
  }

  @Override
  public void close() throws IOException {
    print0("closed");
  }

  public void write(String s) throws IOException {
    print0(s);
  }

  final void print0(String string) {
    System.out.println(name + ": " + string);
  }
}

To use it you first need to create a new instance by invoking the static create method. It requires a name. Think of it as a pathname.

The class can throw an IOException on creation, just like new FileWriter or Files.newBufferedWriter would. Examples of reasons why this might happen:

the specified pathname resolves to a directory. You can't write to a directory as if it were a regular file; or
the specified pathname could be of a location for which you do not have write permission.

Once the resource object is created it prints created to System.out.

You can write to it by invoking the write method. It does actual I/O as it prints to System.out.

After you have done writing you must close the resource by invoking the close method. It is specified by the java.io.Closeable interface which Resource implements. It prints closed signaling that closing was successful.

Single resource

So let's use our class. We will use a single resource to print a string to the console.

First using a plain try statement:

public class Try {
  public static void main(String[] args) throws IOException {
    var out = Resource.create("TRY");

    try {
      out.write("Try statement (iteration 1)");
    } finally {
      out.close();
    }
  }
}

I know, I am not actually doing any error handling here, but bear with me.

Executing this example results in the following output to the console:

TRY: created
TRY: Try statement (iteration 1)
TRY: closed

Now, the same example using the try-with-resources statement:

public class TryWithResources {
  public static void main(String[] args) throws IOException {
    try (var out = Resource.create("TWR")) {
      out.write("Try-with-resources statement (iteration 1)");
    }
  }
}

Prints:

TWR: created
TWR: Try-with-resources statement (iteration 1)
TWR: closed

The try-with-resources is more concise, the closing happens automatically and the resource variable is scoped to the statement itself.

Still, one can say that, in this example, the try statement looks manageable, does it not?

I tend to agree, but I do not think this example illustrates the main reason for using the try-with-resources statement.

Two resources

I think most problems arise when using more than one resource. This can be a common use-case, for instance:

transferring data from an InputStream to an OutputStream;
same thing but using Java NIO channels; or
using plain JDBC and dealing with connection, statement and result set.

So let's write a version using two resources:

public class Try {
  // Please avoid code like this in production
  public static void main(String[] args) throws IOException {
    var a = Resource.create("A");
    var b = Resource.create("B");

    try {
      a.write("Try statement (iteration 2)");
      b.write("Try statement (iteration 2)");
    } finally {
      a.close();
      b.close();
    }
  }
}

This example has a number of problems which we will discuss in this section. For now, let's run it as it is:

A: created
B: created
A: Try statement (iteration 2)
B: Try statement (iteration 2)
A: closed
B: closed

While using the try-with-resources statement:

public class TryWithResources {
  public static void main(String[] args) throws IOException {
    try (var a = Resource.create("A"); var b = Resource.create("B")) {
      a.write("Try-with-resources statement (iteration 2)");
      b.write("Try-with-resources statement (iteration 2)");
    }
  }
}

Gives:

A: created
B: created
A: Try-with-resources statement (iteration 2)
B: Try-with-resources statement (iteration 2)
B: closed
A: closed

Apart from the closing happening in a different order (we will look into it later) both examples produce an equivalent output.

So now what?

Two resources: error on creation

Let's modify our Resource class to simulate an error on creation. As mentioned earlier, thinking the class as a FileWriter, this could be caused by specifying a location for which we do not have writing permission:

public static Resource throwOnCreate(String name) throws IOException {
  throw new IOException("Failed to create: " + name);
}

And we use it with the plain try statement:

public class Try {
  // Please avoid code like this in production
  public static void main(String[] args) throws IOException {
    var a = Resource.create("A");
    var b = Resource.throwOnCreate("B");

    try {
      a.write("Try statement (iteration 3)");
      b.write("Try statement (iteration 3)");
    } finally {
      b.close();
      a.close();
    }
  }
}

Notice we reversed the order of the close statements.

Once again, this example still contain warning signs (in particular in the finally block) which will discuss as we go.

Running this example prints:

A: created
Exception in thread "main" java.io.IOException: Failed to create: B
        at shared.Resource.throwOnCreate(Resource.java:29)
        at iter3.Try.main(Try.java:14)

Resource A was created but it was never closed.

On the other hand, the same example using the try-with-resources statement:

public class TryWithResources {
  public static void main(String[] args) throws IOException {
    try (var a = Resource.create("A"); var b = Resource.throwOnCreate("B")) {
      a.write("Try-with-resources statement (iteration 3)");
      b.write("Try-with-resources statement (iteration 3)");
    }
  }
}

Prints:

A: created
A: closed
Exception in thread "main" java.io.IOException: Failed to create: B
        at shared.Resource.throwOnCreate(Resource.java:29)
        at iter3.TryWithResources.main(TryWithResources.java:13)

Resource A was created and was properly closed.

Two resources: error on closing

Let's modify our Resource class once again to simulate an error when executing the close method.

This can happen when using a buffered writer. During the close operation, flushing the buffer to the filesystem will fail if the disk runs out of space.

So we create a subclass that throws in the close method:

private static class ThrowOnClose extends Resource {
  ThrowOnClose(String name) {
    super(name);
  }

  @Override
  public void close() throws IOException {
    print0("close() called");

    throw new IOException("Failed to close: " + name);
  }
}

And our create method for this class is named throwOnClose:

public static Resource throwOnClose(String name) throws IOException {
  return new ThrowOnClose(name);
}

Let's use it in the plain try case. We will have the B resource to throw on the close operation:

public class Try {
  // Please avoid code like this in production
  public static void main(String[] args) throws IOException {
    var a = Resource.create("A");
    var b = Resource.throwOnClose("B");

    try {
      a.write("Try statement (iteration 4)");
      b.write("Try statement (iteration 4)");
    } finally {
      b.close();
      a.close();
    }
  }
}

Running this example results in:

A: created
B: created
A: Try statement (iteration 4)
B: Try statement (iteration 4)
B: close() called
Exception in thread "main" java.io.IOException: Failed to close: B
        at shared.Resource$ThrowOnClose.close(Resource.java:54)
        at iter4.Try.main(Try.java:20)

And the resource A was not closed.

Let's write the same example using the try-with-resources statement:

public class TryWithResources {
  public static void main(String[] args) throws IOException {
    try (var a = Resource.create("A"); var b = Resource.throwOnClose("B")) {
      a.write("Try-with-resources statement (iteration 4)");
      b.write("Try-with-resources statement (iteration 4)");
    }
  }
}

Which gives:

A: created
B: created
A: Try-with-resources statement (iteration 4)
B: Try-with-resources statement (iteration 4)
B: close() called
A: closed
Exception in thread "main" java.io.IOException: Failed to close: B
        at shared.Resource$ThrowOnClose.close(Resource.java:54)
        at iter4.TryWithResources.main(TryWithResources.java:16)

Resource A was properly closed.

Two resources: exception during the `try` block

We mentioned earlier that, so far, we were not actually doing any error handling. In other words, we were not declaring the catch part of our statement.

Granted, in our example, I am not sure we can do much. Except maybe:

give a proper message to the user (as opposed to a stack trace); and
stop the execution normally (as opposed to abruptly by an uncaught exception).

The try example was refactored to:

public class Try {
  // Please avoid code like this in production
  public static void main(String[] args) throws IOException {
    Resource a = null;
    Resource b = null;

    try {
      a = Resource.create("A");
      a.throwOnWrite("Try statement (iteration 5)");

      b = Resource.create("B");
      b.write("Try statement (iteration 5)");
    } catch (IOException e) {
      System.err.println("The program failed: " + e.getMessage());

      return; // explicitly stop execution
    } finally {
      b.close();
      a.close();
    }

    System.out.println("More instructions...");
  }
}

Notice that, on the A resource, we invoked a throwOnWrite method.

It is a method to simulate an IOException during a write operation:

public void throwOnWrite(String s) throws IOException {
  throw new IOException("Failed to write: " + name);
}

Running the example:

A: created
The program failed: Failed to write: A
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "shared.Resource.close()" because "b" is null
        at iter5.Try.main(Try.java:27)

The A resource does not get closed. To make matters worse, the program additionally exits abruptly with an uncaught exception: a NullPointerException occurred when trying to close the B resource.

The reason it happens is that the B resource is never created as the A resource throws before B can be created. And we deliberately did not include a null-check before closing the resource.

Let's write the same example using the try-with-resources statement:

public class TryWithResources {
  public static void main(String[] args) throws IOException {
    try (var a = Resource.create("A"); var b = Resource.create("B")) {
      a.throwOnWrite("Try-with-resources statement (iteration 5)");
      b.write("Try-with-resources statement (iteration 5)");
    } catch (IOException e) {
      System.err.println("The program failed: " + e.getMessage());

      return; // explicitly stop execution
    }

    System.out.println("More instructions...");
  }
}

Results:

A: created
B: created
B: closed
A: closed
The program failed: Failed to write: A

Both resources are properly closed and the program exits normally.

I am sure that, if we kept looking, we would find more issues. But this should do it for now.

Let's now see what's in a try-with-resources statement.

What's in a `try-with-resources` statement?

So what is in a try-with-resources statement? Meaning can we rewrite it using the plain try statement?

The answer is yes. In fact that is what the Java compiler does. Others have written about it, so I will not here. For example:

Heinz Kabutz writes about it here
there is also this StackOverflow answer

Here I will do something slightly different. Before we go into it, let's first look what the specification says.

Java Language Specification (JLS) 18

At time of writing, Java 18 is the current release of the language. The try-with-resources statement is in section 14.20.3 of the Java language specification. In the first paragraph we read (emphasis mine):

A try-with-resources statement is parameterized with variables (known as resources) that are initialized before execution of the try block and closed automatically, in the reverse order from which they were initialized

So this explains why we had to reverse the order of the close operations in the previous section.

In section 14.20.3.1 we find the specification of the code the compiler must emit:

{
    final {VariableModifierNoFinal} R Identifier = Expression;
    Throwable #primaryExc = null;

    try ResourceSpecification_tail
        Block
    catch (Throwable #t) {
        #primaryExc = #t;
        throw #t;
    } finally {
        if (Identifier != null) {
            if (#primaryExc != null) {
                try {
                    Identifier.close();
                } catch (Throwable #suppressedExc) {
                    #primaryExc.addSuppressed(#suppressedExc);
                }
            } else {
                Identifier.close();
            }
        }
    }
}

The specification is recursive on ResourceSpecification_tail when more than one resource is declared. In other words, when two resources are declared, there will be a second try nested in this try. When three resources are declared, there will be a third try nested in the second one. And so on.

We are not trying to write a Java compiler. We just want to understand what happens when a try-with-resources statement is executed.

So, can we write a version of this code in such ways that:

produces the same effect, that is, "does the same job"; and
is more readable by a Java developer (as opposed to being readable by a JVM)?

Let's give it a try.

A closing utility

A good initial refactoring candidate is the code in the finally block. This block:

closes the resource in a null safe way; and
handles the exception that can be thrown during the close operation.

Let's extract it to a utility class and rewrite slightly:

public final class Close {
  public static Throwable ifPossible(Throwable t, AutoCloseable c) {
    var res = t;

    if (c != null) {
      try {
        c.close();
      } catch (Throwable e) {
        if (res == null) {
         res = e;
        } else {
         res.addSuppressed(e);
        }
      }
    }

    return res;
  }
}

First there is a null check on the AutoCloseable instance. It is there so the NullPointerException we faced in the "Two resources: exception during the try block" example does not happen.

Next the resource is closed in a try-catch statement. The try-catch is necessary as the close() operation might throw:

the Exception it declares it throws;
a RuntimeException. For example, a NullPointerException from a programming error;
an Error. For example, a StackOverflowError from a programming error.

We saw what happens if we don't catch this throwable in the "Two resources: error on closing" example.

In the catch block we check if there was a previous exception. This would typically be the exception caught in the main try block. In our examples this would be the one thrown while trying to write to the resource.

Now, if there were such exception it would be a distinct exception than the one thrown during a close operation. By this I mean that, even though in this particular case they might have some relation (both were thrown by the same instance), they do not share a cause effect. In other words, one should not be declared as the cause of the other.

On the other hand, it would be unwise to simply ignore one exception or the other.

Suppressed exception

So that the closing exception is not ignored, Java 7 introduced the concept of suppressed exceptions.

The exception thrown during the close operation is added as a suppressed exception of the previous exception if the latter exists.

If there was no previous exception then the exception thrown during the close operation is simply returned by our utility and it becomes our primary exception.

Rewriting our two resources `try` examples

Let's use our new utility class by rewriting the two resources examples.

A happy path examples becomes:

public class Try {
  public static void main(String[] args) {
    Throwable rethrow = null;

    Resource a = null;
    Resource b = null;

    try {
      a = Resource.create("A");
      b = Resource.create("B");

      a.write("Try statement (iteration 6)");
      b.write("Try statement (iteration 6)");
    } catch (Throwable e) {
      rethrow = e;
    } finally {
      rethrow = Close.ifPossible(rethrow, b);
      rethrow = Close.ifPossible(rethrow, a);
    }

    if (rethrow != null) {
      System.err.println("The program failed: " + rethrow.getMessage());

      return; // explicitly stop execution
    }

    System.out.println("More instructions...");
  }
}

The general recipe is:

begin with a null throwable local variable named rethrow
declare all your resources initialized will null
at the start of the try block, create all your resources
do your work
declare a single catch-all catch block
simply assign the caught throwable to the rethrow variable
in the finally block, using our utility and in the reverse order of the resource creation close all of the resources
if any error occurred, either in the try block or in the finally block, the rethrow variable will be rethrow != null. Handle the error appropriately
if no errors occurred, continue the execution

Running this program results in:

A: created
B: created
A: Try statement (iteration 6)
B: Try statement (iteration 6)
B: closed
A: closed
More instructions...

Which is equivalent to the output of the following try-with-resources version:

public class TryWithResources {
  public static void main(String[] args) {
    try (var a = Resource.create("A"); var b = Resource.create("B")) {
      a.write("Try-with-resources statement (iteration 6)");
      b.write("Try-with-resources statement (iteration 6)");
    } catch (Throwable e) {
      System.err.println("The program failed: " + e.getMessage());

      return; // explicitly stop execution
    }

    System.out.println("More instructions...");
  }
}

Both versions are equivalent in the sense that both "do the same job". They are not "bytecode equivalent" however.

The try-with-resources version:

is more concise;
the closing happens automatically; and
the resource variable is scoped to the statement itself.

Additionally, the plain try statement version is error-prone:

a good indicator is the fact that the recipe we wrote has nine steps in it.

The remaining examples can be found in the GitHub repo.

Restricting the catch-all to catch `IOException` only

Did you notice that, in the previous try-with-resources example, we used a catch-all catch clause?

Meaning that we declared it to catch Throwable and not IOException which is the only checked exception declared to be thrown in the statement:

by the create operation;
by the write operation; and
by the close operation.

If using an IDE it would most likely suggest for the clause to catch an IOException only and not a Throwable:

} catch (IOException e) {
  System.err.println("The program failed: " + e.getMessage());

  return; // explicitly stop execution
}

To make our try example equivalent our single if statement after the try statement would have to be rewritten to:

if (rethrow instanceof RuntimeException re) {
  throw re;
}

if (rethrow instanceof Error err) {
  throw err;
}

if (rethrow instanceof IOException ioe) {
  System.err.println("The program failed: " + ioe.getMessage());

  return; // explicitly stop execution
}

Meaning that:

If either a RuntimeException or an Error is thrown in either the try block or during the closing of the resources then the program ends abruptly by an uncaught exception.

If an IOException is thrown in either the try block or during the closing of the resources then the program ends normally with the message "The program failed: {exception message}" printed to System.err.

Suppressed exception example

As a final example, let's see the suppressed exceptions in action:

public class TrySuppressed {
  public static void main(String[] args) throws IOException {
    Throwable rethrow = null;

    Resource a = null;
    Resource b = null;

    try {
      a = Resource.create("A");
      b = Resource.throwOnClose("B");

      a.throwOnWrite("Try statement (suppressed in action)");
      b.write("Try statement (suppressed in action)");
    } catch (Throwable e) {
      rethrow = e;
    } finally {
      rethrow = Close.ifPossible(rethrow, b);
      rethrow = Close.ifPossible(rethrow, a);
    }

    if (rethrow != null) {
      System.err.println("The program failed: " + rethrow.getMessage());

      for (Throwable s : rethrow.getSuppressed()) {
        System.err.println("\tsuppressed: " + s.getMessage());
      }

      return; // explicitly stop execution
    }

    System.out.println("More instructions...");
  }
}

Resource B is created such as it throws on closing. Resource A throws during writing.

Running this example gives:

A: created
B: created
B: close() called
A: closed
The program failed: Failed to write: A
        suppressed: Failed to close: B

The close operation was invoked in both resources.

And the close exception thrown by B was added as a suppressed exception to the exception thrown by A.

`AutoCloseable`

Before we go I would like to write a few words on the AutoCloseable type.

As you can see in its Javadocs it was introduced in Java 7.

It marks types that are allowed to be used as resources in try-with-resources statements. It is defined in the try-with-resources section of the Java language specification:

The type of a local variable declared in a resource specification, or the type of an existing variable referred to in a resource specification, must be a subtype of AutoCloseable, or a compile-time error occurs.

Before its introduction there was no standard interface to indicate that a type had a method that had to be invoked in order for resources to be released. Yes, there was the Closeable interface introduced in Java 5.

By the way, Closeable was retrofitted to extend AutoCloseable.

But not all "things that can be closed" implemented it. For instance:

java.util.zip.ZipFile. It had a close() method throwing IOException in Java 6. But it did not implement Closeable. Compare the javadocs: Java 6 vs. Java 7
java.sql.Connection, java.sql.Statement and java.sql.ResultSet. All had a close() method throwing SQLException in Java 6. But they did not implement a common interface. In Java 7 they all implemented AutoCloseable. Compare the javadocs for the Statement interface: Java 6 vs. Java 7

Conclusion

In this blog post we took a in-depth look in the try-with-resources Java statement.

We saw problems that can arise from the plain try statement when dealing with resources that must be closed programmatically. With this we wanted to understand what issues the try-with-resources was meant to address.

We then presented its formal definition in the Java language specification. We tried to understand it by rewriting it using the plain try statement and a small closing utility. In the process we saw two API changes introduced in Java 7 to support it:

suppressed exceptions
the AutoCloseable interface

Finally we saw some examples of JDK classes that were modified so they could be used with the try-with-resources statement.

The full source code of the examples listed in this post can be found in this GitHub repository.

How to implement a hash table in Java (Part 4)

Marcio Endo — Fri, 28 Oct 2022 11:11:05 +0000

We left the previous post of this series with a mostly functional hash table. The latest iteration of the hash table is capable of performing both put and get operations, it handles hash collisions and it is capable of replacing the value of existing mappings.

However, it still has a major limitation: we cannot add more than four distinct mappings to it. The hash table falls into an infinite loop when we try to "put" a fifth mapping. This was discussed during iteration #11.

To overcome this limitation our hash table needs to automatically increase its capacity. The capacity is the number of buckets in the hash table.

So, in this fourth and last post of our series, we will improve our hash table: it must increase its capacity as needed.

Let's continue.

Before we continue

While not strictly required, I recommend reading the previous parts of this series if you haven't already:

In particular:

the "Writing style" section of Part 1 explains why the examples are written the way they are; and
the "Iteration 11: infinite loop?" section of Part 3 show the problem our hash table currently has.

Iteration 13: resizing the arrays is not enough

Increasing the capacity of a hash table involves more steps than increasing the capacity of for e.g. an array list.

So, before we go into the proper solution, let's see why the array list solution does not work for a hash table.

Iteration 13: test case

Let's start with the following test case:

public class HashTableTest {
  @Test(description = """
  Why do we need a rehash operation?
  """)
  public void iter13() {
    var ht = new HashTable<Key, String>();

    var a = new Key("AAA", 1);
    var b = new Key("BBB", 12);
    var c = new Key("CCC", 23);
    var d = new Key("DDD", 34);
    var e = new Key("EEE", 45);

    ht.put(a, "aaa");
    ht.put(b, "bbb");
    ht.put(c, "ccc");
    ht.put(d, "ddd");
    ht.put(e, "eee");

    assertEquals(ht.get(a), "aaa");
    assertEquals(ht.get(b), "bbb");
    assertEquals(ht.get(c), "ccc");
    assertEquals(ht.get(d), "ddd");
    assertEquals(ht.get(e), "eee");
  }
}

We put five mappings into our hash table. Remember it caused an infinite loop during iteration #11.

We proceed and verify that we are able to retrieve the correct values associated to each key.

Iteration 13: the (incorrect) implementation

As mentioned in the section's title, simply resizing the array is not enough. To see why, the following implementation does exactly it:

// does not work!
final class HashTable<K, V> extends iter12.HashTable<K, V> {
  @Override
  protected final V putInsert(K key, V value, int bucket) {
    V result = super.putInsert(key, value, bucket);

    if (size == keys.length) {
      resize();
    }

    return result;
  }

  // does not work!
  private void resize() {
    var newLength = keys.length << 1;

    keys = Arrays.copyOf(keys, newLength);

    values = Arrays.copyOf(values, newLength);
  }
}

We override the putInsert method. The putInsert method is invoked during a put operation when a new mapping is to be stored in the hash table. The implementation of putInsert was discussed in Part 1.

After the new mapping has been inserted, we verify whether our hash table is full or not. If our hash table is full, the resize method is invoked.

The resize method creates new and larger copies of the keys and of the values array. It uses the Arrays::copyOf method. The copies have a larger length newLength that is the double of the previous length.

Iteration 13: running our test

Running our test fails:

java.lang.AssertionError: expected [bbb] but found [null]
    at org.testng.Assert.fail(Assert.java:110)
    at org.testng.Assert.failNotEquals(Assert.java:1413)
    at org.testng.Assert.assertEqualsImpl(Assert.java:149)
    at org.testng.Assert.assertEquals(Assert.java:131)
    at org.testng.Assert.assertEquals(Assert.java:655)
    at org.testng.Assert.assertEquals(Assert.java:665)
    at iter13.HashTableTest.iter13(HashTableTest.java:43)

While the five "put" operations seem to have been successful, assertion fails at the second "get" operation.

So what is happening?

Iteration 13: bucket is a function of the capacity

Remember our current hash function (implemented during iteration #06):

@Override
protected int bucket(Object key) {
  int hc = key.hashCode();

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

Given an existing key in the hash table its computed bucket is a function of:

the key's hash code value; and
the hash table capacity.

Therefore, if we are to increase the capacity of the hash table, the computed bucket of an existing key changes.

Consider the five Key instances of our test:

var a = new Key("AAA", 1);
var b = new Key("BBB", 12);
var c = new Key("CCC", 23);
var d = new Key("DDD", 34);
var e = new Key("EEE", 45);

With the initial capacity of 4, applying the keys to the bucket method yields:

Key(AAA, 1)  = 1
Key(BBB, 12) = 0
Key(CCC, 23) = 3
Key(DDD, 34) = 2
Key(EEE, 45) = 1

On the other hand, when the capacity is increased to 8, the same keys produce the following values:

Key(AAA, 1)  = 1
Key(BBB, 12) = 4
Key(CCC, 23) = 7
Key(DDD, 34) = 2
Key(EEE, 45) = 5

So, after the hash table capacity is increased, key b is expected to be at bucket idx = 4. However, it is still at bucket idx = 0. The test, therefore, fails.

So how can we solve this?

Iteration 13: resize and rehash

After the capacity is increased all of the existing mappings have to be rehashed. In other words:

the buckets for all of the entries in the hash able must be recomputed; and
all of the existing key-value pairs must be relocated to the new, recomputed buckets.

This constitutes what is called a rehash operation.

Iteration 14: a proper rehash operation

Now that we have discussed the rehash operation, let's go and implement a proper one for our hash table.

Before we do, we need to answer two questions:

when should our hash table grow? and
by what factor should the capacity increase?

Let's discuss the first of the questions.

Iteration 14: space-time tradeoff

So, when should our hash table grow? In other words, when should the rehash operation occur?

At first, it might seem reasonable for the answer to be "when the hash table is full". However, consider the following example:

var ht = new HashTable<Key, String>();

var a = new Key("AAA", 1);
var b = new Key("BBB", 5);

ht.put(a, "aaa");
ht.put(b, "bbb");

assertEquals(
  ht.toString(),
  """
  +-----+-----+-----+
  | idx | key | val |
  +-----+-----+-----+
  |   0 |     |     |
  |   1 | AAA | aaa |
  |   2 | BBB | bbb |
  |   3 |     |     |
  +-----+-----+-----+
  """
);

Even though keys a and b have distinct hash code values, they cause a hash collision for the initial capacity of 4. Both keys want to stay at bucket idx = 1.

On the other hand, if our hash table had a capacity of 6 we would expect the following disposition:

assertEquals(
  ht.toString(),
  """
  +-----+-----+-----+
  | idx | key | val |
  +-----+-----+-----+
  |   0 |     |     |
  |   1 | AAA | aaa |
  |   2 |     |     |
  |   3 |     |     |
  |   4 |     |     |
  |   5 | BBB | bbb |
  +-----+-----+-----+
  """
);

In other words, no collisions!

So, considering keys a and b, when the hash table capacity is 4:

we use less memory (as our arrays are smaller); but
put and get operations are slower (as they have to resolve hash collisions);

On the other hand, when the capacity is 6:

put and get operations are optimal; but
we use more memory (as our arrays are larger).

This represents what is called a space-time tradeoff.

So resizing the hash table "when it is full" might not be best option.

Iteration 14: a quick note on iteration

We will not implement any iteration. In other words, from the Map interface, we will not implement for e.g.:

the keySet method;
the entrySet method; nor
the values method.

But, regarding iteration, as indirectly provided by such methods, I'd like to note on the following.

Consider two hash table instances:

they both contain the same mappings; but
one has a capacity that is greater than the other.

Iteration over keys, entries or values will be faster for the hash table having the smaller capacity. Remember, they both contain the same key-value pairs.

So, while put and get operations can be "faster" for higher capacities; iterations are definitely slower.

This is another space-time tradeoff regarding hash tables.

Iteration 14: the load factor

In a hash table, the "when to grow?" question is controlled by the load factor. The HashMap documentation presents the following defintion:

The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

A usual load factor value is 0.75. This is, for instance, the default load factor of the HashMap class.

And what does it mean for a hash table to have a load factor of 0.75?

It means that, when the number of mappings in the hash table exceeds three quarters of its capacity, the internal arrays are resized. As our hash table has a initial capacity of 4, it must increase the number of available buckets when the fourth (distinct) mapping is stored.

Iteration 14: the growth factor

The second question we have to answer before writing our test case is:

by what factor should our capacity increase?

As we will discuss during the next iteration, we have reasons to want a capacity that is a power of two number.

So, during the rehash operation, we will simply double the hash table capacity.

Iteration 14: test case

Having our two questions answered:

our hash table will have a load factor of .75; and
we will double the hash table capacity.

We proceed to writing our test case.

We start by creating three distinct Key instances. We associate them to their respective names in lowercase.

public class HashTableTest {
  @Test(description = """
  put() test case

  - load factor = 0.75
  - should resize on 4th insert
  - no hash collisions
  """)
  public void iter14() {
    var ht = new HashTable<Key, String>();

    var a = new Key("AAA", 2);
    var b = new Key("BBB", 6);
    var c = new Key("CCC", 3);

    assertEquals(ht.put(a, "aaa"), null);
    assertEquals(ht.put(b, "bbb"), null);
    assertEquals(ht.put(c, "ccc"), null);

    // more...
  }
}

The hash code values of the three keys are chosen so that:

keys a and b will want to occupy the same bucket idx = 2; and
key c will try to stay at bucket idx = 3. But, by the time it is mapped, its bucket is already taken by key b.

assertEquals(
  ht.toString(),
  """
  +-----+-----+-----+
  | idx | key | val |
  +-----+-----+-----+
  |   0 | CCC | ccc |
  |   1 |     |     |
  |   2 | AAA | aaa |
  |   3 | BBB | bbb |
  +-----+-----+-----+
  """
);

We verify the expected internal disposition by asserting on the toString output.

At this point, we have three quarters of the buckets occupied. Therefore, the hash table will need to be resized after the fourth distinct mapping is associated:

var d = new Key("DDD", 8);

assertEquals(ht.put(d, "ddd"), null);
assertEquals(ht.size(), 4);

assertEquals(
  ht.toString(),
  """
  +-----+-----+-----+
  | idx | key | val |
  +-----+-----+-----+
  |   0 | DDD | ddd |
  |   1 |     |     |
  |   2 | AAA | aaa |
  |   3 | CCC | ccc |
  |   4 |     |     |
  |   5 |     |     |
  |   6 | BBB | bbb |
  |   7 |     |     |
  +-----+-----+-----+
  """
);

We expect the capacity to be 8.

And, with such capacity, we expect no hash collisions. "Manually" computing the expected buckets we have:

Key("AAA", 2) => 2 % 8 = 2
Key("BBB", 6) => 6 % 8 = 6
Key("CCC", 3) => 3 % 8 = 3
Key("DDD", 8) => 8 % 8 = 0

Iteration 14: running our test

Our test fails when it is run against the implementation of the previous iteration. Here is the (slightly edited) error message:

java.lang.AssertionError: expected [
+-----+-----+-----+
| idx | key | val |
+-----+-----+-----+
|   0 | DDD | ddd |
|   1 |     |     |
|   2 | AAA | aaa |
|   3 | CCC | ccc |
|   4 |     |     |
|   5 |     |     |
|   6 | BBB | bbb |
|   7 |     |     |
+-----+-----+-----+
] but found [
+-----+-----+-----+
| idx | key | val |
+-----+-----+-----+
|   0 | CCC | ccc |
|   1 | DDD | ddd |
|   2 | AAA | aaa |
|   3 | BBB | bbb |
+-----+-----+-----+
]
    at org.testng.Assert.fail(Assert.java:110)
    at org.testng.Assert.failNotEquals(Assert.java:1413)
    at org.testng.Assert.assertEqualsImpl(Assert.java:149)
    at org.testng.Assert.assertEquals(Assert.java:131)
    at org.testng.Assert.assertEquals(Assert.java:655)
    at org.testng.Assert.assertEquals(Assert.java:665)
    at iter14.HashTableTest.iter14(HashTableTest.java:61)

So, the put operation with key d succeeds but the capacity remains unchanged.

Iteration 14: implementation

And here is an implementation that makes our test pass:

public class HashTable<K, V> extends iter12.HashTable<K, V> {
  private int rehashSize = 3;

  @Override
  protected final V putInsert(K key, V value, int bucket) {
    V result = super.putInsert(key, value, bucket);

    if (size > rehashSize) {
      rehash();
    }

    return result;
  }

  @SuppressWarnings("unchecked")
  private void rehash() {
    var capacity = keys.length << 1;

    if (capacity < 0) {
      throw new OutOfMemoryError();
    }

    var oldKeys = keys;

    var oldValues = values;

    keys = new Object[capacity];

    values = new Object[capacity];

    rehashSize = (int) (capacity * 0.75);

    size = 0;

    for (int i = 0; i < oldKeys.length; i++) {
      var key = oldKeys[i];

      if (key == null) {
        continue;
      }

      var value = oldValues[i];

      put0((K) key, (V) value);
    }
  }
}

Let's discuss each section of the code individually.

Iteration 14: the `rehashSize` field

The hash table has a new rehashSize field:

public class HashTable<K, V> extends iter12.HashTable<K, V> {
  private int rehashSize = 3;

  ...
}

It answers our "when should our hash table grow?" question. In other words, the rehash operation must occur when the number of mappings, the hash table size property, exceeds the value given by rehashSize.

Its value is given the product of the load factor and the _capacity. As for our hash table:

the load factor is 0.75; and
the initial capacity is 4.

The rehashSize is initialized to the value 3.

Iteration 14: rehash after a `put` operation (if necessary)

Let's now focus on the putInsert method:

@Override
protected final V putInsert(K key, V value, int bucket) {
  V result = super.putInsert(key, value, bucket);

  if (size > rehashSize) {
    rehash();
  }

  return result;
}

Remember, the putInsert method is invoked when a new key-value pair is to be stored in the hash table.

Before returning the original result it verifies if the current size exceeds the rehashSize. When that is the case it invokes the rehash method.

The technique of rehashing after a new mapping has been inserted is the same used by the HashMap class.

Iteration 14: the `rehash` method

The rehash method, as the name implies, performs the rehash operation.

@SuppressWarnings("unchecked")
private void rehash() {
  var capacity = keys.length << 1;

  if (capacity < 0) {
    throw new OutOfMemoryError();
  }

  var oldKeys = keys;

  var oldValues = values;

  keys = new Object[capacity];

  values = new Object[capacity];

  rehashSize = (int) (capacity * 0.75);

  size = 0;

  for (int i = 0; i < oldKeys.length; i++) {
    var key = oldKeys[i];

    if (key == null) {
      continue;
    }

    var value = oldValues[i];

    put0((K) key, (V) value);
  }
}

It starts by computing the new capacity:

var capacity = keys.length << 1;

if (capacity < 0) {
  throw new OutOfMemoryError();
}

The new capacity is the double of the current capacity. If the capacity overflows, it throws an OutOfMemoryError.

With the new capacity, it then creates two new backing array instances:

var oldKeys = keys;

var oldValues = values;

keys = new Object[capacity];

values = new Object[capacity];

But, before creating the new arrays, it saves a reference to the old ones in two variables.

As the capacity has changed, the rehashSize field is updated accordingly:

rehashSize = (int) (capacity * 0.75);

As mentioned before, its value is given by the product of the load factor and the hash table capacity.

Then, finally, all of the existing entries are rehashed:

size = 0;

for (int i = 0; i < oldKeys.length; i++) {
  var key = oldKeys[i];

  if (key == null) {
    continue;
  }

  var value = oldValues[i];

  put0((K) key, (V) value);
}

This is done by iterating over all of the entries in the hash table. Each key-value pair is then reinserted into the hash table by invoking the put0 method. Before the iteration occurs, the hash table's size is reset to zero.

The put0 method is invoked by the put method after the key and value have been null-checked. It was defined during iteration #02:

public final V put(K key, V value) {
  Objects.requireNonNull(key, "key == null");
  Objects.requireNonNull(value, "value == null");

  return put0(key, value);
}

Iteration 14: a quick note on the load factor

In the spirit of keeping things simple, the load factor in our implementation is a constant. Its value of 0.75 is "hard coded" and cannot be changed.

Keep in mind, however, that the load factor is a property of a hash table. In other words, it is a value that can be configured.

As an example, the HashMap class offers a constructor that allows for creating an instance with a custom load factor:

// hash map with capacity = 32 and load factor = 0.6
var map = new HashMap<Key, String>(32, 0.6f);

Iteration 14: a quick note on the `HashMap::newHashMap` factory

Since JDK 19, the HashMap class offers a new factory method:

// argument is the number of expected mappings, i.e., key-value pairs.
var map = HashMap.<Key, String> newHashMap(10);

In the example, the returned map will be large enough to hold 10 mappings. It has the default load factor of 0.75. Therefore, its capacity will be greater than the supplied argument of 10. The capacity will be given by dividing the number of mappings by the load factor:

              10  <-- no. of mappings
capacity = -----
            0.75  <-- load factor

It is different from the constructor:

// argument is the initial _capacity_
var map = new HashMap<Key, String>(10);

In this case, the argument 10 is the initial capacity (actual capacity will be a power of two number).

Also note that the former will invoke the latter.

Iteration 15: a small improvement to our hash function

We have mentioned a few times about the power-of-two choice for the hash table's capacity. We will finally use this fact to our advantage.

In this iteration we will refactor the bucket method and introduce a small improvement to our hash function.

Iteration 15: test case

As this is a refactoring, we will not write a test case.

Iteration 15: the current hash function

The current hash function was implemented during iteration #06:

@Override
protected int bucket(Object key) {
  int hc = key.hashCode();

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

Remember that, when the key's hash code value is a positive integer, the code is equivalent to:

int hc = key.hashCode();

return hc % keys.length;

It is the remainder of the division of the key's hash code value by the capacity (number of buckets).

Iteration 15: remainder of the division by a power-of-ten number

Suppose a positive integer number represented in base 10. For example:

We can "visually" compute the remainder of its division by a power-of-ten number:

123456 %    123456 %    123456 % 
    10         100        1000
------      ------      ------
     6          56         456

And so on. Rewriting the divisor in "powers of ten" (and a different presentation) we have:

123456 mod 10^1 =   6
123456 mod 10^2 =  56
123456 mod 10^3 = 456

So, to obtain the remainder, we get the rightmost n digits. Where n is the exponent of the divisor.

We can apply an analogous procedure when the divisor is a power-of-two number. Except the dividend has to be represented in base 2.

Iteration 15: remainder of the division by a power-of-two number

Let's consider the number 27 our dividend. The divisors will be the power-of-two numbers 2, 4, 8 and 16. As a "cheat sheet" the following are the modulus results in base 10:

27 mod  2 =  1 
27 mod  4 =  3
27 mod  8 =  3
27 mod 16 = 11

In binary the number 27 is represented by:

Let's apply the same procedure from the previous section:

11011 %    11011 %    11011 %    11011 %
   10        100       1000      10000
-----      -----      -----      -----
    1         11        011       1011

Or, if you prefer:

11011 mod 00010 =    1
11011 mod 00100 =   11
11011 mod 01000 =  011
11011 mod 10000 = 1011

Which matches our cheat sheet as:

dec  |  bin
-----+-----
1    | 0001
3    | 0011
3    | 0011
11   | 1011

Iteration 15: remainder as a bitwise AND operation

Our current example:

11011 %    11011 %    11011 %    11011 %
   10        100       1000      10000
-----      -----      -----      -----
    1         11        011       1011

Can be rewritten as:

11011 &    11011 &    11011 &    11011 &
   01        011       0111      01111
-----      -----      -----      -----
    1         11        011       1011

Where the operation & is the bitwise AND operation.

Notice how the divisor from the first form turned into the bitwise complement in the second form:

NOT    10 =    01
NOT   100 =   011
NOT  1000 =  0111
NOT 10000 = 01111

And as the operand is a power-of-two number, the NOT operation is equivalent to "minus one" subtraction:

00010 - 1 =    01
00100 - 1 =   011
01000 - 1 =  0111
10000 - 1 = 01111

Written as Java code we have:

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

    var mask = keys.length - 1;

    return hc & mask;
  }
}

This is the technique used by the HashMap class.

Iteration 15: advantages?

What is the advantage, if any, of using the "bitwise AND" approach over the Math::floodMod one?

Simply put, the bitwise AND solution is much faster than the Math::floorMod one.

Suppose a hash table for which the keys are String values. As an example, we will use three HTTP request header field names as keys. The following lists their names associated with their String hash code values.

User-Agent      = -1844712829
Accept-Encoding = -1099743112
Connection      =  1217813246

We write the following JMH benchmark:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(1)
@State(Scope.Benchmark)
public class Benchmarks {
  @Param({"-1844712829", "-1099743112", "1217813246"})
  public int hashCode;

  public int capacity = 16;

  @Benchmark
  public int bitwiseAnd() {
    var mask = capacity - 1;

    return hashCode & mask;
  }

  @Benchmark
  public int floorMod() {
    return Math.floorMod(hashCode, capacity);
  }
}

The benchmark computes the bucket of our keys for a hypothetical hash table with a capacity of 16. It does so using both the "bitwise AND" method and the floorMod one.

It produces the following on my machine:

Benchmark                      (hashCode)  Mode  Cnt   Score   Error  Units
Benchmarks.bitwiseAnd         -1844712829  avgt    5   1.256 ± 0.002  ns/op
Benchmarks.bitwiseAnd         -1099743112  avgt    5   1.286 ± 0.255  ns/op
Benchmarks.bitwiseAnd          1217813246  avgt    5   1.351 ± 0.542  ns/op
Benchmarks.floorMod           -1844712829  avgt    5  19.164 ± 0.036  ns/op
Benchmarks.floorMod           -1099743112  avgt    5  19.159 ± 0.036  ns/op
Benchmarks.floorMod            1217813246  avgt    5  19.157 ± 0.033  ns/op

The bitwise AND version takes a around 1.2ns per operation. The floorMod version, on the other hand, takes around 19.1ns per operation. So the former is faster than the latter (even when considering the higher error of the former).

Iteration 16: putting it all together

We have developed our hash table in a series of incremental steps. It helped making each increment visible.

It has, however, a drawback.

A test from an earlier iteration is not run against the code of a later iteration. In other words, the test from iteration #05, for example, may never touch the code written during iteration #10.

Therefore, as a final step, we will:

combine all of the tests in a single test class; and
combine all of the hash table in a single HashTable class.

Having done that, we will verify whether all of the tests continue to pass.

Iteration 16: test case

The test case is written by simply combining the test from each iteration in a single test file:

public class HashTableTest {
  @Test(description = """
  size() method

  - empty hash table must return 0
  """)
  public void iter01() {
    ...
  }

  @Test(description = """
  put() method

  - it must reject null keys
  - it must reject null values
  """)
  public void iter02() {
    ...
  }

  // iterations #03 to #14

  @Test(description = """
  put() test case

  - refactor bucket() method
  """)
  public void iter15() {
    ...
  }
}

For brevity we've only listed a small section of the test. If you are interested, you can find the full version here.

Iteration 16: implementation

The following is a small section of our implementation:

public final class HashTable<K, V> {
  private Object[] keys = new Object[4];

  private Object[] values = new Object[4];

  private int size;

  private int rehashSize = 3;

  @SuppressWarnings("unchecked")
  public final V get(Object key) {
    Objects.requireNonNull(key, "key == null");

    var bucket = bucket(key);

    var candidate = keys[bucket];

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

    return get0(key, bucket, candidate);
  }

  ...

  private int bucket(Object key) {
    var hc = key.hashCode();

    var mask = keys.length - 1;

    return hc & mask;
  }

  private V get0(Object key, int bucket, Object candidate) {
    if (candidate == null) {
      return null;
    }

    return get1(key, bucket);
  }

  ...
}

Once again, for brevity reasons, only a small section of the code is listed. You can find the full version here.

Two things are worth noting when compared to the versions of previous iterations:

the class does not have an extends declaration; and
protected fields and methods are all private in this version.

Running the test against this implementation passes.

Great!

Conclusion

And we are done!

In this four part blog post series we have implemented a bare-bones hash table in Java that:

supports both the put and the get methods as defined by the Map interface;
rejects null keys and null values;
uses linear probing for handling hash collisions; and
dynamically resizes (and rehashes) itself when required.

We additionally implemented both the size and the toString methods as testing aids.

The source code for all of the examples in this post can be found at this GitHub repository.

How to implement a hash table in Java (Part 3)

Marcio Endo — Fri, 21 Oct 2022 12:02:06 +0000

In the previous post of this series we've improved on the initial version of our hash table. It is capable of:

"putting" mappings;
"getting" mappings; and
replacing the value of existing mappings.

However, it still misses a major functionality: it does not handle hash collisions yet.

That's what we will work on during this third post of our series. We will have our hash table handle hash collisions during both put and get operations.

Let's continue.

Before we continue

While not strictly required, I recommend reading the previous parts of this series if you haven't already:

In particular:

the "Writing style" section of Part 1 explains why the examples are written the way they are; and
the "Iteration 06: hash collision" section of Part 2 gives a brief explanation of what a hash collision is.

Iteration 09: two testing conveniences

In order to properly test that our hash table is capable of handling hash collisions we need:

an easy way to create key values capable of causing hash collisions; and
a way to assert the internal disposition of our hash table contents.

Therefore, in this iteration, we will introduce two testing conveniences:

a Key class for causing hash collisions; and
a toString implementation for displaying the contents of our hash table.

Iteration 09: the `Key` class

Two distinct keys a and b are guaranteed to cause a hash collision in our hash table if:

they are distinct, i.e., !a.equals(b) evaluates to true; and
they both have the same hash code values, i.e., a.hashCode() == b.hashCode() evaluates to true.

The following class allows to easily create instances satisfying these criteria:

public final class Key {
  private final String value;

  private final int hash;

  public Key(String value, int hash) {
    this.value = value;
    this.hash = hash;
  }

  @Override
  public final boolean equals(Object obj) {
    return obj == this
        || obj instanceof Key that
            && Objects.equals(value, that.value);
  }

  @Override
  public final int hashCode() { return hash; }

  @Override
  public final String toString() { return value; }
}

As an example, the following test passes:

var a = new Key("A", 123);
var b = new Key("B", 123);

assertNotEquals(a, b);
assertEquals(a.hashCode(), 123);
assertEquals(b.hashCode(), 123);

Of course the class also makes it easy to violate the equals and hashCode contract.

For example, we can easily create two instances that are equal to each other but have distinct hash code values. This is a violation of the hashCode contract.

Keep in mind we are only using it to cause hash collisions in a testing environment. In other words, I am not advocating for the use of a class like this one in production.

Iteration 09: test case

Let's now focus on the toString method. Here's our test case:

public class HashTableTest {
  @Test(description = """
  toString() method

  - renders an ascii table with columns:

  1. array index
  2. key toString()
  3. value toString()
  """)
  public void iter09() {
    var ht = new HashTable<Key, String>();

    var a = new Key("AAA", 4);
    var c = new Key("CCC", 6);

    ht.put(a, "aaa");
    ht.put(c, "ccc");

    assertEquals(
      ht.toString(),
      """
      +-----+-----+-----+
      | idx | key | val |
      +-----+-----+-----+
      |   0 | AAA | aaa |
      |   1 |     |     |
      |   2 | CCC | ccc |
      |   3 |     |     |
      +-----+-----+-----+
      """
    );
  }
}

First, we create two instances, a and c, of our Key class. As seen in the previous section, their hash code values are given by the constructor's second argument. The hash code values were chosen so that the mapping stays at a known array index. Given their values, we know that:

key a will be stored at index idx = 0; and
key c will be stored at index idx = 2.

Remember, we know how our hash function is implemented. We also know the length of the internal keys and values arrays. Therefore, we can "manually" compute the array index.

Next, we associate the keys to their values.

We then write how we want the toString output to look like. It is a table showing the internal contents of our hash table. It has three columns:

the array index
the key toString output
the value toString output

When the key and the value are null their respective table cells are blank.

Iteration 09: implementation

Here's an implementation that make the test pass:

public class HashTable<K, V> extends iter08.HashTable<K, V> {
  @Override
  public final String toString() {
    var sb = new StringBuilder();

    sb.append(
      """
      +-----+-----+-----+
      | idx | key | val |
      +-----+-----+-----+
      """);

    for (int idx = 0; idx < keys.length; idx++) {
      var key = keys[idx];

      if (key != null) {
        var value = values[idx];

        sb.append("| %3d | %3s | %3s |\n".formatted(idx, key, value));
      } else {
        sb.append("| %3d |     |     |\n".formatted(idx));
      }
    }

    sb.append("+-----+-----+-----+\n");

    return sb.toString();
  }
}

It starts by writing the table header.

It then loops through the keys array. If a non-null key is found, it writes, in order, the current array index, the key itself and the mapped value. If the key is null it only writes the array index.

It ends by writing the table footer.

Iteration 10: handling hash collision during `put` operations

Let's (at last) begin the implementation of the hash collision handling code of our hash table. We'll focus on put operations initially.

In this iteration we will put a series of distinct mappings that "want to stay in the same bucket".

Iteration 10: test case

With the help of our Key class created earlier, we create our test case:

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

  - handle hash collisions
  - no value replacement
  """)
  public void iter10() {
    var ht = new HashTable<Key, String>();

    var a = new Key("AAA", 2);
    var b = new Key("BBB", 2);
    var c = new Key("CCC", 2);

    assertEquals(ht.put(a, "aaa"), null);
    assertEquals(ht.put(b, "bbb"), null);
    assertEquals(ht.put(c, "ccc"), null);

    assertEquals(
      ht.toString(),
      """
      +-----+-----+-----+
      | idx | key | val |
      +-----+-----+-----+
      |   0 | CCC | ccc |
      |   1 |     |     |
      |   2 | AAA | aaa |
      |   3 | BBB | bbb |
      +-----+-----+-----+
      """
    );
  }
}

We create three Key instances a, b and c in such way that:

they are all distinct to each other; and
they all produce the same hash code value.

Therefore, keys a, b and c are guaranteed to cause hash collisions in our hash table. When associated with a value via the put method, they will all try to occupy the bucket idx = 2.

But, of course, only a single key can occupy that bucket at any given time. In other words, the first put will occupy the bucket; the keys of the subsequent put operations will have to look for alternative buckets.

The final internal disposition in our hash table is given by the toString assertion. How did we get to this exact disposition depicted by the toString output?

Iteration 10: linear probing

As all of the keys in our current test produce the same hash code value, they will all try to occupy the same bucket.

The hash table is empty when we associate key a to its value. So the a mapping occupies the bucket with index idx = 2.

When we try to associate key b to its value, that bucket it is already taken by key a. So we have key b occupy the next empty cell in the array. The next empty bucket is the one with index idx = 3 and that's where the b mapping is stored.

When we try to associate key c to its value it also wants to stay at bucket idx = 2. As it is occupied by key a, it tries the next cell. As the next cell is occupied by key b it tries the next cell.
Except there's no next cell: we are at the end of the array. So it tries again from the start of the array, idx = 0. As idx = 0 is empty that's where key c stays.

So that's how we got to the toString assertion:

assertEquals(
  ht.toString(),
  """
  +-----+-----+-----+
  | idx | key | val |
  +-----+-----+-----+
  |   0 | CCC | ccc |
  |   1 |     |     |
  |   2 | AAA | aaa |
  |   3 | BBB | bbb |
  +-----+-----+-----+
  """
);

This technique of resolving hash collisions by "probing" for the next empty cell is called linear probing. You should know that there are more ways to handle hash collisions. This is just one of the possible solutions.

In the JDK, the following JDK classes use the same linear probing solution:

The first is the one returned by the Map.of methods when two or more mapping are specified. The second is the one returned by the Set.of methods when three or more elements are specified. I should note that these are the values returned by the methods at time of writing.

Iteration 10: running our test

Running our test against the previous implementation fails:

java.lang.UnsupportedOperationException: Implement me
    at iter07.HashTable.put2(HashTable.java:29)
    at iter07.HashTable.put1(HashTable.java:25)
    at iter03.HashTable.put0(HashTable.java:39)
    at iter02.HashTable.put(HashTable.java:25)
    at iter10.HashTableTest.iter10(HashTableTest.java:38)

It reaches a branch of our code we did not implement yet. The stack trace indicates it is part of the code written during iteration #07.

Iteration 10: implementation

The following code makes our current test pass:

public class HashTable<K, V> extends iter09.HashTable<K, V> {
  @Override
  protected V put2(K key, V value, int bucket) {
    var index = bucket + 1;

    while (true) {
      if (index == keys.length) {
        index = 0;
      }

      var existing = keys[index];

      if (existing == null) {
        return putInsert(key, value, index);
      }

      index++;
    }
  }
}

It overrides the put2 method created during iteration #07. This method is invoked with an unresolved hash collision. The parameters are:

key = the key the put method was invoked with;
value = the value the put method was invoked with; and
bucket = the computed array index for key.

Being a hash collision the specified bucket index is already occupied by a mapping. We need to look for an empty bucket.

Iteration 10: looking for an empty bucket

We start looking at the next adjacent bucket:

var index = bucket + 1;

The index variable indicates our current array index candidate.

The search itself is done in a while loop:

while (true) {
  if (index == keys.length) {
    index = 0;
  }

  ...

  index++;
}

At the very end of the loop the index variable is incremented. So, if an empty bucket is not found at the current candidate, we continue the search with the next one.

Except index might already be the last index of the array. When this is the case, we have to continue the search from the beginning of the array. That's the responsibility of the if statement at the beginning of the loop.

At the "core" of the loop, we test the current index candidate:

var existing = keys[index];

if (existing == null) {
  return putInsert(key, value, index);
}

If the hash table contains no mappings at the current index candidate it means we have found our bucket. We proceed to store the specified key-value pair, at the current index, by invoking the putInsert method.

Iteration 11: hash collisions and value replacements

During iteration #07 of Part 2 we allowed the put method to replace the value of an existing mapping.

In this iteration we will implement the same use-case. Except we will do it for a mapping participating in a hash collision.

Iteration 11: test case

Here's our test case:

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

  - hash collision
  - value replacement
  """)
  public void iter11() {
    var ht = new HashTable<Key, String>();

    var a = new Key("AAA", 2);
    var b = new Key("BBB", 2);

    assertEquals(ht.put(a, "aaa"), null);
    assertEquals(ht.put(b, "123"), null);
    assertEquals(ht.put(b, "bbb"), "123", "\n" + ht.toString());

    var c = new Key("CCC", 3);

    assertEquals(ht.put(c, "ccc"), null);

    assertEquals(
      ht.toString(),
      """
      +-----+-----+-----+
      | idx | key | val |
      +-----+-----+-----+
      |   0 | CCC | ccc |
      |   1 |     |     |
      |   2 | AAA | aaa |
      |   3 | BBB | bbb |
      +-----+-----+-----+
      """
    );
  }
}

We create two Key instances. Keys a and b are guaranteed to cause a hash collision.

We start by associating key a to the "aaa" string value.

Then, immediately after we associate key b to the "123" value, we replace its value with "bbb". As this is a replacement operation, we verify that the put method returns the previous value.

Finally, to additionally verify the correctness of our put method implementation, we associate the "ccc" value to key c. Unlike keys a and b, key c wants to stay at index idx = 3. In other words, it does not cause a hash collision with neither key a nor key b. But, as its "natural bucket" is already taken by key b, it must be put in an alternative location. So it is stored at the beginning of the array.

Iteration 11: running the test

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

java.lang.AssertionError: 
+-----+-----+-----+
| idx | key | val |
+-----+-----+-----+
|   0 | BBB | bbb |
|   1 |     |     |
|   2 | AAA | aaa |
|   3 | BBB | 123 |
+-----+-----+-----+
 expected [123] but found [null]
    at org.testng.Assert.fail(Assert.java:110)
    at org.testng.Assert.failNotEquals(Assert.java:1413)
    at org.testng.Assert.assertEqualsImpl(Assert.java:149)
    at org.testng.Assert.assertEquals(Assert.java:131)
    at org.testng.Assert.assertEquals(Assert.java:655)
    at iter11.HashTableTest.iter11(HashTableTest.java:39)

The test fails: the put method does not return the previous mapping.

In fact, observing the error message, it seems our hash table now contains different mappings for the same key.

Iteration 11: implementation

Here's an implementation that makes our test pass:

public class HashTable<K, V> extends iter10.HashTable<K, V> {
  @Override
  protected final V put2(K key, V value, int bucket) {
    var index = bucket + 1;

    while (true) {
      if (index == keys.length) {
        index = 0;
      }

      var existing = keys[index];

      if (existing == null) {
        return putInsert(key, value, index);
      } 

      if (existing.equals(key)) {
        return putReplace(key, value, index);
      }

      index++;
    }
  }
}

Once again, we override the put2 method. It is the same method we worked on during the previous iteration.

The implementation is almost identical to the one from the last iteration. The difference is an additional if statement:

var existing = keys[index];

...

if (existing.equals(key)) {
  return putReplace(key, value, index);
}

It tests whether existing is equal to the specified key. When the test evaluates to true, the corresponding mapped value must be replaced. We do so by invoking the putReplace method.

Iteration 11: infinite loop?

You may have noticed that our while statement contains an always true expression:

while (true) {
  ...
}

So, unless one of the return statements in its "body" is executed, the while statement will run indefinitely. In fact, we can create a test case that does just that:

@Test(enabled = false, description = """
put() method

- guaranteed to cause an infinite loop
""")
public void iter11_infiniteLoop() {
  var ht = new HashTable<Key, String>();

  var a = new Key("AAA", 2);
  var b = new Key("BBB", 2);
  var c = new Key("CCC", 2);
  var d = new Key("DDD", 2);
  var e = new Key("EEE", 2);

  ht.put(a, "aaa");
  ht.put(b, "bbb");
  ht.put(c, "ccc");
  ht.put(d, "ddd");
  ht.put(e, "eee");
}

Notice that we are trying to put more mappings than the hash table's capacity of 4.

The infinite loop is expected in this case. And there's nothing wrong (as far as I can tell) with our while loop.

The actual problem is that our hash table does not grow to accommodate more mappings. If the arrays are large enough, then an empty bucket will always be found.

Don't worry. We will implement the resize operation in the next post of this series.

Iteration 12: handling hash collision during `get` operations

We are done implementing the hash collision handling for put operations.

We can now focus on the get operation. Let's now have our get method support retrieving the values associated to keys that cause hash collisions.

Iteration 12: test case

This is our test case:

public class HashTableTest {
  @Test(description = """
  get() test case

  - hash collision
  - non existing key
  """)
  public void iter12() {
    var ht = new HashTable<Key, String>();

    var a = new Key("AAA", 3);
    var b = new Key("BBB", 3);
    var c = new Key("CCC", 3);

    assertEquals(ht.put(a, "aaa"), null);
    assertEquals(ht.put(b, "bbb"), null);
    assertEquals(ht.put(c, "ccc"), null);

    assertEquals(ht.get(a), "aaa");
    assertEquals(ht.get(b), "bbb");
    assertEquals(ht.get(c), "ccc");

    var d = new Key("DDD", 3);

    assertEquals(ht.get(d), null);
  }
}

The first section of our test is very similar to the one we wrote during iteration #10:

we create three Key instances that produce the same hash code value; and
we proceed to associate a distinct value to each key.

Next, we try to retrieve the values we have just inserted by invoking the get method. We verify that the value returned is the one we expect it to be.

For completeness, we verify that the get method returns null when the hash table does not contain a mapping for the specified key:

var d = new Key("DDD", 3);

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

Note that key d has the same hash code value as the other three keys. In other words, if we were to put it in our map, it would cause a hash collision at the same bucket as the other keys.

Iteration 12: running our test

As expected, running our test against the current implementation fails:

java.lang.UnsupportedOperationException: Implement me
    at iter08.HashTable.get1(HashTable.java:29)
    at iter08.HashTable.get0(HashTable.java:25)
    at iter04.HashTable.get(HashTable.java:33)
    at iter12.HashTableTest.iter12(HashTableTest.java:42)

It reaches the method get1. It was left unimplemented during iteration #08.

Iteration 12: implementation

The following is the iteration's implementation:

public class HashTable<K, V> extends iter11.HashTable<K, V> {
  @SuppressWarnings("unchecked")
  @Override
  protected final V get1(Object key, int bucket) {
    var index = bucket + 1;

    while (true) {
      if (index == keys.length) {
        index = 0;
      }

      var existing = keys[index];

      if (existing == null) {
        return null;
      }

      if (key.equals(existing)) {
        return (V) values[index];
      }

      index++;
    }
  }
}

We override the get1 method created during iteration #08. It is called when a hash collision occurs during a get operation. The parameters are:

key = the key the get method was invoked with; and
bucket = the computed array index for key.

Iteration 12: looking for the specified `key`

The implementation is very similar to the one of the put operation:

In fact, the "outer layer" is identical to the put operation: we perform the search in a while loop starting at the next adjacent bucket.

var index = bucket + 1;

while (true) {
  if (index == keys.length) {
    index = 0;
  }

  ...

  index++;
}

The differences are in the "core" of the loop.

If the current bucket is empty, it means our hash table does not contain the specified key. We must return null in this case:

var existing = keys[index];

if (existing == null) {
  // empty bucket == key not found
  return null;
}

On the other hand, if the bucket is not empty and the stored existing key is equal to the specified key, it means we have found the key. In this case, we return the corresponding value from the values array:

var existing = keys[index];
...
if (key.equals(existing)) {
  // we've found the key!
  // return the corresponding value
  return (V) values[index];
}

In the next blog post of this series

In this third blog post of our series our hash table is finally capable of handling hash collisions. We have implemented the linear probing technique for both the put and the get operations.

But the implementation is still incomplete. Trying to put a fifth mapping to our hash table causes an infinite loop.

To fix this issue, our hash table needs to dynamically grow so it can store more mappings. In doing so, all of the key-value mappings must be re-inserted.

This is what we call a rehash operation and will be the topic of the next and final blog post of this series.

Stay tuned!

The source code for all of the examples in this post can be found at this GitHub repository.

How to implement a hash table in Java (Part 2)

Marcio Endo — Fri, 14 Oct 2022 10:34:36 +0000

In the first post 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 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 of this series if you haven't already. The "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:

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 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 during iteration #03.

The problem is in our current bucket method implementation:

// 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:

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:

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?" 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:

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.

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:

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 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:

  return hc % keys.length;

when the hash code value hc is negative, it might give a distinct result than:

  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:

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:

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.

Iteration 07: implementation

Here's an implementation that make our test pass:

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.
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:

@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:

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:

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. To be more precise, it fails because it reaches a branch left unimplemented during that iteration:

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:

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.

How to implement a hash table in Java (Part 1)

Marcio Endo — Fri, 07 Oct 2022 13:16:50 +0000

If you are developing an application in Java chances are you are currently using an implementation of java.util.Map or java.util.Set in your programs.

When you use any of the following you are using a hash table data structure in your program:

java.util.HashMap
java.util.HashSet which internally just delegates to a HashMap
java.util.ImmutableCollections.MapN as returned by the Map.of methods
java.util.ImmutableCollections.SetN as returned by the Set.of methods
java.util.EnumMap

These are only a few of the examples from the JDK; the JDK has more hash-based implementations.

I've always wanted to know the details of how a hash table work. I find the HashMap source code to be quite difficult to parse though. So I was a bit intimidated to try and implement one.

I have read this blog post from Ben Hoyt sometime last year. It describes the implementation of a hash table structure in the C programming language. It encouraged me to try and implement one in Java from scratch.

So, in this blog series, I will guide you through the implementation of a hash table in Java.

Introduction

Before we begin, just a couple of notes.

Not quite like a `HashMap`

I should preface saying the hash table we will implement is going to be somewhat different from java.util.HashMap.

It will still give a good understanding (hopefully) of the internals. But, implementation-wise, it will be closer to:

java.util.ImmutableCollections.MapN as returned by the Map.of methods;
java.util.ImmutableCollections.SetN as returned by the Set.of methods; and to
java.util.EnumMap

Writing style

We will create our hash table implementation in a series of small steps. Each iteration will add on top of the previous one.

We want each increment to be visible. In other words, we want to easily see what has changed from the previous step.

To achieve this goal we will have the implementation from one step extend the one from the previous step. This may be quite particular.

Keep in mind the sole purpose of this usage is to make each change from a previous iteration more apparent.

In other words, I am not advocating for the use of this technique in production code.

A small set of requirements

So we know where we are headed to, let's write down a small set of requirements.

We will implement a very small subset of the java.util.Map interface. Representing it as a Java interface we would have the following:

public interface HashTable<K, V> {
  V put(K key, V value);

  V get(Object key);

  int size();
}

Please note that, to keep things simple, we will create our implementation directly as a class. The interface is listed only to show the methods we want to implement.

Our target is to implement three methods: the put, the get and the size methods. I should note that the size method is not strictly required. But it will help writing some of the assertions along the way so we will implement it.

As an additional and final requirement our implementation must reject null keys and null values. Rejecting null keys in particular will simplify our implementation.

Iteration 01: the size() method implementation

We want to implement our hash table in a series of small steps. So it is fitting for our first step to be to implement the size method.

Iteration 01: test case

Let's start with a test case. It verifies that a newly created hash table has a size of zero:

public class HashTableTest {
  @Test(description = """
  size() method

  - empty hash table must return 0
  """)
  public void iter01() {
    var ht = new HashTable<Object, Object>();
    assertEquals(ht.size(), 0);
  }
}

Note that we are not "putting" nor "getting" anything from our hash table. For this reason the types of the keys and of the values are not important. So, in this test, our hash table instance simply maps an Object to another Object.

Iteration 01: implementation

The implementation is trivial. It makes our test pass:

public class HashTable<K, V> {
  protected int size;

  public final int size() { return size; }
}

The only thing to notice is that the visibility of size field: protected. It is required so that subclasses can directly read or modify its value.

Iteration 02: reject `null` keys and `null` values

As a next step let's implement the requirement that our hash table must reject both null keys and null values. It means we will implement a first version of the put method. Granted, it will not do much yet.

Iteration 02: test case

Once again, we start with a test case:

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

  - it must reject null keys
  - it must reject null values
  """)
  public void iter02() {
    var ht = new HashTable<String, String>();
    assertEquals(ht.size(), 0);

    try {
      ht.put(null, "non-null value");

      Assert.fail("Expected a NPE");
    } catch (NullPointerException expected) {
      assertEquals(expected.getMessage(), "key == null");
    }

    try {
      ht.put("non-null key", null);

      Assert.fail("Expected a NPE");
    } catch (NullPointerException expected) {
      assertEquals(expected.getMessage(), "value == null");
    }

    assertEquals(ht.size(), 0);
  }
}

We first verify that an attempt to put a null key and a non-null value fails with a NullPointerException. Next, we verify that a null value (with a non-null key) also causes a NullPointerException to be thrown. In both cases we verify that the exception contains the expected error message.

Finally, we verify that the hash table did not change by asserting its size remains zero. Note that this is not really sufficient to verify that no key-value mappings were added. But, at the moment, it is all we can do.

Iteration 02: implementation

Here's an implementation that make our test pass:

public class HashTable<K, V> extends iter01.HashTable<K, V> {
  public final V put(K key, V value) {
    Objects.requireNonNull(key, "key == null");
    Objects.requireNonNull(value, "value == null");

    return put0(key, value);
  }

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

The first thing to notice is that this class is a subclass of the implementation of the previous iteration. I mentioned this at the beginning of the post. We want to easily see what has changed from the previous iteration.

And what has changed from the previous iteration? We created a put implementation that rejects both null keys and null values.

If, on the other hand, both the key and the value are non-null, it continues execution by calling a put0 method. At this iteration the put0 method simply throws an UnsupportedOperationException.

Iteration 03: `put` key-value mappings (happy path)

We handled the put method preconditions in the previous section. Now we will actually add key-value mappings to our hash table exercising a happy path.

Our happy path consists of:

each inserted key-value pair is stored at a distinct bucket (i.e., no hash collisions);
each inserted key-value pair is distinct from each other (i.e., no value replacements); and
the hash code values are all positive

If you don't know what a hash collision is, don't worry. We will discuss it in this series.

Iteration 03: test case

We start with a test case.

Given the requirements of our test, let's use Integer instances as keys. The hash code value of a Integer object is simply the int value it wraps. Integer instances, therefore, make it easy to define an exact hash code value for our key.

Here's our test listing:

public class HashTableTest {
  @Test(description = """
  put() and size() methods

  - positive hash codes
  - no hash collisions
  - no value replacements
  """)
  public void iter03() {
    var ht = new HashTable<Integer, String>();
    assertEquals(ht.size(), 0);

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

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

We start by creating a hash table instance that maps Integer values to their names in English.

We add two key-value mappings to our hash table; and, since there are no value replacements, we assert that the put method returns null. Remember the Javadocs for put method. The put method returns:

the previous value associated with key, or null if there was no mapping for key.

Additionally, we verify that the size of our hash table increases by one after each key-value insertion.

Iteration 03: implementation

And here's an implementation that makes our third test pass:

public class HashTable<K, V> extends iter02.HashTable<K, V> {
  protected Object[] keys = new Object[4];

  protected Object[] values = new Object[4];

  protected int bucket(Object key) {
    var hc = key.hashCode();

    return hc % keys.length;
  }

  @Override
  protected final V put0(K key, V value) {
    var bucket = bucket(key);

    var existing = keys[bucket];

    if (existing == null) {
      return putInsert(key, value, bucket);
    }

    return put1(key, value, bucket, existing);
  }

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

  protected V putInsert(K key, V value, int bucket) {
    keys[bucket] = key;

    values[bucket] = value;

    size++;

    return null;
  }
}

Let's take a closer look into the implementation.

Iteration 03: the `keys` and `values` arrays

Our class declares two arrays of the same length: keys and values. As their names indicate they are used to store the key-value mappings. A key-value pair mapping is stored at the two arrays in the following manner:

the keys array holds the key of the mapping;
the values array holds the value of the mapping;
both arrays have the same length; and
the index bucket at which the key and value are stored are the same.

In other words, a single key-value pair can be stored like so:

keys[bucket] = key;
values[bucket] = value;

Similarly, a single key-value pair can be read like so:

var key = keys[bucket];
var value = values[bucket];

The following diagram illustrates a possible disposition for the mappings 1=One and 2=Two.

--------|-------+-------+-------+-------+
  index:|     0 |     1 |     2 |     3 |
--------|-------+-------+-------+-------+  
   keys:|       |     1 |     2 |       |
--------|-------+-------+-------+-------+
 values:|       | "One" | "Two" |       |
--------|-------+-------+-------+-------+

But how is the bucket index computed?

Iteration 03: the initial array length

Before we look into the bucket method, notice how the hash table arrays were both initialized with a length of 4:

protected Object[] keys = new Object[4];

protected Object[] values = new Object[4];

The choice of a power-of-two number is not a coincidence.
We will look into it later. For now, just consider it an arbitrary positive value.

Iteration 03: the `bucket` method

The bucket method is responsible for computing the index.
At this iteration the method returns the remainder of the division between the key's hash code value and the keys array length.

// the iter 03 'incomplete' implementation
protected int bucket(Object key) {
  var hc = key.hashCode();

  return hc % keys.length;
}

As an example, consider the following:

the keys array length is 4; and
the specified key has a positive hash code value

Then the bucket variable will hold a value between:

zero (inclusive); and
the keys length (exclusive).

These are all of the valid values for the indices of the keys array. And, as keys and values have the same length, these are also all of the valid values for the indices of the values array.

As a final note I should mention that the implementation of this iteration is known to be incomplete. It fails to handle negative hash code values. We will look into it during iteration #05.

Iteration 03: is this a new mapping?

With the bucket index computed, the put0 method goes on to verify if hash table contains the specified key or not. It does so by checking if the keys array component at that index is null.

var bucket = bucket(key);

var existing = keys[bucket];

if (existing == null) {
  // new mapping
  return putInsert(key, value, bucket);
}

...

Remember, our hash table disallows null keys; so if a component of the keys array is null, it means there is no existing mapping at that location.

Iteration 03: the `putInsert` method

The actual insertion is done at the putInsert method. After storing both the specified key and value it increments the hash table's size value by one and returns null.

protected V putInsert(K key, V value, int bucket) {
  keys[bucket] = key;

  values[bucket] = value;

  size++;

  return null;
}

Iteration 03: same key or collision?

If the keys array component at the computed index is non-null, it means that either:

we have the same key at the bucket (and possibly a distinct value); or
we have a distinct key at the same bucket.

if (existing == null) {
  return putInsert(key, value, bucket);
}

// what to do here?
return put1(key, value, bucket, existing);

We will look into those situations in a moment. For now, we throw an UnsupportedOperationException just in case we inadvertently reach this branch.

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

Iteration 03: a note on the two arrays

In our hash table implementation we are storing the keys and the values in two distinct arrays. While I try to have code as closer to "real-life" as possible, this is a blog post. In other words, I believe the "easy to understand" requirement is more important.

In a more "production-ready" hash table implementation, however, we would probably store the key-value pairs in a single array. For an example from the JDK see java.util.ImmutableCollections.MapN.

One reason would be to reduce memory requirements of our hash table:

the hash table would have one less field; and
having one less array, it would require one less array object header.

A second reason would be to (probably) improve performance.
I am sorry I do not have much to add on this topic as I do not know much about performance. I believe it relates to this article but don't take my word for it.

Iteration 04: `get` the value mapped to a key (happy path)

We have implemented the put method for a happy path. Let's now implement the get method for the same case:

the hash table contains the key-value mapping. In other words, the get method will return a non-null value;
no hash collisions; and
positive hash code values.

Iteration 04: test case

We start with a test case once more:

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

  - hash table contains the mapping
  - no hash collisions
  - positive hash codes
  """)
  public void iter04() {
    var ht = new HashTable<Integer, String>();
    assertEquals(ht.size(), 0);

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

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

The test is very similar to the one from the previous iteration. The difference is that we verify that the hash table has correctly stored the key-value pairings. We do so by invoking the get method for each stored key: we expected it to return the correct value.

Iteration 04: implementation

And here's an implementation that make our fourth test pass:

public class HashTable<K, V> extends iter03.HashTable<K, V> {
  @SuppressWarnings("unchecked")
  public final V get(Object key) {
    Objects.requireNonNull(key, "key == null");

    var bucket = bucket(key);

    var candidate = keys[bucket];

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

    return get0(key, bucket, candidate);
  }

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

Let's look at our get implementation.

It starts by rejecting null keys. The Javadocs of the get(Object key) method states that it should throw a NullPointerException:

if the specified key is null and this map does not permit null keys

Next, it invokes the bucket method created in the previous iteration. Remember that this method computes and returns the array index at which to store the specified key.

So, if the specified key is equal to the value at the index returned by the bucket method, it means our hash table contains a mapping for the specified key. In this case it returns the corresponding value from the values array.

Note that the expression in the if statement is "null-safe" as key is guaranteed to be non-null.

If the expression evaluates to false then our get method invokes the get0 method. For this iteration it simply throws a UnsupportedOperationException.

In the next blog posts of this series

We have a bare-bones hash table implementation so far. We are able to both "put" and "get" mappings, albeit in a very limited set of conditions.

In the next blog posts of this series, among other things, we will:

handle keys with negative hash code values
handle hash collisions
perform a rehash operation, i.e., resize the inner arrays so our hash table can hold more mappings.

Stay tuned.

The source code of all of the examples can be found in this GitHub repository. It also contains the draft code for the upcoming posts.

Things I didn't know about Java: Generic Constructors

Marcio Endo — Mon, 25 Jul 2022 11:13:39 +0000

Later this year I will work again on Objectos Code. It is a library for generating Java source code. At time of writing, it is still unreleased and alpha-quality. Using a code similar to the following planned one:

import static objectos.code.Java.*;

_var(id("foo"), _new(Foo.class, l(1), l("abc")));

Would generate the following Java statement:

var foo = new Foo(1, "abc");

Whenever I work on it, I have to study the Java Language Specification. In the previous example, I need to know what the actual formal definition of a new expression is. Its formal name is Class Instance Creation Expression, defined in section 15.9. A relevant production is the following:

UnqualifiedClassInstanceCreationExpression:
  new [TypeArguments] ClassOrInterfaceTypeToInstantiate ( [ArgumentList] ) [ClassBody]

As you can see, there is an optional list of type arguments immediately after the new keyword. I did not know about that. The following java class compiles:

public class OptionalTypeArgumentsExample {
  public static void main(String[] args) {
    var t = new <String> Thread();

    t.start();
  }
}

The Eclipse JDT compiler issues a warning about an unused type argument. On the other hand, javac (OpenJDK 18.0.1.1) compiles it without warnings:

$ javac -Xlint:all src/main/java/iter1/OptionalTypeArgumentsExample.java
[no warnings emitted]

So what is this? JLS section 15.9 states (emphasis mine):

If the constructor is generic (§8.8.4), the type arguments to the constructor may similarly either be inferred or passed explicitly.

Ah, so constructors can be generic. Well, I did not about that either. I think we should investigate that.

So, in this blog post I will give you a quick overview of generic constructors.

Generic constructors are rarely used (in the JDK)

As I have never seen generic constructors before I wanted to know how "real-world" code uses them. So I wrote a program that parses the Java files in the JDK source code. It uses the JavaParser open-source library. Since its README file mentions Java 15, I ran the program on tag jdk-15+36 of the JDK source code.

I found seven classes having generic constructors. They are all in the java.management module. Four classes are exported (and therefore have Javadocs):

While three of the classes are internal:

Therefore one can safely say generic constructors are rarely used. At least in the JDK source code.

Still... it gives a glimpse on how to use them

Let's study the signature of one of those constructors.
For example, let's take this one from the OpenMBeanAttributeInfoSupport class. Its signature is:

public <T> OpenMBeanParameterInfoSupport(
  String name, String description,
  OpenType<T> openType, T defaultValue)
  throws OpenDataException

The Javadocs for the type parameter <T> says:

T - allows the compiler to check that the defaultValue, if non-null, has the correct Java type for the given openType.

So the type parameter in the constructor prevents mixing incompatible types. In other words, the following code to compiles:

OpenType<Foo> openType = getOpenType();
Foo foo = getFoo();
var o = new OpenMBeanParameterInfoSupport(
  "A Name", "Some description", openType, foo);

As OpenType<Foo> is compatible with Foo. However, the following code fails to compile:

OpenType<Foo> openType = getOpenType();
Bar bar = getBar();
var o = new OpenMBeanParameterInfoSupport(
  "A Name", "Some description", openType, bar);
// compilation error                      ^^^

As OpenType<Foo> is not compatible with Bar.

Great, let's try to create an example using same idea. It should make things clearer.

A simple example

Suppose we have a Payload class that represents arbitrary data to be sent over the wire. For example, It could be JSON data to be sent over HTTPS. To keep our example simple, we will model the data as a String value. Additionally, since our data is immutable, we will use a Java record:

public record Payload(String data) {}

So, if we were to send a "Hello world!" message over the wire, we could invoke a hypothetical send method like so:

send(new Payload("Hello world!"));

The actual JSON payload sent by our hypothetical service is not important for our example. But, for completeness sake, let's suppose the JSON data sent in our previous example was:

{
  "data": "Hello world!"
}

That's great. Next, let's add a little complexity to our data.

Sending other data types

Suppose now we want to send data that is both structured and more complex than our previous "Hello world!" message. For example, we want to send a simplified log message represented by the following Java record:

public record Log(long millis, Level level, String msg) {}

This data is structured in the sense that its JSON format is defined by the following converter:

public class LogConverter {
  public String convert(Log log) {
    return """
    {
      "millis": %d,
      "level": "%s",
      "msg": "%s"
    }
    """.formatted(log.millis(), log.level(), log.msg());
  }
}

To send our log record we could just:

var converter = new LogConverter();
var log = new Log(12345L, Level.INFO, "A message");
var data = converter.convert(log);
send(new Payload(data));

But we expect more data types each with its own structure. That is, each data type will bring its own converter. So, let's refactor our Payload record.

Enter the generic constructor

Since each data type will have its own converter there is a chance to use a generic constructor like so:

public record Payload(String data) {
  public <T> Payload(Function<T, String> converter, T item) {
    this(converter.apply(item));
  }
}

The converter is represented by a Function from a generic type T to a String. Our parameterized constructor ensures that the second argument's type is compatible with the converter.

So let's use our new constructor. The following test does just that:

@Test
public void data() {
  var converter = new LogConverter();
  var log = new Log(12345L, Level.INFO, "A message");
  var p = new Payload(converter::convert, log);

  assertEquals(p.data(), """
  {
    "millis": 12345,
    "level": "INFO",
    "msg": "A message"
  }
  """);
}

Good, our test passes. Granted, there is very little difference to the previous example using the canonical constructor. But it does its job as an example of generic constructors.

Invoking generic constructors

In our last example we invoked our generic constructor just like we do with a non-generic one. In other words, we did not provide explicit type arguments to our generic constructor. The actual type arguments were inferred by the compiler.

We can be explicit if we wanted. That is, we can provide a type argument list to the generic constructor.

Providing type arguments with the `new` keyword

Taking again our last example, we can provide explicit type arguments. So the class instance creation becomes:

var p = new <Log> Payload(converter::convert, log);

Notice the <Log> right after the new keyword. Providing explicit type arguments means that the following code does not compile:

var converter = new LogConverter();
var log = new Log(12345L, Level.INFO, "A message");
var p = new <Category> Payload(converter::convert, log);
// compilation error           ^^^                 ^^^

The compiler tries to match the actual arguments to a "virtual" constructor having the following signature:

public Payload(Function<Category, String> converter, Category item);

As the types are not compatible, compilation fails.

Providing type arguments with the `this` or `super` keyword

Apart from the class instance creation expression (i.e., new keyword), there are other ways to invoke constructors. In particular, constructors themselves can invoke other constructors:

a constructor in the same class using this; and
a constructor from the superclass using super.

But what happens if the invoked constructor is generic? Let's investigate.

Here's the production from Section 8.8.7.1 of the JLS:

ExplicitConstructorInvocation:
  [TypeArguments] this ( [ArgumentList] ) ;
  [TypeArguments] super ( [ArgumentList] ) ;
  ExpressionName . [TypeArguments] super ( [ArgumentList] ) ;
  Primary . [TypeArguments] super ( [ArgumentList] ) ;

As suspected, both this and super can be invoked with a type arguments list.

So let's try it with our Payload record. We can add a specialized constructor for a Log instance like so:

public record Payload(String data) {
  public <T> Payload(Function<T, String> converter, T item) {
    this(converter.apply(item));
  }

  static final Function<Log, String> LOG_CONVERTER
      = LogConverter.INSTANCE::convert;

  public Payload(Log log) {
    <Log> this(LOG_CONVERTER, log);
  }
}

We added an invocation to the other constructor in the same class. It supplies a type argument to it:

public Payload(Log log) {
  <Log> this(LOG_CONVERTER, log);
}

This means that the following code does not compile:

public Payload(Log log) {
  <LocalDate> this(LOG_CONVERTER, log);
  // error         ^^^            ^^^
}

As the compiler tries to match the actual arguments to a "virtual" constructor having the following signature:

public Payload(Function<LocalDate, String> converter, LocalDate item);

As the types are not compatible, compilation fails.

Caveat with `new` keyword and diamond form

Section 15.9 of the JLS has the following in bold:

It is a compile-time error if a class instance creation expression provides type arguments to a constructor but uses the diamond form for type arguments to the class.

Let's investigate. Here's a small Java program:

public class Caveat<T> {
  public <E> Caveat(T t, E e) {}

  public static void main(String[] args) {
    var t = LocalDate.now();
    var e = "abc";

    new <String> Caveat<>(t, e);
  }
}

The class Caveat is generic on <T>. It declares a single constructor which is generic on <E>. In the main method it tries to create a new instance of the Caveat class.

Let's compile it:

$ javac src/main/java/iter3/Caveat.java
src/main/java/iter3/Caveat.java:17: error: cannot infer type arguments for Caveat<T>
    new <String> Caveat<>(t, e);
                       ^
  reason: cannot use '<>' with explicit type parameters for constructor
  where T is a type-variable:
    T extends Object declared in class Caveat
1 error

Here's the explanation from the JLS:

This rule is introduced because inference of a generic class's type arguments may influence the constraints on a generic constructor's type arguments.

To be honest, I was not able to understand it. In any case, to fix the compilation error we replace the diamond form:

new <String> Caveat<LocalDate>(t, e);

With an explicit <LocalDate>. The code now compiles.

Conclusion

In this blog post we discussed a few topics on generic constructors. A feature of the Java language I did not know until recently.

We have seen how it is rarely used in the JDK source code. Is it safe to extrapolate and say that it is rarely used in general? I personally believe it is. But don't take my word for it.

We then saw an example exercising a possible use-case.

Finally, we saw how to invoke generic constructors using:

new keyword; and
this keyword (which can be equally applied to the super keyword).

The source code of the examples in this post can be found in this GitHub repository.

Originally published at the Objectos Software Blog on July 18^th, 2022.

Follow me on twitter.

DEV Community: Marcio Endo

Creating a static site using pure Java. Objectos 0.5.1 released

Before we begin

Creating a static site using pure Java

Our template

Generating our static site

Running our example

Objectos Code: allow annotations in field declarations

Until the next issue of Objectos Weekly

Objectos Weekly #005: Java's contextual keywords, class names and method names

Contextual keywords

Reserved keywords

Backward compatibility

List of contextual keywords

Contextual keywords and class names

Contextual keywords and method names

Why though?

Until the next issue of Objectos Weekly

Objectos Weekly #004: Type annotations, canonical names and inner classes

Type annotations, canonical names and inner classes

Referring to the superclass by its canonical name

Fixing the compilation error

Why though?

Extending an inner class of Super

Objectos Code Weekly

Method type parameters and type variables

Parameterized types

Until the next issue of Objectos Weekly

OW #003: A type annotation curiosity, the qualified superclass constructor invocation and more

Does this an annotation apply to the type or to the declaration?

The qualified superclass constructor invocation

What if we subclass the Inner class?

Objectos Code Weekly

Simple Box type

Nested classes

Chained methods

Until the next issue of Objectos Weekly

LWO #002: Annotations are just modifiers, array access curiosity, faux code generators and more

Annotations are just modifiers (grammatically speaking)

An Array Access Expression curiosity

Faux code generators

Last week in Objectos Code

Lambda inclusion support

Constructor declarations, assignment expressions, and field access expressions

More enum declarations

Until the next edition

LWO #001: Objectos Code API revamp, and a use of Java's sealed interfaces

Objectos Code API revamp

The new API

Consistent API across Objectos' libraries

Work on Objectos Code

Initial enum declaration support

Initial field declaration support

A (somewhat) type-safe API

Using Java's sealed interfaces

Until the next edition

In-depth look: the Java try-with-resources statement

What problems did the try-with-resources solve?

Our running example

Single resource

Two resources

Two resources: error on creation

Two resources: error on closing

Two resources: exception during the try block

What's in a try-with-resources statement?

Java Language Specification (JLS) 18

A closing utility

Suppressed exception

Rewriting our two resources try examples

Restricting the catch-all to catch IOException only

Suppressed exception example

AutoCloseable

Conclusion

How to implement a hash table in Java (Part 4)

Before we continue

Iteration 13: resizing the arrays is not enough

Iteration 13: test case

Iteration 13: the (incorrect) implementation

Iteration 13: running our test

Iteration 13: bucket is a function of the capacity

Extending an inner class of `Super`

What if we subclass the `Inner` class?

Simple `Box` type

What problems did the `try-with-resources` solve?

Two resources: exception during the `try` block

What's in a `try-with-resources` statement?

Rewriting our two resources `try` examples

Restricting the catch-all to catch `IOException` only

`AutoCloseable`

Iteration 14: the `rehashSize` field

Iteration 14: rehash after a `put` operation (if necessary)

Iteration 14: the `rehash` method

Iteration 14: a quick note on the `HashMap::newHashMap` factory

Iteration 09: the `Key` class

Iteration 10: handling hash collision during `put` operations

Iteration 12: handling hash collision during `get` operations

Iteration 12: looking for the specified `key`

Iteration 07: the `putReplace` method