MAL - Preliminaries

There are a number of functions we'll use for S-expressions generically, like computing the hash code for an S-expression. (We could, further, cache this as metadata in the struct Object.)

/* types.h */
typedef int hash_t;

hash_t hashCode(Object *object);
bool equals(Object *lhs, Object *rhs);

The contracts we demand of these functions:

• Let Object *x, *y be non-null. If equals(x, y) is true, then hashCode(x) == hashCode(y).
  • We do not require the inverse of this proposition — i.e., we do not require if equals(x, y) is false, then hashCode(x) != hashCode(y).
• The equals() function is an equivalence relation, so
  • Reflexivity: for any non-null Object *x, we have equals(x, x)
  • Symmetry: for non-null Object *x, *y, if equals(x, y), then equals(y, x)
  • Transitivity: for non-null Object *x, *y, *z, if equals(x, y) and equals(y, z), then we have equals(x, z)
• Further, for any non-null Object *x and Object *null = NULL, we have equals(x, NULL) and Object(x, null) both return false
• We have consistency:
  • equals(): for any non-null Object *x, *y we have equals(x, y) return the same value if we compute it repeatedly without any other computation in between
  • hashCode(): for any non-null Object *x, we have hashCode(x) return the same value if called repeatedly and no other computation occurs in between these calls

• Java Objects Inside Out
• Ruby Internals: Exploring the Memory Layout of Ruby Objects
• CLR (Managed object internals)
• Python Common Object Structures

Primitive values would naively be represented by structures like:

/* types.h */
struct Int {
    Object header;
    int value;
};

struct Char {
    Object header;
    char codepoint;
};

struct Boolean {
    Object header;
    bool value;
};

These will be two words in size. There are tricks to compactify their memory usage (NaN boxing, tagged object pointers since x64 uses 48-bit addresses giving us 16 bits of metadata).

There are several different ways to represent a string. C uses a null-terminated sequence of characters. Pascal uses length-prefixed strings — by convention, the first k bytes are interpreted as an integer, encoding the length of the string. C++ (and, I guess, Java) encodes a string as a record (well, Java uses classes). We'll follow the structure encoding:

/* types.h */
typedef struct String String;

String* string_new(char *str, int length);
void string_free(String **string);
bool string_isEqual(String *this, String *other);
hash_t string_hashCode(String *this);

The constructor string_new takes an additional parameter, length, which tells us how many characters to take from the source. The special value of length < 0 will copy until a null character is encountered.

The string API can be extended as necessary.

The data structure for a string would be implemented as:

/* types.c */
struct String {
    Object header;
    size_t length;
    char *text;
};

We intern symbols to make at most one object which corresponds with a symbol name. This could be done using a Hash Table, a binary tree, or some other data structure.

/* types.h */
typedef struct Symbol Symbol;

Symbol* intern(char *name);
void symbol_free(Symbol **symbol);
hash_t symbol_hashCode(Symbol *this);

We make public the symbol_free() function, though we may want to hide it, and make some method to register it with the garbage collector hidden from the user.

