Skip to content

Latest commit

 

History

History
61 lines (42 loc) · 2.21 KB

README.md

File metadata and controls

61 lines (42 loc) · 2.21 KB
Raw

gomap

Go Reference Test workflow

This package reimplements Go's built-in map as a library using generics. The major difference between gomap.Map and map is that users of gomap.Map must provide their own equal and hash functions.

The use case for gomap.Map is when you want to use map, but can't because your key type is not comparable.

gomap.Map has similar performance and most of the features of the built-in map including:

  • iteration that is not invalidated by modifications to the map

  • randomized hash seeds and randomized iteration order

  • incremental rehash

  • cheap best effort detection of unsafe concurrent accesses

Requirements

There is a reason that Go's built-in map uses compiler generated equal and hash functions that users don't have control over: there are subtle requirements of a hash table that when invalidated cause hard to diagnose bugs.

The following requirements are the user's responsibility to follow:

  1. equal(a, b) => hash(a) == hash(b)

  2. equal(a, a) must be true for all values of a. Be careful around NaN float values. Go's built-in map has special cases for handling this, but Map does not.

  3. If a key in a Map contains references -- such as pointers, maps, or slices -- modifying the referenced data in a way that effects the result of the equal or hash functions will result in undefined behavior.

  4. For good performance hash functions should return uniformly distributed data across the entire 64-bits of the value.

Stability

The APIs of Map are subject to change at this early stage. In particular, Iter is likely to change depending on the outcome of this discussion for a standard iterator interface.

Implementation

The implementation of Map is largely copy-pasted from Go's map implementation. It implements a chaining hash table with buckets that contain 8 entries.