Add MapBuilder

This commit provides a `MapBuilder` for efficiently combining multiple
`Map` mutations.

3 files changed, 448 insertions, 116 deletions

diff --git a/README.md b/README.md
index fe862c4..653b9bb 100644
--- a/README.md
+++ b/README.md
@@ -212,6 +212,27 @@ iterate in the same order. Ordering can be insertion order dependent when two
 keys generate the same hash.
 
 
+### Efficiently building maps
+
+If you are executing multiple mutations on a map, it can be much more efficient
+to use the `MapBuilder`. It uses nearly the same API as `Map` except that it 
+updates a map in-place until you are ready to use it. 
+
+```go
+b := immutable.NewMapBuilder(immutable.NewMap(nil))
+b.Set("foo", 100)
+b.Set("bar", 200)
+b.Set("foo", 300)
+
+m := b.Map()
+fmt.Println(m.Get("foo")) // "300"
+fmt.Println(m.Get("bar")) // "200"
+```
+
+Maps are safe to use even after you continue to use the builder. You can
+also build on top of existing maps too.
+
+
 ### Implementing a custom Hasher
 
 If you need to use a key type besides `int`, `string`, or `[]byte` then you'll
diff --git a/immutable.go b/immutable.go
index ac430ea..307b324 100644
--- a/immutable.go
+++ b/immutable.go
@@ -687,6 +687,12 @@ func (m *Map) Len() int {
 	return m.size
 }
 
+// clone returns a shallow copy of m.
+func (m *Map) clone() *Map {
+	other := *m
+	return &other
+}
+
 // Get returns the value for a given key and a flag indicating whether the
 // key exists. This flag distinguishes a nil value set on a key versus a
 // non-existent key in the map.