Again, we are using opaque pointers (since it's good style):

/* types.c */

struct Symbol {
    Object header;
    String *name;
};

The contract is, for any non-empty strings x and y such that they are equal (in the sense that 0 == strcmp(x, y)), then we have intern(x) == intern(y) and specifically intern(x) != NULL.

The constructor works as we would expect: allocate the memory for the header and addresses. If one of the arguments is NULL, then its double pointer will point to NULL.

/* types.c */
Cons* cons_new(Object *car, Object *cdr) {
    Cons *cell = alloc(sizeof(*cell));
    cell->header.type = TYPE_CONS;
    cell->car = (NULL == car) ? NULL : &car;
    cell->cdr = (NULL == cdr) ? NULL : &cdr;
    return cell;
}

This requires a bit more care. We'll iterate through the list, recursively freeing the car and cdr, before finally freeing the wrapper and metadata for the Cons cell itself.

/* types.c */
void cons_free(Cons **this) {
    if ((NULL == this) || (NULL == *this)) return;
    obj_free((*this)->car);
    //@ assert (\null == \old(*this)->car) || (\null == *((*this)->car));
    obj_free((*this)->cdr);
    //@ assert (\null == \old(*this)->cdr) || (\null == *((*this)->cdr));
    free(*this);
    (*this) = NULL;
}

The basic computation amounts to

hash_t list_hashCode(List *this) {
    hash_t hashCode = 1;
    for (Elt e : this)
        hashCode = 31*hashCode + ((NULL == e) ? 0 : hashCode(e));
    return hashCode;
}

The actual source code implementation needs to handle the special case where cell == nil, when it should be zero.

/* types.c */
hash_t cons_hashCode(Cons *cell) {
    if (NULL == cell) return 0;

    hash_t h = 1;
    Object *car = safe_car(cell);
    Object *cdr = safe_cdr(cell);

    if ((NULL == car) && (NULL == cdr)) {
        h = 0;
    } else {
        h = 31*h + hashCode(car);
        h = 31*h + hashCode(cdr);
    }
    return h;
}

We test for equality by checking the car of the left-hand side equals the car of the right-hand side, and the cdr of both sides are equal. Component-wise equality, in other words.

/* types.c */
bool cons_equals(Cons *lhs, Cons *rhs) {
    if (lhs == rhs) return true;
    if (NULL == lhs) return false;
    if (NULL == rhs) return false;

    if (equals(safe_car(lhs), safe_car(rhs))) {
        return equals(safe_cdr(lhs), safe_cdr(rhs));
    }
    return false;
}

We will use simple chaining. The idea is to use an array of buckets (a bucket is a linked list of "Entries" — key-value pairs plus some extra metadata), associating a key-value pair to exactly one bucket. When there are too many entries, we increase the number of buckets, then rebalance the entries.

The constructor expects no parameters. The default capacity for a hash map would be 16, its initial size 0.

/* types.c */

#define INITIAL_HASH_MAP_CAPACITY 16 /* must be power of 2 */

HashMap* hashmap_new() {
    HashMap *map = alloc(sizeof(*map));
    map->header.type = TYPE_HASH_MAP;
    map->capacity = INITIAL_HASH_MAP_CAPACITY;
    map->size = 0;
    map->table = alloc_array(sizeof(struct Entry*), map->capacity);
    return map;
}

When we destroy a HashMap object, we also have to iteratively destroy the table entries.

/* types.c */

void hashmap_free(HashMap **this) {
    if ((NULL == this) || (NULL == *this)) return;

    for (size_t row = 0; row < (*this)->capacity; row++) {
        Entry *iter = (*this)->table[row];
        while (NULL != iter) {
            Entry *next = iter->next;
            entry_free(iter);
            iter = next;
        }
    }

    free(*this);
    (*this) = NULL;
}

We then need to isolate a helper function to get the index for a given hash code. Since our code makes sure there are 2ⁿ buckets in the table, we can use the fact hash % length == hash & (length - 1). Using bitwise-and is faster than the modulo operator.

/* types.c */

static size_t indexFor(hash_t hash, size_t length) {
    return hash & (length - 1);
}

Now the process for obtaining the value for a given key is quite straightforward traversing the linked list ("bucket") selected by that index, and when finding that key, returning the associated value:

/* types.c */

Object* hashmap_get(HashMap *this, Object *key) {
    assert (NULL != this);

    hash_t h = hashCode(key);
    size_t index = indexFor(h, this->capacity);
    for (Entry *e = this->table[index]; e != NULL; e = e->next) {
        if (equals(key, e->key)) {
            return e->value;
        }
    }
    return NULL;
}

We associate a value to a key in a given hash map by finding the bucket associated for the hash code for that key. First, we try finding the key in that bucket of entries by simple traversal. If we're lucky, it's already associated with a value. In that case, we just update the entry to point to the new value, and return the old value.

But if that bucket has not been started (so it's a null pointer) or if the bucket does not contain the key, then we create a new entry, and prepend it to that row of the table. Since no value is associated to the key, we return a null pointer.

/* types.c */

#define CAPACITY_FACTOR 0.75

static void resize(HashMap *this, size_t new_capacity);

Object* hashmap_put(HashMap *this, Object *key, Object *value) {
    assert(NULL != this);

    hash_t h = hashCode(key);
    size_t index = indexFor(h, this->capacity);
    Entry *entry = this->table[index];
    if (NULL != entry) {
        // try updating the value associated to key, if key is present
        Entry *e = entry;
        while (e != NULL) {
            if ((e->hash == h) && equals(keys, e->key)) {
                Object *old_val = e->value;
                e->value = value;
                return old_val;
            }
            e = e->next;
        }
        // fall-through: no key associated with that value, then prepend entry
    }
    // key is not present, so add entry
    Entry *new_entry = entry_new(key, value, h);
    // entry_insert(&(this->table[index]), new_entry);
    new_entry->next = this->table[index];
    this->table[index] = new_entry;
    this->size++;

    if ((this->size) >= (size_t)((this->capacity)*CAPACITY_FACTOR)) {
        resize(this, 2*(this->capacity));
    }
    return NULL;
}

If we want to disassociate a key from the hash map altogether (assuming the hash map contains it), then we simply update the bucket containing the associated hash.

Yes, I know about Linus Torvalds's commentary about using a double pointer here, but I found it less clear after a second glance.

/* types.c */

void hashmap_remove(HashMap *this, Object *key) {
    if (NULL == this) return;
    hash_t h = hashCode(key);
    size_t index = indexFor(h, this->capacity);
    Entry *entry = this->table[index];
    Entry *prev = NULL;

    while (NULL != entry) {
        if ((entry->hash == h) && equals(entry->key, key)) {
            if (NULL == prev) {
                this->table[index] = entry->next;
            } else {
                prev->next = entry->next;
            }
            entry_free(&entry);
            this->size--;
            return;
        }
    }
}

The size of the hash map has been abstracted away to a helper function. It just accesses the size field. For *this null pointers, it defaults to zero.

/* types.c */

size_t hashmap_size(HashMap *this) {
    if (NULL == this) return 0;

    return this->size;
}

We can implement the hashcode computation as treating it as a list of key-value entries.

(N.B. Java computes the hash code of a HashMap by iterating over the entry set, and using their hash code computation for a generic list. See, e.g., AbstractMap::hashCode in JDK8).

/* types.c */

static hash_t entry_hashCode(Entry *entry) {
    if (NULL == entry) return 0;
    else return hashCode(entry->key) ^ hashCode(entry->value);
}

hash_t hashmap_hashCode(HashMap *this) {
    hash_t h = 0;
    for (size_t row = 0; row < (this->capacity); row++) {
        for (Entry *e = (this->table[row]); NULL != e; e = e->next) {
            h += entry_hashCode(e);
        }
    }
    return h;
}

This is trickier, but basically checks if every key in the lhs map appears in the rhs map, and if that key is associated to the same values. And if they have the same size, then the two hash maps are equal, and the method returns true. All other scenarios return false.

/* types.c */

bool hashmap_equals(HashMap *lhs, HashMap *rhs) {
    if (lhs == rhs) return true;
    if (NULL == lhs) return false;
    if (NULL == rhs) return false;
    if ((lhs->size) != (rhs->size)) return false;

    for (size_t row = 0; row < (lhs->capacity); row++) {
        for (Entry *e = (lhs->table[row]); NULL != e; e = e->next) {
            if (!equals(e->value, hashmap_get(rhs, e->key))) {
                return false;
            }
        }
    }
    return true;
}

• How does a HashMap work in JAVA
  • OpenJDK's implementation changed from a linked list (jdk8-b01) to use a binary tree for buckets with 8 or more elements (by jdk8-b120)
• Intel's concurrent_unordered_map
• Attractive Chaos's khash
  • Implementation Notes
  • Comparison of Hash Table Libraries
• An Analysis of Hash Map Implementations in Popular Languages
• Common Lisp implementations all seem to use chaining
  • SBCL
  • CCL
  • ABCL