@@ -703,6 +709,10 @@ func (m *Map) Get(key interface{}) (value interface{}, ok bool) {
 // This function will return a new map even if the updated value is the same as
 // the existing value because Map does not track value equality.
 func (m *Map) Set(key, value interface{}) *Map {
+	return m.set(key, value, false)
+}
+
+func (m *Map) set(key, value interface{}, mutable bool) *Map {
 	// Set a hasher on the first value if one does not already exist.
 	hasher := m.hasher
 	if hasher == nil {
@@ -718,23 +728,24 @@ func (m *Map) Set(key, value interface{}) *Map {
 		}
 	}
 
+	// Generate copy if necessary.
+	other := m
+	if !mutable {
+		other = m.clone()
+	}
+	other.hasher = hasher
+
 	// If the map is empty, initialize with a simple array node.
 	if m.root == nil {
-		return &Map{
-			size:   1,
-			root:   &mapArrayNode{entries: []mapEntry{{key: key, value: value}}},
-			hasher: hasher,
-		}
+		other.size = 1
+		other.root = &mapArrayNode{entries: []mapEntry{{key: key, value: value}}}
+		return other
 	}
 
 	// Otherwise copy the map and delegate insertion to the root.
 	// Resized will return true if the key does not currently exist.
 	var resized bool
-	other := &Map{
-		size:   m.size,
-		root:   m.root.set(key, value, 0, hasher.Hash(key), hasher, &resized),
-		hasher: hasher,
-	}
+	other.root = m.root.set(key, value, 0, hasher.Hash(key), hasher, mutable, &resized)
 	if resized {
 		other.size++
 	}
@@ -744,23 +755,32 @@ func (m *Map) Set(key, value interface{}) *Map {
 // Delete returns a map with the given key removed.
 // Removing a non-existent key will cause this method to return the same map.
 func (m *Map) Delete(key interface{}) *Map {
+	return m.delete(key, false)
+}
+
+func (m *Map) delete(key interface{}, mutable bool) *Map {
 	// Return original map if no keys exist.
 	if m.root == nil {
 		return m
 	}
 
 	// If the delete did not change the node then return the original map.
-	newRoot := m.root.delete(key, 0, m.hasher.Hash(key), m.hasher)
-	if newRoot == m.root {
+	var resized bool
+	newRoot := m.root.delete(key, 0, m.hasher.Hash(key), m.hasher, mutable, &resized)
+	if !resized {
 		return m
 	}
 
-	// Return copy of map with new root and decreased size.
-	return &Map{
-		size:   m.size - 1,
-		root:   newRoot,
-		hasher: m.hasher,
+	// Generate copy if necessary.
+	other := m
+	if !mutable {
+		other = m.clone()
 	}
+
+	// Return copy of map with new root and decreased size.
+	other.size = m.size - 1
+	other.root = newRoot
+	return other
 }
 
 // Iterator returns a new iterator for the map.
@@ -770,11 +790,56 @@ func (m *Map) Iterator() *MapIterator {
 	return itr
 }
 
+// MapBuilder represents an efficient builder for creating Maps.
+//
+// Maps returned from the builder are safe to use even after you continue to
+// use the builder. However, for efficiency, you should only retrieve your map
+// after you have completed building it.
+type MapBuilder struct {
+	m       *Map // current state
+	mutable bool // if true, next mutation will operate in-place.
+}
+
+// NewMapBuilder returns a new instance of MapBuilder to build on a base map.
+func NewMapBuilder(m *Map) *MapBuilder {
+	return &MapBuilder{m: m}
+}
+
+// Map returns the current copy of the map.
+// The returned map is safe to use even if after the builder continues to be used.
+func (b *MapBuilder) Map() *Map {
+	m := b.m
+	b.mutable = false
+	return m
+}
+
+// Len returns the number of elements in the underlying map.
+func (b *MapBuilder) Len() int {
+	return b.m.Len()
+}
+
+// Get returns the value for the given key.
+func (b *MapBuilder) Get(key interface{}) (value interface{}, ok bool) {
+	return b.m.Get(key)
+}
+
+// Set sets the value of the given key. See Map.Set() for additional details.
+func (b *MapBuilder) Set(key, value interface{}) {
+	b.m = b.m.set(key, value, b.mutable)
+	b.mutable = true
+}
+
+// Delete removes the given key. See Map.Delete() for additional details.
+func (b *MapBuilder) Delete(key interface{}) {
+	b.m = b.m.delete(key, b.mutable)
+	b.mutable = true
+}
+
 // mapNode represents any node in the map tree.
 type mapNode interface {
 	get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool)
-	set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode
-	delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode
+	set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode
+	delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode
 }
 
 var _ mapNode = (*mapArrayNode)(nil)
@@ -820,7 +885,7 @@ func (n *mapArrayNode) get(key interface{}, shift uint, keyHash uint32, h Hasher
 
 // set inserts or updates the value for a given key. If the key is inserted and
 // the new size crosses the max size threshold, a bitmap indexed node is returned.
-func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode {
+func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	idx := n.indexOf(key, h)
 
 	// Mark as resized if the key doesn't exist.
@@ -833,11 +898,21 @@ func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h
 	if idx == -1 && len(n.entries) >= maxArrayMapSize {
 		var node mapNode = newMapValueNode(h.Hash(key), key, value)
 		for _, entry := range n.entries {
-			node = node.set(entry.key, entry.value, 0, h.Hash(entry.key), h, resized)
+			node = node.set(entry.key, entry.value, 0, h.Hash(entry.key), h, false, resized)
 		}
 		return node
 	}
 
+	// Update in-place if mutable.
+	if mutable {
+		if idx != -1 {
+			n.entries[idx] = mapEntry{key, value}
+		} else {
+			n.entries = append(n.entries, mapEntry{key, value})
+		}
+		return n
+	}
+
 	// Update existing entry if a match is found.
 	// Otherwise append to the end of the element list if it doesn't exist.
 	var other mapArrayNode
@@ -855,19 +930,28 @@ func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h
 
 // delete removes the given key from the node. Returns the same node if key does
 // not exist. Returns a nil node when removing the last entry.
-func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode {
+func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	idx := n.indexOf(key, h)
 
 	// Return original node if key does not exist.
 	if idx == -1 {
 		return n
 	}
+	*resized = true
 
 	// Return nil if this node will contain no nodes.
 	if len(n.entries) == 1 {
 		return nil
 	}
 
+	// Update in-place, if mutable.
+	if mutable {
+		copy(n.entries[idx:], n.entries[idx+1:])
+		n.entries[len(n.entries)-1] = mapEntry{}
+		n.entries = n.entries[:len(n.entries)-1]
+		return n
+	}
+
 	// Otherwise create a copy with the given entry removed.
 	other := &mapArrayNode{entries: make([]mapEntry, len(n.entries)-1)}
 	copy(other.entries[:idx], n.entries[:idx])
@@ -895,7 +979,7 @@ func (n *mapBitmapIndexedNode) get(key interface{}, shift uint, keyHash uint32,
 
 // set inserts or updates the value for the given key. If a new key is inserted
 // and the size crosses the max size threshold then a hash array node is returned.
-func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode {
+func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	// Extract the index for the bit segment of the key hash.
 	keyHashFrag := (keyHash >> shift) & mapNodeMask
 
@@ -915,7 +999,7 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u
 	// If the node doesn't exist then create a simple value leaf node.
 	var newNode mapNode
 	if exists {
-		newNode = n.nodes[idx].set(key, value, shift+mapNodeBits, keyHash, h, resized)
+		newNode = n.nodes[idx].set(key, value, shift+mapNodeBits, keyHash, h, mutable, resized)
 	} else {
 		newNode = newMapValueNode(keyHash, key, value)
 	}
@@ -935,6 +1019,19 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u
 		return &other
 	}
 
+	// Update in-place if mutable.
+	if mutable {
+		if exists {
+			n.nodes[idx] = newNode
+		} else {
+			n.bitmap |= bit
+			n.nodes = append(n.nodes, nil)
+			copy(n.nodes[idx+1:], n.nodes[idx:])
+			n.nodes[idx] = newNode
+		}
+		return n
+	}
+
 	// If node exists at given slot then overwrite it with new node.
 	// Otherwise expand the node list and insert new node into appropriate position.
 	other := &mapBitmapIndexedNode{bitmap: n.bitmap | bit}
@@ -954,7 +1051,7 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u
 // delete removes the key from the tree. If the key does not exist then the
 // original node is returned. If removing the last child node then a nil is
 // returned. Note that shrinking the node will not convert it to an array node.
-func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode {
+func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	bit := uint32(1) << ((keyHash >> shift) & mapNodeMask)
 
 	// Return original node if key does not exist.
@@ -967,10 +1064,10 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3
 
 	// Delegate delete to child node.
 	child := n.nodes[idx]
-	newChild := child.delete(key, shift+mapNodeBits, keyHash, h)
+	newChild := child.delete(key, shift+mapNodeBits, keyHash, h, mutable, resized)
 
 	// Return original node if key doesn't exist in child.
-	if newChild == child {
+	if !*resized {
 		return n
 	}
 
@@ -981,6 +1078,15 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3
 			return nil
 		}
 
+		// Update in-place if mutable.
+		if mutable {
+			n.bitmap ^= bit
+			copy(n.nodes[idx:], n.nodes[idx+1:])
+			n.nodes[len(n.nodes)-1] = nil
+			n.nodes = n.nodes[:len(n.nodes)-1]
+			return n
+		}
+
 		// Return copy with bit removed from bitmap and node removed from node list.
 		other := &mapBitmapIndexedNode{bitmap: n.bitmap ^ bit, nodes: make([]mapNode, len(n.nodes)-1)}
 		copy(other.nodes[:idx], n.nodes[:idx])
@@ -988,9 +1094,14 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3
 		return other
 	}
 
-	// Return copy with child updated.
-	other := &mapBitmapIndexedNode{bitmap: n.bitmap, nodes: make([]mapNode, len(n.nodes))}
-	copy(other.nodes, n.nodes)
+	// Generate copy, if necessary.
+	other := n
+	if !mutable {
+		other = &mapBitmapIndexedNode{bitmap: n.bitmap, nodes: make([]mapNode, len(n.nodes))}
+		copy(other.nodes, n.nodes)
+	}
+
+	// Update child.
 	other.nodes[idx] = newChild
 	return other
 }
@@ -1002,6 +1113,12 @@ type mapHashArrayNode struct {
 	nodes [mapNodeSize]mapNode // child node slots, may contain empties
 }
 
+// clone returns a shallow copy of n.
+func (n *mapHashArrayNode) clone() *mapHashArrayNode {
+	other := *n
+	return &other
+}
+
 // get returns the value for the given key.
 func (n *mapHashArrayNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) {
 	node := n.nodes[(keyHash>>shift)&mapNodeMask]
@@ -1012,7 +1129,7 @@ func (n *mapHashArrayNode) get(key interface{}, shift uint, keyHash uint32, h Ha
 }
 
 // set returns a node with the value set for the given key.
-func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode {
+func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	idx := (keyHash >> shift) & mapNodeMask
 	node := n.nodes[idx]
 
@@ -1023,22 +1140,27 @@ func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint3
 		*resized = true
 		newNode = newMapValueNode(keyHash, key, value)
 	} else {
-		newNode = node.set(key, value, shift+mapNodeBits, keyHash, h, resized)
+		newNode = node.set(key, value, shift+mapNodeBits, keyHash, h, mutable, resized)
 	}
 
-	// Return a copy of node with updated child node (and updated size, if new).
-	other := *n
+	// Generate copy, if necessary.
+	other := n
+	if !mutable {
+		other = n.clone()
+	}
+
+	// Update child node (and update size, if new).
 	if node == nil {
 		other.count++
 	}
 	other.nodes[idx] = newNode
-	return &other
+	return other
 }
 
 // delete returns a node with the given key removed. Returns the same node if
 // the key does not exist. If node shrinks to within bitmap-indexed size then
 // converts to a bitmap-indexed node.
-func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode {
+func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	idx := (keyHash >> shift) & mapNodeMask
 	node := n.nodes[idx]
 
@@ -1048,8 +1170,8 @@ func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h
 	}
 
 	// Return original node if child is unchanged.
-	newNode := node.delete(key, shift+mapNodeBits, keyHash, h)
-	if newNode == node {
+	newNode := node.delete(key, shift+mapNodeBits, keyHash, h, mutable, resized)
+	if !*resized {
 		return n
 	}
 
@@ -1065,13 +1187,18 @@ func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h
 		return other
 	}
 
+	// Generate copy, if necessary.
+	other := n
+	if !mutable {
+		other = n.clone()
+	}
+
 	// Return copy of node with child updated.
-	other := *n
 	other.nodes[idx] = newNode
 	if newNode == nil {
 		other.count--
 	}
-	return &other
+	return other
 }
 
 // mapValueNode represents a leaf node with a single key/value pair.
@@ -1109,9 +1236,15 @@ func (n *mapValueNode) get(key interface{}, shift uint, keyHash uint32, h Hasher
 // the node's key then a new value node is returned. If key is not equal to the
 // node's key but has the same hash then a hash collision node is returned.
 // Otherwise the nodes are merged into a branch node.
-func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode {
+func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	// If the keys match then return a new value node overwriting the value.
 	if h.Equal(n.key, key) {
+		// Update in-place if mutable.
+		if mutable {
+			n.value = value
+			return n
+		}
+		// Otherwise return a new copy.
 		return newMapValueNode(n.keyHash, key, value)
 	}
 
@@ -1130,13 +1263,14 @@ func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h
 }
 
 // delete returns nil if the key matches the node's key. Otherwise returns the original node.
-func (n *mapValueNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode {
+func (n *mapValueNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	// Return original node if the keys do not match.
 	if !h.Equal(n.key, key) {
 		return n
 	}
 
 	// Otherwise remove the node if keys do match.
+	*resized = true
 	return nil
 }
 
@@ -1174,13 +1308,24 @@ func (n *mapHashCollisionNode) get(key interface{}, shift uint, keyHash uint32,
 }
 
 // set returns a copy of the node with key set to the given value.
-func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode {
+func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	// Merge node with key/value pair if this is not a hash collision.
 	if n.keyHash != keyHash {
 		*resized = true
 		return mergeIntoNode(n, shift, keyHash, key, value)
 	}
 
+	// Update in-place if mutable.
+	if mutable {
+		if idx := n.indexOf(key, h); idx == -1 {
+			*resized = true
+			n.entries = append(n.entries, mapEntry{key, value})
+		} else {
+			n.entries[idx] = mapEntry{key, value}
+		}
+		return n
+	}
+
 	// Append to end of node if key doesn't exist & mark resized.
 	// Otherwise copy nodes and overwrite at matching key index.
 	other := &mapHashCollisionNode{keyHash: n.keyHash}
@@ -1200,7 +1345,7 @@ func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash u
 // delete returns a node with the given key deleted. Returns the same node if
 // the key does not exist. If removing the key would shrink the node to a single
 // entry then a value node is returned.
-func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode {
+func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode {
 	idx := n.indexOf(key, h)
 
 	// Return original node if key is not found.
@@ -1208,6 +1353,9 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3
 		return n
 	}
 
+	// Mark as resized if key exists.
+	*resized = true
+
 	// Convert to value node if we move to one entry.
 	if len(n.entries) == 2 {
 		return &mapValueNode{
@@ -1217,7 +1365,15 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3
 		}
 	}
 
-	// Otherwise return copy with entry removed.
+	// Remove entry in-place if mutable.
+	if mutable {
+		copy(n.entries[idx:], n.entries[idx+1:])
+		n.entries[len(n.entries)-1] = mapEntry{}
+		n.entries = n.entries[:len(n.entries)-1]
+		return n
+	}
+
+	// Return copy without entry if immutable.
 	other := &mapHashCollisionNode{keyHash: n.keyHash, entries: make([]mapEntry, len(n.entries)-1)}
 	copy(other.entries[:idx], n.entries[:idx])
 	copy(other.entries[idx:], n.entries[idx+1:])
diff --git a/immutable_test.go b/immutable_test.go
index c2c91d9..1512e93 100644
--- a/immutable_test.go
+++ b/immutable_test.go
@@ -611,7 +611,7 @@ func TestInternal_mapNode_Overwrite(t *testing.T) {
 	var node mapNode = &mapArrayNode{}
 	for i := 0; i < n; i++ {
 		var resized bool
-		node = node.set(i, i, 0, h.Hash(i), &h, &resized)
+		node = node.set(i, i, 0, h.Hash(i), &h, false, &resized)
 		if !resized {
 			t.Fatal("expected resize")
 		}
@@ -619,7 +619,7 @@ func TestInternal_mapNode_Overwrite(t *testing.T) {
 		// Overwrite every node.
 		for j := 0; j <= i; j++ {
 			var resized bool
-			node = node.set(j, i*j, 0, h.Hash(j), &h, &resized)
+			node = node.set(j, i*j, 0, h.Hash(j), &h, false, &resized)
 			if resized {
 				t.Fatalf("expected no resize: i=%d, j=%d", i, j)
 			}
@@ -646,7 +646,7 @@ func TestInternal_mapArrayNode(t *testing.T) {
 		n := &mapArrayNode{}
 		for i := 0; i < 8; i++ {
 			var resized bool
-			n = n.set(i*10, i, 0, h.Hash(i*10), &h, &resized).(*mapArrayNode)
+			n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode)
 			if !resized {
 				t.Fatal("expected resize")
 			}
@@ -665,7 +665,7 @@ func TestInternal_mapArrayNode(t *testing.T) {
 		n := &mapArrayNode{}
 		for i := 7; i >= 0; i-- {
 			var resized bool
-			n = n.set(i*10, i, 0, h.Hash(i*10), &h, &resized).(*mapArrayNode)
+			n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode)
 			if !resized {
 				t.Fatal("expected resize")
 			}
@@ -684,7 +684,7 @@ func TestInternal_mapArrayNode(t *testing.T) {
 		var n mapNode = &mapArrayNode{}
 		for i := 0; i < 100; i++ {
 			var resized bool
-			n = n.set(i, i, 0, h.Hash(i), &h, &resized)
+			n = n.set(i, i, 0, h.Hash(i), &h, false, &resized)
 			if !resized {
 				t.Fatal("expected resize")
 			}
@@ -703,11 +703,12 @@ func TestInternal_mapArrayNode(t *testing.T) {
 		var n mapNode = &mapArrayNode{}
 		for i := 0; i < 8; i++ {
 			var resized bool
-			n = n.set(i*10, i, 0, h.Hash(i*10), &h, &resized)
+			n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized)
 		}
 
 		for _, i := range rand.Perm(8) {
-			n = n.delete(i*10, 0, h.Hash(i*10), &h)
+			var resized bool
+			n = n.delete(i*10, 0, h.Hash(i*10), &h, false, &resized)
 		}
 		if n != nil {
 			t.Fatal("expected nil rand")
@@ -730,7 +731,7 @@ func TestInternal_mapValueNode(t *testing.T) {
 		var h intHasher
 		var resized bool
 		n := newMapValueNode(h.Hash(2), 2, 3)
-		other := n.set(2, 4, 0, h.Hash(2), &h, &resized).(*mapValueNode)
+		other := n.set(2, 4, 0, h.Hash(2), &h, false, &resized).(*mapValueNode)
 		if other == n {
 			t.Fatal("expected new node")
 		} else if got, exp := other.keyHash, h.Hash(2); got != exp {
@@ -751,7 +752,7 @@ func TestInternal_mapValueNode(t *testing.T) {
 		}
 		var resized bool
 		n := newMapValueNode(h.Hash(2), 2, 3)
-		other := n.set(4, 5, 0, h.Hash(4), h, &resized).(*mapHashCollisionNode)
+		other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapHashCollisionNode)
 		if got, exp := other.keyHash, h.Hash(2); got != exp {
 			t.Fatalf("keyHash=%v, expected %v", got, exp)
 		} else if got, exp := len(other.entries), 2; got != exp {
@@ -777,7 +778,7 @@ func TestInternal_mapValueNode(t *testing.T) {
 			var h intHasher
 			var resized bool
 			n := newMapValueNode(h.Hash(2), 2, 3)
-			other := n.set(4, 5, 0, h.Hash(4), &h, &resized).(*mapBitmapIndexedNode)
+			other := n.set(4, 5, 0, h.Hash(4), &h, false, &resized).(*mapBitmapIndexedNode)
 			if got, exp := other.bitmap, uint32(0x14); got != exp {
 				t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
 			} else if got, exp := len(other.nodes), 2; got != exp {
@@ -813,7 +814,7 @@ func TestInternal_mapValueNode(t *testing.T) {
 			var h intHasher
 			var resized bool
 			n := newMapValueNode(h.Hash(4), 4, 5)
-			other := n.set(2, 3, 0, h.Hash(2), &h, &resized).(*mapBitmapIndexedNode)
+			other := n.set(2, 3, 0, h.Hash(2), &h, false, &resized).(*mapBitmapIndexedNode)
 			if got, exp := other.bitmap, uint32(0x14); got != exp {
 				t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
 			} else if got, exp := len(other.nodes), 2; got != exp {
@@ -852,7 +853,7 @@ func TestInternal_mapValueNode(t *testing.T) {
 			}
 			var resized bool
 			n := newMapValueNode(h.Hash(2), 2, 3)
-			other := n.set(4, 5, 0, h.Hash(4), h, &resized).(*mapBitmapIndexedNode)
+			other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapBitmapIndexedNode)
 			if got, exp := other.bitmap, uint32(0x01); got != exp { // mask is zero, expect first slot.
 				t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp)
 			} else if got, exp := len(other.nodes), 1; got != exp {
@@ -1139,73 +1140,131 @@ func TestMap_Delete(t *testing.T) {
 
 // Ensure map works even with hash conflicts.
 func TestMap_LimitedHash(t *testing.T) {
-	h := mockHasher{
-		hash:  func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF },
-		equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
-	}
-	m := NewMap(&h)
+	t.Run("Immutable", func(t *testing.T) {
+		h := mockHasher{
+			hash:  func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF },
+			equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
+		}
+		m := NewMap(&h)
 
-	rand := rand.New(rand.NewSource(0))
-	keys := rand.Perm(100000)
-	for _, i := range keys {
-		m = m.Set(i, i) // initial set
-	}
-	for i := range keys {
-		m = m.Set(i, i*2) // overwrite
-	}
-	if m.Len() != len(keys) {
-		t.Fatalf("unexpected len: %d", m.Len())
-	}
+		rand := rand.New(rand.NewSource(0))
+		keys := rand.Perm(100000)
+		for _, i := range keys {
+			m = m.Set(i, i) // initial set
+		}
+		for i := range keys {
+			m = m.Set(i, i*2) // overwrite
+		}
+		if m.Len() != len(keys) {
+			t.Fatalf("unexpected len: %d", m.Len())
+		}
 
-	// Verify all key/value pairs in map.
-	for i := 0; i < m.Len(); i++ {
-		if v, ok := m.Get(i); !ok || v != i*2 {
-			t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
+		// Verify all key/value pairs in map.
+		for i := 0; i < m.Len(); i++ {
+			if v, ok := m.Get(i); !ok || v != i*2 {
+				t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
+			}
 		}
-	}
 
-	// Verify iteration.
-	itr := m.Iterator()
-	for !itr.Done() {
-		if k, v := itr.Next(); v != k.(int)*2 {
-			t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2)
+		// Verify iteration.
+		itr := m.Iterator()
+		for !itr.Done() {
+			if k, v := itr.Next(); v != k.(int)*2 {
+				t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2)
+			}
 		}
-	}
 
-	// Verify not found works.
-	if _, ok := m.Get(10000000); ok {
-		t.Fatal("expected no value")
-	}
+		// Verify not found works.
+		if _, ok := m.Get(10000000); ok {
+			t.Fatal("expected no value")
+		}
 
-	// Verify delete non-existent key works.
-	if other := m.Delete(10000000 + 1); m != other {
-		t.Fatal("expected no change")
-	}
+		// Verify delete non-existent key works.
+		if other := m.Delete(10000000 + 1); m != other {
+			t.Fatal("expected no change")
+		}
 
-	// Remove all keys.
-	for _, key := range keys {
-		m = m.Delete(key)
-	}
-	if m.Len() != 0 {
-		t.Fatalf("unexpected size: %d", m.Len())
-	}
+		// Remove all keys.
+		for _, key := range keys {
+			m = m.Delete(key)
+		}
+		if m.Len() != 0 {
+			t.Fatalf("unexpected size: %d", m.Len())
+		}
+	})
+
+	t.Run("Builder", func(t *testing.T) {
+		h := mockHasher{
+			hash:  func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF },
+			equal: func(a, b interface{}) bool { return a.(int) == b.(int) },
+		}
+		b := NewMapBuilder(NewMap(&h))
+
+		rand := rand.New(rand.NewSource(0))
+		keys := rand.Perm(100000)
+		for _, i := range keys {
+			b.Set(i, i) // initial set
+		}
+		for i := range keys {
+			b.Set(i, i*2) // overwrite
+		}
+		if b.Len() != len(keys) {
+			t.Fatalf("unexpected len: %d", b.Len())
+		}
+
+		// Verify all key/value pairs in map.
+		for i := 0; i < b.Len(); i++ {
+			if v, ok := b.Get(i); !ok || v != i*2 {
+				t.Fatalf("Get(%d)=<%v,%v>", i, v, ok)
+			}
+		}
+
+		// Verify iteration.
+		itr := b.Map().Iterator()
+		for !itr.Done() {
+			if k, v := itr.Next(); v != k.(int)*2 {
+				t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2)
+			}
+		}
+
+		// Verify not found works.
+		if _, ok := b.Get(10000000); ok {
+			t.Fatal("expected no value")
+		}
+
+		// Verify delete non-existent key works.
+		m := b.Map()
+		if b.Delete(10000000 + 1); m != b.Map() {
+			t.Fatal("expected no change")
+		}
+
+		// Remove all keys.
+		for _, key := range keys {
+			b.Delete(key)
+		}
+		if b.Len() != 0 {
+			t.Fatalf("unexpected size: %d", b.Len())
+		}
+	})
 }
 
-// TestMap represents a combined immutable and stdlib map.
-type TestMap struct {
+// TMap represents a combined immutable and stdlib map.
+type TMap struct {
 	im, prev *Map
+	builder  *MapBuilder
 	std      map[int]int
 	keys     []int
 }
 
-func NewTestMap() *TestMap {
-	return &TestMap{
-		im:  NewMap(nil),
-		std: make(map[int]int),
+func NewTestMap() *TMap {
+	return &TMap{
+		im:      NewMap(nil),
+		builder: NewMapBuilder(NewMap(nil)),
+		std:     make(map[int]int),
 	}
 }
 
-func (m *TestMap) NewKey(rand *rand.Rand) int {
+func (m *TMap) NewKey(rand *rand.Rand) int {
 	for {
 		k := rand.Int()
 		if _, ok := m.std[k]; !ok {
@@ -1214,16 +1273,17 @@ func (m *TestMap) NewKey(rand *rand.Rand) int {
 	}
 }
 
-func (m *TestMap) ExistingKey(rand *rand.Rand) int {
+func (m *TMap) ExistingKey(rand *rand.Rand) int {
 	if len(m.keys) == 0 {
 		return 0
 	}
 	return m.keys[rand.Intn(len(m.keys))]
 }
 
-func (m *TestMap) Set(k, v int) {
+func (m *TMap) Set(k, v int) {
 	m.prev = m.im
 	m.im = m.im.Set(k, v)
+	m.builder.Set(k, v)
 
 	_, exists := m.std[k]
 	if !exists {
@@ -1232,9 +1292,10 @@ func (m *TestMap) Set(k, v int) {
 	m.std[k] = v
 }
 
-func (m *TestMap) Delete(k int) {
+func (m *TMap) Delete(k int) {
 	m.prev = m.im
 	m.im = m.im.Delete(k)
+	m.builder.Delete(k)
 	delete(m.std, k)
 
 	for i := range m.keys {
@@ -1245,20 +1306,30 @@ func (m *TestMap) Delete(k int) {
 	}
 }
 
-func (m *TestMap) Validate() error {
+func (m *TMap) Validate() error {
 	for _, k := range m.keys {
 		if v, ok := m.im.Get(k); !ok {
 			return fmt.Errorf("key not found: %d", k)
 		} else if v != m.std[k] {
 			return fmt.Errorf("key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
 		}
+		if v, ok := m.builder.Get(k); !ok {
+			return fmt.Errorf("builder key not found: %d", k)
+		} else if v != m.std[k] {
+			return fmt.Errorf("builder key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
+		}
+	}
+	if err := m.validateIterator(m.im); err != nil {
+		return fmt.Errorf("basic: %s", err)
+	} else if err := m.validateIterator(m.builder.Map()); err != nil {
+		return fmt.Errorf("builder: %s", err)
 	}
-	return m.validateIterator()
+	return nil
 }
 
-func (m *TestMap) validateIterator() error {
+func (m *TMap) validateIterator(mm *Map) error {
 	other := make(map[int]int)
-	itr := m.im.Iterator()
+	itr := mm.Iterator()
 	for !itr.Done() {
 		k, v := itr.Next()
 		other[k.(int)] = v.(int)
@@ -1272,6 +1343,29 @@ func (m *TestMap) validateIterator() error {
 	return nil
 }
 
+func BenchmarkBuiltinMap_Set(b *testing.B) {
+	b.ReportAllocs()
+	m := make(map[int]int)
+	for i := 0; i < b.N; i++ {
+		m[i] = i
+	}
+}
+
+func BenchmarkBuiltinMap_Delete(b *testing.B) {
+	const n = 10000000
+
+	m := make(map[int]int)
+	for i := 0; i < n; i++ {
+		m[i] = i
+	}
+	b.ReportAllocs()
+	b.ResetTimer()
+
+	for i := 0; i < b.N; i++ {
+		delete(m, i%n)
+	}
+}
+
 func BenchmarkMap_Set(b *testing.B) {
 	b.ReportAllocs()
 	m := NewMap(nil)
@@ -1281,15 +1375,16 @@ func BenchmarkMap_Set(b *testing.B) {
 }
 
 func BenchmarkMap_Delete(b *testing.B) {
-	const n = 10000
+	const n = 10000000
 
-	m := NewMap(nil)
+	builder := NewMapBuilder(NewMap(nil))
 	for i := 0; i < n; i++ {
-		m = m.Set(i, i)
+		builder.Set(i, i)
 	}
 	b.ReportAllocs()
 	b.ResetTimer()
 
+	m := builder.Map()
 	for i := 0; i < b.N; i++ {
 		m.Delete(i % n) // Do not update map, always operate on original
 	}
@@ -1315,6 +1410,29 @@ func BenchmarkMap_Iterator(b *testing.B) {
 	})
 }
 
+func BenchmarkMapBuilder_Set(b *testing.B) {
+	b.ReportAllocs()
+	builder := NewMapBuilder(NewMap(nil))
+	for i := 0; i < b.N; i++ {
+		builder.Set(i, i)
+	}
+}
+
+func BenchmarkMapBuilder_Delete(b *testing.B) {
+	const n = 10000000
+
+	builder := NewMapBuilder(NewMap(nil))
+	for i := 0; i < n; i++ {
+		builder.Set(i, i)
+	}
+	b.ReportAllocs()
+	b.ResetTimer()
+
+	for i := 0; i < b.N; i++ {
+		builder.Delete(i % n)
+	}
+}
+
 func ExampleMap_Set() {
 	m := NewMap(nil)
 	m = m.Set("foo", "bar")
@@ -1379,6 +1497,43 @@ func ExampleMap_Iterator() {
 	// apple 100
 }
 
+func ExampleMapBuilder_Set() {
+	b := NewMapBuilder(NewMap(nil))
+	b.Set("foo", "bar")
+	b.Set("baz", 100)
+
+	m := b.Map()
+	v, ok := m.Get("foo")
+	fmt.Println("foo", v, ok)
+
+	v, ok = m.Get("baz")
+	fmt.Println("baz", v, ok)
+
+	v, ok = m.Get("bat") // does not exist
+	fmt.Println("bat", v, ok)
+	// Output:
+	// foo bar true
+	// baz 100 true
+	// bat <nil> false
+}
+
+func ExampleMapBuilder_Delete() {
+	b := NewMapBuilder(NewMap(nil))
+	b.Set("foo", "bar")
+	b.Set("baz", 100)
+	b.Delete("baz")
+
+	m := b.Map()
+	v, ok := m.Get("foo")
+	fmt.Println("foo", v, ok)
+
+	v, ok = m.Get("baz")
+	fmt.Println("baz", v, ok)
+	// Output:
+	// foo bar true
+	// baz <nil> false
+}
+
 func TestInternalSortedMapLeafNode(t *testing.T) {
 	RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) {
 		var cmpr intComparer