Repository: puzpuzpuz/xsync
Pull request #48 (2022-10-15 14:36:31)

Combine top hash caching with bucket chaining
Reintroduces bucket chaining, so that the map can cope with poor quality hash functions. This is a required preliminary step for #46.

codecov-commenter: # [Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/48?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) Report
Base: **93.10**% // Head: **94.69**% // Increases project coverage by **`+1.59%`** :tada:
> Coverage data is based on head [(`64f7b60`)](https://codecov.io/gh/puzpuzpuz/xsync/pull/48?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) compared to base [(`c340e98`)](https://codecov.io/gh/puzpuzpuz/xsync/commit/c340e98bdc0d1b5b034f90ee86137286ecabe793?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov).
> Patch coverage: 97.01% of modified lines in pull request are covered.

<details><summary>Additional details and impacted files</summary>


```diff
@@            Coverage Diff             @@
##             main      #48      +/-   ##
==========================================
+ Coverage   93.10%   94.69%   +1.59%     
==========================================
  Files           6        6              
  Lines         725      830     +105     
==========================================
+ Hits          675      786     +111     
+ Misses         40       35       -5     
+ Partials       10        9       -1     
```


| [Impacted Files](https://codecov.io/gh/puzpuzpuz/xsync/pull/48?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov) | Coverage Δ | |
|---|---|---|
| [map.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/48/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-bWFwLmdv) | `93.65% <96.75%> (+1.55%)` | :arrow_up: |
| [mapof.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/48/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-bWFwb2YuZ28=) | `94.16% <97.35%> (+3.02%)` | :arrow_up: |
| [mpmcqueue.go](https://codecov.io/gh/puzpuzpuz/xsync/pull/48/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov#diff-bXBtY3F1ZXVlLmdv) | `100.00% <100.00%> (ø)` | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/puzpuzpuz/xsync/pull/48?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Andrey+Pechkurov).


Patch:
diff --git a/map.go b/map.go
index f75fea4..7ef9993 100644
--- a/map.go
+++ b/map.go
@@ -3,6 +3,7 @@ package xsync
 import (
 	"fmt"
 	"math"
+	"runtime"
 	"sync"
 	"sync/atomic"
 	"unsafe"
@@ -22,11 +23,15 @@ const (
 	// threshold fraction of table occupation to start a table shrinking
 	// when deleting the last entry in a bucket chain
 	mapShrinkFraction = 128
+	// map load factor to trigger a table resize during insertion;
+	// a map holds up to mapLoadFactor*entriesPerMapBucket*mapTableLen
+	// key-value pairs
+	mapLoadFactor = 1.0
 	// minimal table size, i.e. number of buckets; thus, minimal map
 	// capacity can be calculated as entriesPerMapBucket*minMapTableLen
-	minMapTableLen = 32
+	minMapTableLen = 16
 	// maximum counter stripes to use; stands for around 8KB of memory
-	maxMapCounterLen = 128
+	maxMapCounterLen = 64
 )
 
 // Map is like a Go map[string]interface{} but is safe for concurrent
@@ -58,7 +63,7 @@ type Map struct {
 }
 
 type mapTable struct {
-	buckets []bucket
+	buckets []bucketPadded
 	// striped counter for number of table entries;
 	// used to determine if a table shrinking is needed
 	// occupies min(buckets_memory/1024, 64KB) of memory
@@ -71,15 +76,26 @@ type counterStripe struct {
 	pad [cacheLineSize - 8]byte
 }
 
+type bucketPadded struct {
+	//lint:ignore U1000 ensure each bucket takes two cache lines on both 32 and 64-bit archs
+	pad [2*cacheLineSize - unsafe.Sizeof(bucket{})]byte
+	bucket
+}
+
 type bucket struct {
-	mu     sync.Mutex
+	next   unsafe.Pointer // *bucketPadded
 	keys   [entriesPerMapBucket]unsafe.Pointer
 	values [entriesPerMapBucket]unsafe.Pointer
-	// contains packed top bytes (8 MSBs) of hash codes for keys
-	// stored in the bucket:
+	// topHashMutex is a 2-in-1 value.
+	//
+	// First, it contains packed top bytes (8 MSBs) of hash codes for
+	// keys stored in the bucket:
 	// | key 0's top hash | ... | key 7's top hash | bitmap for keys |
 	// |      1 byte      | ... |      1 byte      |     1 byte      |
-	topHashes uint64
+	//
+	// Second, the least significant bit in the bitmap for keys byte
+	// is used for the mutex (TTAS spinlock).
+	topHashMutex uint64
 }
 
 type rangeEntry struct {
@@ -97,7 +113,7 @@ func NewMap() *Map {
 }
 
 func newMapTable(size int) *mapTable {
-	buckets := make([]bucket, size)
+	buckets := make([]bucketPadded, size)
 	counterLen := size >> 10
 	if counterLen < minMapTableLen {
 		counterLen = minMapTableLen
@@ -120,27 +136,33 @@ func (m *Map) Load(key string) (value interface{}, ok bool) {
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
 	bidx := bucketIdx(table, hash)
 	b := &table.buckets[bidx]
-	topHashes := atomic.LoadUint64(&b.topHashes)
-	for i := 0; i < entriesPerMapBucket; i++ {
-		if !topHashMatch(hash, topHashes, i) {
-			continue
-		}
-	atomic_snapshot:
-		// Start atomic snapshot.
-		vp := atomic.LoadPointer(&b.values[i])
-		kp := atomic.LoadPointer(&b.keys[i])
-		if kp != nil && vp != nil {
-			if key == derefKey(kp) {
-				if uintptr(vp) == uintptr(atomic.LoadPointer(&b.values[i])) {
-					// Atomic snapshot succeeded.
-					return derefValue(vp), true
+	for {
+		topHashes := atomic.LoadUint64(&b.topHashMutex)
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if !topHashMatch(hash, topHashes, i) {
+				continue
+			}
+		atomic_snapshot:
+			// Start atomic snapshot.
+			vp := atomic.LoadPointer(&b.values[i])
+			kp := atomic.LoadPointer(&b.keys[i])
+			if kp != nil && vp != nil {
+				if key == derefKey(kp) {
+					if uintptr(vp) == uintptr(atomic.LoadPointer(&b.values[i])) {
+						// Atomic snapshot succeeded.
+						return derefValue(vp), true
+					}
+					// Concurrent update/remove. Go for another spin.
+					goto atomic_snapshot
 				}
-				// Concurrent update/remove. Go for another spin.
-				goto atomic_snapshot
 			}
 		}
+		bucketPtr := atomic.LoadPointer(&b.next)
+		if bucketPtr == nil {
+			return
+		}
+		b = (*bucketPadded)(bucketPtr)
 	}
-	return nil, false
 }
 
 // Store sets the value for a key.
@@ -173,69 +195,91 @@ func (m *Map) doStore(key string, value interface{}, loadIfExists bool) (interfa
 	// Write path.
 	hash := maphash64(key)
 	for {
+	store_attempt:
 		var (
 			emptykp, emptyvp *unsafe.Pointer
 			emptyidx         int
 		)
 		table := (*mapTable)(atomic.LoadPointer(&m.table))
+		tableLen := len(table.buckets)
 		bidx := bucketIdx(table, hash)
-		b := &table.buckets[bidx]
-		b.mu.Lock()
+		rootb := &table.buckets[bidx]
+		b := rootb
+		lockBucket(&rootb.topHashMutex)
 		if m.newerTableExists(table) {
 			// Someone resized the table. Go for another attempt.
-			b.mu.Unlock()
-			continue
+			unlockBucket(&rootb.topHashMutex)
+			goto store_attempt
 		}
 		if m.resizeInProgress() {
 			// Resize is in progress. Wait, then go for another attempt.
-			b.mu.Unlock()
+			unlockBucket(&rootb.topHashMutex)
 			m.waitForResize()
-			continue
+			goto store_attempt
 		}
-		for i := 0; i < entriesPerMapBucket; i++ {
-			if b.keys[i] == nil {
-				if emptykp == nil {
-					emptykp = &b.keys[i]
-					emptyvp = &b.values[i]
-					emptyidx = i
+		for {
+			topHashes := atomic.LoadUint64(&b.topHashMutex)
+			for i := 0; i < entriesPerMapBucket; i++ {
+				if b.keys[i] == nil {
+					if emptykp == nil {
+						emptykp = &b.keys[i]
+						emptyvp = &b.values[i]
+						emptyidx = i
+					}
+					continue
 				}
-				continue
-			}
-			if !topHashMatch(hash, b.topHashes, i) {
-				continue
-			}
-			if key == derefKey(b.keys[i]) {
-				vp := b.values[i]
-				if loadIfExists {
-					b.mu.Unlock()
+				if !topHashMatch(hash, topHashes, i) {
+					continue
+				}
+				if key == derefKey(b.keys[i]) {
+					vp := b.values[i]
+					if loadIfExists {
+						unlockBucket(&rootb.topHashMutex)
+						return derefValue(vp), true
+					}
+					// In-place update case. Luckily we get a copy of the value
+					// interface{} on each call, thus the live value pointers are
+					// unique. Otherwise atomic snapshot won't be correct in case
+					// of multiple Store calls using the same value.
+					nvp := unsafe.Pointer(&value)
+					if assertionsEnabled && vp == nvp {
+						panic("non-unique value pointer")
+					}
+					atomic.StorePointer(&b.values[i], nvp)
+					unlockBucket(&rootb.topHashMutex)
 					return derefValue(vp), true
 				}
-				// In-place update case. Luckily we get a copy of the value
-				// interface{} on each call, thus the live value pointers are
-				// unique. Otherwise atomic snapshot won't be correct in case
-				// of multiple Store calls using the same value.
-				nvp := unsafe.Pointer(&value)
-				if assertionsEnabled && vp == nvp {
-					panic("non-unique value pointer")
+			}
+			if b.next == nil {
+				if emptykp != nil {
+					// Insertion case. First we update the value, then the key.
+					// This is important for atomic snapshot states.
+					atomic.StoreUint64(&b.topHashMutex, storeTopHash(hash, topHashes, emptyidx))
+					atomic.StorePointer(emptyvp, unsafe.Pointer(&value))
+					atomic.StorePointer(emptykp, unsafe.Pointer(&key))
+					unlockBucket(&rootb.topHashMutex)
+					table.addSize(bidx, 1)
+					return value, false
+				}
+				growThreshold := float64(tableLen) * entriesPerMapBucket * mapLoadFactor
+				if table.sumSize() > int64(growThreshold) {
+					// Need to grow the table. Then go for another attempt.
+					unlockBucket(&rootb.topHashMutex)
+					m.resize(table, mapGrowHint)
+					goto store_attempt
 				}
-				atomic.StorePointer(&b.values[i], nvp)
-				b.mu.Unlock()
-				return derefValue(vp), true
+				// Create and append a new bucket.
+				newb := new(bucketPadded)
+				newb.keys[0] = unsafe.Pointer(&key)
+				newb.values[0] = unsafe.Pointer(&value)
+				newb.topHashMutex = storeTopHash(hash, topHashes, emptyidx)
+				atomic.StorePointer(&b.next, unsafe.Pointer(newb))
+				unlockBucket(&rootb.topHashMutex)
+				table.addSize(bidx, 1)
+				return value, false
 			}
+			b = (*bucketPadded)(b.next)
 		}
-		if emptykp != nil {
-			// Insertion case. First we update the value, then the key.
-			// This is important for atomic snapshot states.
-			atomic.StoreUint64(&b.topHashes, storeTopHash(hash, b.topHashes, emptyidx))
-			atomic.StorePointer(emptyvp, unsafe.Pointer(&value))
-			atomic.StorePointer(emptykp, unsafe.Pointer(&key))
-			b.mu.Unlock()
-			addSize(table, bidx, 1)
-			return value, false
-		}
-		// Need to grow the table. Then go for another attempt.
-		b.mu.Unlock()
-		m.resize(table, mapGrowHint)
 	}
 }
 
@@ -262,7 +306,7 @@ func (m *Map) resize(table *mapTable, hint mapResizeHint) {
 	// Fast path for shrink attempts.
 	if hint == mapShrinkHint {
 		shrinkThreshold = int64((tableLen * entriesPerMapBucket) / mapShrinkFraction)
-		if tableLen == minMapTableLen || sumSize(table) > shrinkThreshold {
+		if tableLen == minMapTableLen || table.sumSize() > shrinkThreshold {
 			return
 		}
 	}
@@ -279,7 +323,7 @@ func (m *Map) resize(table *mapTable, hint mapResizeHint) {
 		atomic.AddInt64(&m.totalGrowths, 1)
 		newTable = newMapTable(tableLen << 1)
 	case mapShrinkHint:
-		if sumSize(table) <= shrinkThreshold {
+		if table.sumSize() <= shrinkThreshold {
 			// Shrink the table with factor of 2.
 			atomic.AddInt64(&m.totalShrinks, 1)
 			newTable = newMapTable(tableLen >> 1)
@@ -294,15 +338,9 @@ func (m *Map) resize(table *mapTable, hint mapResizeHint) {
 	default:
 		panic(fmt.Sprintf("unexpected resize hint: %d", hint))
 	}
-copy:
 	for i := 0; i < tableLen; i++ {
-		copied, ok := copyBucket(&table.buckets[i], newTable)
-		if !ok {
-			// Table size is insufficient, need to grow it.
-			newTable = newMapTable(len(newTable.buckets) << 1)
-			goto copy
-		}
-		addSizeNonAtomic(newTable, uint64(i), copied)
+		copied := copyBucket(&table.buckets[i], newTable)
+		newTable.addSizePlain(uint64(i), copied)
 	}
 	// Publish the new table and wake up all waiters.
 	atomic.StorePointer(&m.table, unsafe.Pointer(newTable))
@@ -312,36 +350,48 @@ copy:
 	m.resizeMu.Unlock()
 }
 
-func copyBucket(b *bucket, destTable *mapTable) (copied int, ok bool) {
-	b.mu.Lock()
-	for i := 0; i < entriesPerMapBucket; i++ {
-		if b.keys[i] != nil {
-			k := derefKey(b.keys[i])
-			hash := maphash64(k)
-			bidx := bucketIdx(destTable, hash)
-			destb := &destTable.buckets[bidx]
-			appended := appendToBucket(hash, b.keys[i], b.values[i], destb)
-			if !appended {
-				b.mu.Unlock()
-				return 0, false
+func copyBucket(b *bucketPadded, destTable *mapTable) (copied int) {
+	rootb := b
+	lockBucket(&rootb.topHashMutex)
+	for {
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if b.keys[i] != nil {
+				k := derefKey(b.keys[i])
+				hash := maphash64(k)
+				bidx := bucketIdx(destTable, hash)
+				destb := &destTable.buckets[bidx]
+				appendToBucket(hash, b.keys[i], b.values[i], destb)
+				copied++
 			}
-			copied++
 		}
+		if b.next == nil {
+			unlockBucket(&rootb.topHashMutex)
+			return
+		}
+		b = (*bucketPadded)(b.next)
 	}
-	b.mu.Unlock()
-	return copied, true
 }
 
-func appendToBucket(hash uint64, keyPtr, valPtr unsafe.Pointer, b *bucket) (appended bool) {
-	for i := 0; i < entriesPerMapBucket; i++ {
-		if b.keys[i] == nil {
-			b.keys[i] = keyPtr
-			b.values[i] = valPtr
-			b.topHashes = storeTopHash(hash, b.topHashes, i)
-			return true
+func appendToBucket(hash uint64, keyPtr, valPtr unsafe.Pointer, b *bucketPadded) {
+	for {
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if b.keys[i] == nil {
+				b.keys[i] = keyPtr
+				b.values[i] = valPtr
+				b.topHashMutex = storeTopHash(hash, b.topHashMutex, i)
+				return
+			}
+		}
+		if b.next == nil {
+			newb := new(bucketPadded)
+			newb.keys[0] = keyPtr
+			newb.values[0] = valPtr
+			newb.topHashMutex = storeTopHash(hash, b.topHashMutex, 0)
+			b.next = unsafe.Pointer(newb)
+			return
 		}
+		b = (*bucketPadded)(b.next)
 	}
-	return false
 }
 
 // LoadAndDelete deletes the value for a key, returning the previous
@@ -349,51 +399,59 @@ func appendToBucket(hash uint64, keyPtr, valPtr unsafe.Pointer, b *bucket) (appe
 // present.
 func (m *Map) LoadAndDelete(key string) (value interface{}, loaded bool) {
 	hash := maphash64(key)
-delete_attempt:
-	hintNonEmpty := 0
-	table := (*mapTable)(atomic.LoadPointer(&m.table))
-	bidx := bucketIdx(table, hash)
-	b := &table.buckets[bidx]
-	b.mu.Lock()
-	if m.newerTableExists(table) {
-		// Someone resized the table. Go for another attempt.
-		b.mu.Unlock()
-		goto delete_attempt
-	}
-	if m.resizeInProgress() {
-		// Resize is in progress. Wait, then go for another attempt.
-		b.mu.Unlock()
-		m.waitForResize()
-		goto delete_attempt
-	}
-	for i := 0; i < entriesPerMapBucket; i++ {
-		kp := b.keys[i]
-		if kp == nil || !topHashMatch(hash, b.topHashes, i) {
+	for {
+		hintNonEmpty := 0
+		table := (*mapTable)(atomic.LoadPointer(&m.table))
+		bidx := bucketIdx(table, hash)
+		rootb := &table.buckets[bidx]
+		b := rootb
+		lockBucket(&rootb.topHashMutex)
+		if m.newerTableExists(table) {
+			// Someone resized the table. Go for another attempt.
+			unlockBucket(&rootb.topHashMutex)
+			continue
+		}
+		if m.resizeInProgress() {
+			// Resize is in progress. Wait, then go for another attempt.
+			unlockBucket(&rootb.topHashMutex)
+			m.waitForResize()
 			continue
 		}
-		if key == derefKey(kp) {
-			vp := b.values[i]
-			// Deletion case. First we update the value, then the key.
-			// This is important for atomic snapshot states.
-			atomic.StoreUint64(&b.topHashes, eraseTopHash(b.topHashes, i))
-			atomic.StorePointer(&b.values[i], nil)
-			atomic.StorePointer(&b.keys[i], nil)
-			leftEmpty := false
-			if hintNonEmpty == 0 {
-				leftEmpty = isEmpty(b)
+		for {
+			topHashes := atomic.LoadUint64(&b.topHashMutex)
+			for i := 0; i < entriesPerMapBucket; i++ {
+				kp := b.keys[i]
+				if kp == nil || !topHashMatch(hash, topHashes, i) {
+					continue
+				}
+				if key == derefKey(kp) {
+					vp := b.values[i]
+					// Deletion case. First we update the value, then the key.
+					// This is important for atomic snapshot states.
+					atomic.StoreUint64(&b.topHashMutex, eraseTopHash(topHashes, i))
+					atomic.StorePointer(&b.values[i], nil)
+					atomic.StorePointer(&b.keys[i], nil)
+					leftEmpty := false
+					if hintNonEmpty == 0 {
+						leftEmpty = isEmpty(b)
+					}
+					unlockBucket(&rootb.topHashMutex)
+					table.addSize(bidx, -1)
+					// Might need to shrink the table.
+					if leftEmpty {
+						m.resize(table, mapShrinkHint)
+					}
+					return derefValue(vp), true
+				}
+				hintNonEmpty++
 			}
-			b.mu.Unlock()
-			addSize(table, bidx, -1)
-			// Might need to shrink the table.
-			if leftEmpty {
-				m.resize(table, mapShrinkHint)
+			if b.next == nil {
+				unlockBucket(&rootb.topHashMutex)
+				return
 			}
-			return derefValue(vp), true
+			b = (*bucketPadded)(b.next)
 		}
-		hintNonEmpty++
 	}
-	b.mu.Unlock()
-	return nil, false
 }
 
 // Delete deletes the value for a key.
@@ -401,13 +459,19 @@ func (m *Map) Delete(key string) {
 	m.LoadAndDelete(key)
 }
 
-func isEmpty(b *bucket) bool {
-	for i := 0; i < entriesPerMapBucket; i++ {
-		if b.keys[i] != nil {
-			return false
+func isEmpty(rootb *bucketPadded) bool {
+	b := rootb
+	for {
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if b.keys[i] != nil {
+				return false
+			}
 		}
+		if b.next == nil {
+			return true
+		}
+		b = (*bucketPadded)(b.next)
 	}
-	return true
 }
 
 // Range calls f sequentially for each key and value present in the
@@ -427,18 +491,26 @@ func (m *Map) Range(f func(key string, value interface{}) bool) {
 	tablep := atomic.LoadPointer(&m.table)
 	table := *(*mapTable)(tablep)
 	for i := range table.buckets {
-		n := copyRangeEntries(&table.buckets[i], &bentries)
-		for j := 0; j < n; j++ {
-			k := derefKey(bentries[j].key)
-			v := derefValue(bentries[j].value)
-			if !f(k, v) {
-				return
+		b := &table.buckets[i]
+		for {
+			n := copyRangeEntries(b, &bentries)
+			for j := 0; j < n; j++ {
+				k := derefKey(bentries[j].key)
+				v := derefValue(bentries[j].value)
+				if !f(k, v) {
+					return
+				}
+			}
+			bucketPtr := atomic.LoadPointer(&b.next)
+			if bucketPtr == nil {
+				break
 			}
+			b = (*bucketPadded)(bucketPtr)
 		}
 	}
 }
 
-func copyRangeEntries(b *bucket, destEntries *[entriesPerMapBucket]rangeEntry) int {
+func copyRangeEntries(b *bucketPadded, destEntries *[entriesPerMapBucket]rangeEntry) int {
 	n := 0
 	for i := 0; i < entriesPerMapBucket; i++ {
 	atomic_snapshot:
@@ -465,7 +537,7 @@ func copyRangeEntries(b *bucket, destEntries *[entriesPerMapBucket]rangeEntry) i
 // Size returns current size of the map.
 func (m *Map) Size() int {
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
-	return int(sumSize(table))
+	return int(table.sumSize())
 }
 
 func derefKey(keyPtr unsafe.Pointer) string {
@@ -480,8 +552,30 @@ func bucketIdx(table *mapTable, hash uint64) uint64 {
 	return uint64(len(table.buckets)-1) & hash
 }
 
+func lockBucket(mu *uint64) {
+	for {
+		var v uint64
+		for {
+			v = atomic.LoadUint64(mu)
+			if v&1 != 1 {
+				break
+			}
+			runtime.Gosched()
+		}
+		if atomic.CompareAndSwapUint64(mu, v, v|1) {
+			return
+		}
+		runtime.Gosched()
+	}
+}
+
+func unlockBucket(mu *uint64) {
+	v := atomic.LoadUint64(mu)
+	atomic.StoreUint64(mu, v&^1)
+}
+
 func topHashMatch(hash, topHashes uint64, idx int) bool {
-	if topHashes&(1<<idx) == 0 {
+	if topHashes&(1<<(idx+1)) == 0 {
 		// Entry is not present.
 		return false
 	}
@@ -497,24 +591,25 @@ func storeTopHash(hash, topHashes uint64, idx int) uint64 {
 	// Store top byte of the given hash.
 	top := (hash >> 56) << (8 * (entriesPerMapBucket - idx))
 	topHashes = topHashes | top
-	return topHashes | (1 << idx)
+	topHashes = topHashes | (1 << (idx + 1))
+	return topHashes | (1 << (idx + 1))
 }
 
 func eraseTopHash(topHashes uint64, idx int) uint64 {
-	return topHashes &^ (1 << idx)
+	return topHashes &^ (1 << (idx + 1))
 }
 
-func addSize(table *mapTable, bucketIdx uint64, delta int) {
+func (table *mapTable) addSize(bucketIdx uint64, delta int) {
 	cidx := uint64(len(table.size)-1) & bucketIdx
 	atomic.AddInt64(&table.size[cidx].c, int64(delta))
 }
 
-func addSizeNonAtomic(table *mapTable, bucketIdx uint64, delta int) {
+func (table *mapTable) addSizePlain(bucketIdx uint64, delta int) {
 	cidx := uint64(len(table.size)-1) & bucketIdx
 	table.size[cidx].c += int64(delta)
 }
 
-func sumSize(table *mapTable) int64 {
+func (table *mapTable) sumSize() int64 {
 	sum := int64(0)
 	for i := range table.size {
 		sum += atomic.LoadInt64(&table.size[i].c)
@@ -557,17 +652,23 @@ func (m *Map) stats() mapStats {
 	}
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
 	stats.TableLen = len(table.buckets)
-	stats.Counter = int(sumSize(table))
+	stats.Counter = int(table.sumSize())
 	stats.CounterLen = len(table.size)
 	for i := range table.buckets {
 		numEntries := 0
-		stats.Capacity += entriesPerMapBucket
 		b := &table.buckets[i]
-		for i := 0; i < entriesPerMapBucket; i++ {
-			if atomic.LoadPointer(&b.keys[i]) != nil {
-				stats.Size++
-				numEntries++
+		for {
+			stats.Capacity += entriesPerMapBucket
+			for i := 0; i < entriesPerMapBucket; i++ {
+				if atomic.LoadPointer(&b.keys[i]) != nil {
+					stats.Size++
+					numEntries++
+				}
+			}
+			if b.next == nil {
+				break
 			}
+			b = (*bucketPadded)(b.next)
 		}
 		if numEntries < stats.MinEntries {
 			stats.MinEntries = numEntries
diff --git a/mapof.go b/mapof.go
index 6427f3f..77dda58 100644
--- a/mapof.go
+++ b/mapof.go
@@ -56,27 +56,33 @@ func (m *MapOf[V]) Load(key string) (value V, ok bool) {
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
 	bidx := bucketIdx(table, hash)
 	b := &table.buckets[bidx]
-	topHashes := atomic.LoadUint64(&b.topHashes)
-	for i := 0; i < entriesPerMapBucket; i++ {
-		if !topHashMatch(hash, topHashes, i) {
-			continue
-		}
-	atomic_snapshot:
-		// Start atomic snapshot.
-		vp := atomic.LoadPointer(&b.values[i])
-		kp := atomic.LoadPointer(&b.keys[i])
-		if kp != nil && vp != nil {
-			if key == derefKey(kp) {
-				if uintptr(vp) == uintptr(atomic.LoadPointer(&b.values[i])) {
-					// Atomic snapshot succeeded.
-					return derefTypedValue[V](vp), true
+	for {
+		topHashes := atomic.LoadUint64(&b.topHashMutex)
+		for i := 0; i < entriesPerMapBucket; i++ {
+			if !topHashMatch(hash, topHashes, i) {
+				continue
+			}
+		atomic_snapshot:
+			// Start atomic snapshot.
+			vp := atomic.LoadPointer(&b.values[i])
+			kp := atomic.LoadPointer(&b.keys[i])
+			if kp != nil && vp != nil {
+				if key == derefKey(kp) {
+					if uintptr(vp) == uintptr(atomic.LoadPointer(&b.values[i])) {
+						// Atomic snapshot succeeded.
+						return derefTypedValue[V](vp), true
+					}
+					// Concurrent update/remove. Go for another spin.
+					goto atomic_snapshot
 				}
-				// Concurrent update/remove. Go for another spin.
-				goto atomic_snapshot
 			}
 		}
+		bucketPtr := atomic.LoadPointer(&b.next)
+		if bucketPtr == nil {
+			return
+		}
+		b = (*bucketPadded)(bucketPtr)
 	}
-	return value, false
 }
 
 // Store sets the value for a key.
@@ -109,71 +115,94 @@ func (m *MapOf[V]) doStore(key string, value V, loadIfExists bool) (V, bool) {
 	// Write path.
 	hash := maphash64(key)
 	for {
+	store_attempt:
 		var (
 			emptykp, emptyvp *unsafe.Pointer
 			emptyidx         int
 		)
 		table := (*mapTable)(atomic.LoadPointer(&m.table))
+		tableLen := len(table.buckets)
 		bidx := bucketIdx(table, hash)
-		b := &table.buckets[bidx]
-		b.mu.Lock()
+		rootb := &table.buckets[bidx]
+		b := rootb
+		lockBucket(&rootb.topHashMutex)
 		if m.newerTableExists(table) {
 			// Someone resized the table. Go for another attempt.
-			b.mu.Unlock()
-			continue
+			unlockBucket(&rootb.topHashMutex)
+			goto store_attempt
 		}
 		if m.resizeInProgress() {
 			// Resize is in progress. Wait, then go for another attempt.
-			b.mu.Unlock()
+			unlockBucket(&rootb.topHashMutex)
 			m.waitForResize()
-			continue
+			goto store_attempt
 		}
-		for i := 0; i < entriesPerMapBucket; i++ {
-			if b.keys[i] == nil {
-				if emptykp == nil {
-					emptykp = &b.keys[i]
-					emptyvp = &b.values[i]
-					emptyidx = i
+		for {
+			topHashes := atomic.LoadUint64(&b.topHashMutex)
+			for i := 0; i < entriesPerMapBucket; i++ {
+				if b.keys[i] == nil {
+					if emptykp == nil {
+						emptykp = &b.keys[i]
+						emptyvp = &b.values[i]
+						emptyidx = i
+					}
+					continue
 				}
-				continue
-			}
-			if !topHashMatch(hash, b.topHashes, i) {
-				continue
-			}
-			if key == derefKey(b.keys[i]) {
-				vp := b.values[i]
-				if loadIfExists {
-					b.mu.Unlock()
+				if !topHashMatch(hash, topHashes, i) {
+					continue
+				}
+				if key == derefKey(b.keys[i]) {
+					vp := b.values[i]
+					if loadIfExists {
+						unlockBucket(&rootb.topHashMutex)
+						return derefTypedValue[V](vp), true
+					}
+					// In-place update case. We get a copy of the value via an
+					// interface{} on each call, thus the live value pointers are
+					// unique. Otherwise atomic snapshot won't be correct in case
+					// of multiple Store calls using the same value.
+					var wv interface{} = value
+					nvp := unsafe.Pointer(&wv)
+					if assertionsEnabled && vp == nvp {
+						panic("non-unique value pointer")
+					}
+					atomic.StorePointer(&b.values[i], nvp)
+					unlockBucket(&rootb.topHashMutex)
 					return derefTypedValue[V](vp), true
 				}
-				// In-place update case. We get a copy of the value via an
-				// interface{} on each call, thus the live value pointers are
-				// unique. Otherwise atomic snapshot won't be correct in case
-				// of multiple Store calls using the same value.
-				var wv interface{} = value
-				nvp := unsafe.Pointer(&wv)
-				if assertionsEnabled && vp == nvp {
-					panic("non-unique value pointer")
+			}
+			if b.next == nil {
+				if emptykp != nil {
+					// Insertion case. First we update the value, then the key.
+					// This is important for atomic snapshot states.
+					atomic.StoreUint64(&b.topHashMutex, storeTopHash(hash, topHashes, emptyidx))
+					var wv interface{} = value
+					atomic.StorePointer(emptyvp, unsafe.Pointer(&wv))
+					atomic.StorePointer(emptykp, unsafe.Pointer(&key))
+					unlockBucket(&rootb.topHashMutex)
+					table.addSize(bidx, 1)
+					return value, false
 				}
-				atomic.StorePointer(&b.values[i], nvp)
-				b.mu.Unlock()
-				return derefTypedValue[V](vp), true
+				growThreshold := float64(tableLen) * entriesPerMapBucket * mapLoadFactor
+				if table.sumSize() > int64(growThreshold) {
+					// Need to grow the table. Then go for another attempt.
+					unlockBucket(&rootb.topHashMutex)
+					m.resize(table, mapGrowHint)
+					goto store_attempt
+				}
+				// Create and append a new bucket.
+				newb := new(bucketPadded)
+				newb.keys[0] = unsafe.Pointer(&key)
+				var wv interface{} = value
+				newb.values[0] = unsafe.Pointer(&wv)
+				newb.topHashMutex = storeTopHash(hash, topHashes, emptyidx)
+				atomic.StorePointer(&b.next, unsafe.Pointer(newb))
+				unlockBucket(&rootb.topHashMutex)
+				table.addSize(bidx, 1)
+				return value, false
 			}
+			b = (*bucketPadded)(b.next)
 		}
-		if emptykp != nil {
-			// Insertion case. First we update the value, then the key.
-			// This is important for atomic snapshot states.
-			atomic.StoreUint64(&b.topHashes, storeTopHash(hash, b.topHashes, emptyidx))
-			var wv interface{} = value
-			atomic.StorePointer(emptyvp, unsafe.Pointer(&wv))
-			atomic.StorePointer(emptykp, unsafe.Pointer(&key))
-			b.mu.Unlock()
-			addSize(table, bidx, 1)
-			return value, false
-		}
-		// Need to grow the table. Then go for another attempt.
-		b.mu.Unlock()
-		m.resize(table, mapGrowHint)
 	}
 }
 
@@ -200,7 +229,7 @@ func (m *MapOf[V]) resize(table *mapTable, hint mapResizeHint) {
 	// Fast path for shrink attempts.
 	if hint == mapShrinkHint {
 		shrinkThreshold = int64((tableLen * entriesPerMapBucket) / mapShrinkFraction)
-		if tableLen == minMapTableLen || sumSize(table) > shrinkThreshold {
+		if tableLen == minMapTableLen || table.sumSize() > shrinkThreshold {
 			return
 		}
 	}
@@ -217,7 +246,7 @@ func (m *MapOf[V]) resize(table *mapTable, hint mapResizeHint) {
 		atomic.AddInt64(&m.totalGrowths, 1)
 		newTable = newMapTable(tableLen << 1)
 	case mapShrinkHint:
-		if sumSize(table) <= shrinkThreshold {
+		if table.sumSize() <= shrinkThreshold {
 			// Shrink the table with factor of 2.
 			atomic.AddInt64(&m.totalShrinks, 1)
 			newTable = newMapTable(tableLen >> 1)
@@ -232,15 +261,9 @@ func (m *MapOf[V]) resize(table *mapTable, hint mapResizeHint) {
 	default:
 		panic(fmt.Sprintf("unexpected resize hint: %d", hint))
 	}
-copy:
 	for i := 0; i < tableLen; i++ {
-		copied, ok := copyBucket(&table.buckets[i], newTable)
-		if !ok {
-			// Table size is insufficient, need to grow it.
-			newTable = newMapTable(len(newTable.buckets) << 1)
-			goto copy
-		}
-		addSizeNonAtomic(newTable, uint64(i), copied)
+		copied := copyBucket(&table.buckets[i], newTable)
+		newTable.addSizePlain(uint64(i), copied)
 	}
 	// Publish the new table and wake up all waiters.
 	atomic.StorePointer(&m.table, unsafe.Pointer(newTable))
@@ -255,51 +278,59 @@ copy:
 // present.
 func (m *MapOf[V]) LoadAndDelete(key string) (value V, loaded bool) {
 	hash := maphash64(key)
-delete_attempt:
-	hintNonEmpty := 0
-	table := (*mapTable)(atomic.LoadPointer(&m.table))
-	bidx := bucketIdx(table, hash)
-	b := &table.buckets[bidx]
-	b.mu.Lock()
-	if m.newerTableExists(table) {
-		// Someone resized the table. Go for another attempt.
-		b.mu.Unlock()
-		goto delete_attempt
-	}
-	if m.resizeInProgress() {
-		// Resize is in progress. Wait, then go for another attempt.
-		b.mu.Unlock()
-		m.waitForResize()
-		goto delete_attempt
-	}
-	for i := 0; i < entriesPerMapBucket; i++ {
-		kp := b.keys[i]
-		if kp == nil || !topHashMatch(hash, b.topHashes, i) {
+	for {
+		hintNonEmpty := 0
+		table := (*mapTable)(atomic.LoadPointer(&m.table))
+		bidx := bucketIdx(table, hash)
+		rootb := &table.buckets[bidx]
+		b := rootb
+		lockBucket(&rootb.topHashMutex)
+		if m.newerTableExists(table) {
+			// Someone resized the table. Go for another attempt.
+			unlockBucket(&rootb.topHashMutex)
 			continue
 		}
-		if key == derefKey(kp) {
-			vp := b.values[i]
-			// Deletion case. First we update the value, then the key.
-			// This is important for atomic snapshot states.
-			atomic.StoreUint64(&b.topHashes, eraseTopHash(b.topHashes, i))
-			atomic.StorePointer(&b.values[i], nil)
-			atomic.StorePointer(&b.keys[i], nil)
-			leftEmpty := false
-			if hintNonEmpty == 0 {
-				leftEmpty = isEmpty(b)
+		if m.resizeInProgress() {
+			// Resize is in progress. Wait, then go for another attempt.
+			unlockBucket(&rootb.topHashMutex)
+			m.waitForResize()
+			continue
+		}
+		for {
+			topHashes := atomic.LoadUint64(&b.topHashMutex)
+			for i := 0; i < entriesPerMapBucket; i++ {
+				kp := b.keys[i]
+				if kp == nil || !topHashMatch(hash, topHashes, i) {
+					continue
+				}
+				if key == derefKey(kp) {
+					vp := b.values[i]
+					// Deletion case. First we update the value, then the key.
+					// This is important for atomic snapshot states.
+					atomic.StoreUint64(&b.topHashMutex, eraseTopHash(topHashes, i))
+					atomic.StorePointer(&b.values[i], nil)
+					atomic.StorePointer(&b.keys[i], nil)
+					leftEmpty := false
+					if hintNonEmpty == 0 {
+						leftEmpty = isEmpty(b)
+					}
+					unlockBucket(&rootb.topHashMutex)
+					table.addSize(bidx, -1)
+					// Might need to shrink the table.
+					if leftEmpty {
+						m.resize(table, mapShrinkHint)
+					}
+					return derefTypedValue[V](vp), true
+				}
+				hintNonEmpty++
 			}
-			b.mu.Unlock()
-			addSize(table, bidx, -1)
-			// Might need to shrink the table.
-			if leftEmpty {
-				m.resize(table, mapShrinkHint)
+			if b.next == nil {
+				unlockBucket(&rootb.topHashMutex)
+				return
 			}
-			return derefTypedValue[V](vp), true
+			b = (*bucketPadded)(b.next)
 		}
-		hintNonEmpty++
 	}
-	b.mu.Unlock()
-	return value, false
 }
 
 // Delete deletes the value for a key.
@@ -324,13 +355,21 @@ func (m *MapOf[V]) Range(f func(key string, value V) bool) {
 	tablep := atomic.LoadPointer(&m.table)
 	table := *(*mapTable)(tablep)
 	for i := range table.buckets {
-		n := copyRangeEntries(&table.buckets[i], &bentries)
-		for j := 0; j < n; j++ {
-			k := derefKey(bentries[j].key)
-			v := derefTypedValue[V](bentries[j].value)
-			if !f(k, v) {
-				return
+		b := &table.buckets[i]
+		for {
+			n := copyRangeEntries(b, &bentries)
+			for j := 0; j < n; j++ {
+				k := derefKey(bentries[j].key)
+				v := derefTypedValue[V](bentries[j].value)
+				if !f(k, v) {
+					return
+				}
+			}
+			bucketPtr := atomic.LoadPointer(&b.next)
+			if bucketPtr == nil {
+				break
 			}
+			b = (*bucketPadded)(bucketPtr)
 		}
 	}
 }
@@ -338,7 +377,7 @@ func (m *MapOf[V]) Range(f func(key string, value V) bool) {
 // Size returns current size of the map.
 func (m *MapOf[V]) Size() int {
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
-	return int(sumSize(table))
+	return int(table.sumSize())
 }
 
 func derefTypedValue[V any](valuePtr unsafe.Pointer) (val V) {
@@ -354,17 +393,23 @@ func (m *MapOf[V]) stats() mapStats {
 	}
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
 	stats.TableLen = len(table.buckets)
-	stats.Counter = int(sumSize(table))
+	stats.Counter = int(table.sumSize())
 	stats.CounterLen = len(table.size)
 	for i := range table.buckets {
 		numEntries := 0
-		stats.Capacity += entriesPerMapBucket
 		b := &table.buckets[i]
-		for i := 0; i < entriesPerMapBucket; i++ {
-			if atomic.LoadPointer(&b.keys[i]) != nil {
-				stats.Size++
-				numEntries++
+		for {
+			stats.Capacity += entriesPerMapBucket
+			for i := 0; i < entriesPerMapBucket; i++ {
+				if atomic.LoadPointer(&b.keys[i]) != nil {
+					stats.Size++
+					numEntries++
+				}
+			}
+			if b.next == nil {
+				break
 			}
+			b = (*bucketPadded)(b.next)
 		}
 		if numEntries < stats.MinEntries {
 			stats.MinEntries = numEntries
diff --git a/mpmcqueue.go b/mpmcqueue.go
index b90aed8..96584e6 100644
--- a/mpmcqueue.go
+++ b/mpmcqueue.go
@@ -22,16 +22,16 @@ type MPMCQueue struct {
 	tail uint64
 	//lint:ignore U1000 prevents false sharing
 	tpad  [cacheLineSize - 8]byte
-	slots []slot
+	slots []slotPadded
 }
 
-type slot struct {
-	slotInternal
+type slotPadded struct {
+	slot
 	//lint:ignore U1000 prevents false sharing
-	pad [cacheLineSize - unsafe.Sizeof(slotInternal{})]byte
+	pad [cacheLineSize - unsafe.Sizeof(slot{})]byte
 }
 
-type slotInternal struct {
+type slot struct {
 	turn uint64
 	item interface{}
 }
@@ -44,7 +44,7 @@ func NewMPMCQueue(capacity int) *MPMCQueue {
 	}
 	return &MPMCQueue{
 		cap:   uint64(capacity),
-		slots: make([]slot, capacity),
+		slots: make([]slotPadded, capacity),
 	}
 }
 


Test patch:
diff --git a/export_test.go b/export_test.go
index ebd63c9..1db3c9e 100644
--- a/export_test.go
+++ b/export_test.go
@@ -2,12 +2,13 @@ package xsync
 
 const (
 	EntriesPerMapBucket = entriesPerMapBucket
+	MapLoadFactor       = mapLoadFactor
 	MinMapTableLen      = minMapTableLen
 	MaxMapCounterLen    = maxMapCounterLen
 )
 
 type (
-	Bucket = bucket
+	BucketPadded = bucketPadded
 )
 
 type MapStats struct {
@@ -18,6 +19,14 @@ func CollectMapStats(m *Map) MapStats {
 	return MapStats{m.stats()}
 }
 
+func LockBucket(mu *uint64) {
+	lockBucket(mu)
+}
+
+func UnlockBucket(mu *uint64) {
+	unlockBucket(mu)
+}
+
 func TopHashMatch(hash, topHashes uint64, idx int) bool {
 	return topHashMatch(hash, topHashes, idx)
 }
diff --git a/map_test.go b/map_test.go
index 4195936..3175faa 100644
--- a/map_test.go
+++ b/map_test.go
@@ -1,10 +1,13 @@
 package xsync_test
 
 import (
+	"fmt"
+	"math"
 	"math/bits"
 	"math/rand"
 	"strconv"
 	"sync"
+	"sync/atomic"
 	"testing"
 	"time"
 	"unsafe"
@@ -44,7 +47,7 @@ func TestMap_BucketStructSize(t *testing.T) {
 	if bits.UintSize != 64 {
 		return // skip for 32-bit builds
 	}
-	size := unsafe.Sizeof(Bucket{})
+	size := unsafe.Sizeof(BucketPadded{})
 	if size != 128 {
 		t.Errorf("size of 128B (2 cache lines) is expected, got: %d", size)
 	}
@@ -371,7 +374,7 @@ func TestMapResize(t *testing.T) {
 	if stats.Size != numEntries {
 		t.Errorf("size was too small: %d", stats.Size)
 	}
-	expectedCapacity := stats.TableLen * EntriesPerMapBucket
+	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.TableLen * EntriesPerMapBucket
 	if stats.Capacity > expectedCapacity {
 		t.Errorf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}
@@ -542,69 +545,133 @@ func TestMapParallelStoresAndDeletes(t *testing.T) {
 	}
 }
 
-func TestMapTopHash_Store(t *testing.T) {
+func TestMapTopHashMutex(t *testing.T) {
+	const (
+		numLockers    = 4
+		numIterations = 1000
+	)
+	var (
+		activity int32
+		mu       uint64
+	)
+	cdone := make(chan bool)
+	for i := 0; i < numLockers; i++ {
+		go func() {
+			for i := 0; i < numIterations; i++ {
+				LockBucket(&mu)
+				n := atomic.AddInt32(&activity, 1)
+				if n != 1 {
+					UnlockBucket(&mu)
+					panic(fmt.Sprintf("lock(%d)\n", n))
+				}
+				atomic.AddInt32(&activity, -1)
+				UnlockBucket(&mu)
+			}
+			cdone <- true
+		}()
+	}
+	// Wait for all lockers to finish.
+	for i := 0; i < numLockers; i++ {
+		<-cdone
+	}
+}
+
+func TestMapTopHashMutex_Set_NoLock(t *testing.T) {
+	mu := uint64(0)
+	testMapTopHashMutex_Set(t, &mu)
+}
+
+func TestMapTopHashMutex_Set_WhileLocked(t *testing.T) {
+	mu := uint64(0)
+	LockBucket(&mu)
+	defer UnlockBucket(&mu)
+	testMapTopHashMutex_Set(t, &mu)
+}
+
+func testMapTopHashMutex_Set(t *testing.T, topHashes *uint64) {
 	hash := uint64(0xd400000000000000) // top hash is 11010100
-	topHashes := uint64(0)
 	for i := 0; i < EntriesPerMapBucket; i++ {
-		if TopHashMatch(hash, topHashes, i) {
+		if TopHashMatch(hash, *topHashes, i) {
 			t.Errorf("top hash match for all zeros for index %d", i)
 		}
 
-		prevOnes := bits.OnesCount64(topHashes)
-		topHashes = StoreTopHash(hash, topHashes, i)
-		newOnes := bits.OnesCount64(topHashes)
+		prevOnes := bits.OnesCount64(*topHashes)
+		*topHashes = StoreTopHash(hash, *topHashes, i)
+		newOnes := bits.OnesCount64(*topHashes)
 		expectedInc := bits.OnesCount64(hash) + 1
 		if newOnes != prevOnes+expectedInc {
 			t.Errorf("unexpected bits change after store for index %d: %d, %d, %#b",
-				i, newOnes, prevOnes+expectedInc, topHashes)
+				i, newOnes, prevOnes+expectedInc, *topHashes)
 		}
 
-		if !TopHashMatch(hash, topHashes, i) {
-			t.Errorf("top hash mismatch after store for index %d: %#b", i, topHashes)
+		if !TopHashMatch(hash, *topHashes, i) {
+			t.Errorf("top hash mismatch after store for index %d: %#b", i, *topHashes)
 		}
 	}
 }
 
-func TestMapTopHash_Erase(t *testing.T) {
+func TestMapTopHashMutex_Delete_NoLock(t *testing.T) {
+	mu := uint64(0)
+	testMapTopHashMutex_Delete(t, &mu)
+}
+
+func TestMapTopHashMutex_Delete_WhileLocked(t *testing.T) {
+	mu := uint64(0)
+	LockBucket(&mu)
+	defer UnlockBucket(&mu)
+	testMapTopHashMutex_Delete(t, &mu)
+}
+
+func testMapTopHashMutex_Delete(t *testing.T, topHashes *uint64) {
 	hash := uint64(0xabababababababab) // top hash is 10101011
-	topHashes := uint64(0)
 	for i := 0; i < EntriesPerMapBucket; i++ {
-		topHashes = StoreTopHash(hash, topHashes, i)
-		ones := bits.OnesCount64(topHashes)
+		*topHashes = StoreTopHash(hash, *topHashes, i)
+		ones := bits.OnesCount64(*topHashes)
 
-		topHashes = EraseTopHash(topHashes, i)
-		if TopHashMatch(hash, topHashes, i) {
-			t.Errorf("top hash match after erase for index %d: %#b", i, topHashes)
+		*topHashes = EraseTopHash(*topHashes, i)
+		if TopHashMatch(hash, *topHashes, i) {
+			t.Errorf("top hash match after erase for index %d: %#b", i, *topHashes)
 		}
 
-		erasedBits := ones - bits.OnesCount64(topHashes)
+		erasedBits := ones - bits.OnesCount64(*topHashes)
 		if erasedBits != 1 {
 			t.Errorf("more than one bit changed after erase: %d, %d", i, erasedBits)
 		}
 	}
 }
 
-func TestMapTopHash_StoreAfterErase(t *testing.T) {
+func TestMapTopHashMutex_SetAfterDelete_NoLock(t *testing.T) {
+	mu := uint64(0)
+	testMapTopHashMutex_SetAfterDelete(t, &mu)
+}
+
+func TestMapTopHashMutex_SetAfterDelete_WhileLocked(t *testing.T) {
+	mu := uint64(0)
+	LockBucket(&mu)
+	defer UnlockBucket(&mu)
+	testMapTopHashMutex_SetAfterDelete(t, &mu)
+}
+
+func testMapTopHashMutex_SetAfterDelete(t *testing.T, topHashes *uint64) {
 	hashOne := uint64(0xd400000000000000) // top hash is 11010100
 	hashTwo := uint64(0xab00000000000000) // top hash is 10101011
 	idx := 3
-	topHashes := uint64(0)
 
-	topHashes = StoreTopHash(hashOne, topHashes, idx)
-	if !TopHashMatch(hashOne, topHashes, idx) {
-		t.Errorf("top hash mismatch for hash one: %#b, %#b", hashOne, topHashes)
+	*topHashes = StoreTopHash(hashOne, *topHashes, idx)
+	if !TopHashMatch(hashOne, *topHashes, idx) {
+		t.Errorf("top hash mismatch for hash one: %#b, %#b", hashOne, *topHashes)
 	}
-	if TopHashMatch(hashTwo, topHashes, idx) {
-		t.Errorf("top hash match for hash two: %#b, %#b", hashTwo, topHashes)
+	if TopHashMatch(hashTwo, *topHashes, idx) {
+		t.Errorf("top hash match for hash two: %#b, %#b", hashTwo, *topHashes)
 	}
 
-	topHashes = EraseTopHash(topHashes, idx)
-	topHashes = StoreTopHash(hashTwo, topHashes, idx)
-	if TopHashMatch(hashOne, topHashes, idx) {
-		t.Errorf("top hash match for hash one: %#b, %#b", hashOne, topHashes)
+	*topHashes = EraseTopHash(*topHashes, idx)
+	*topHashes = StoreTopHash(hashTwo, *topHashes, idx)
+	if TopHashMatch(hashOne, *topHashes, idx) {
+		t.Errorf("top hash match for hash one: %#b, %#b", hashOne, *topHashes)
 	}
-	if !TopHashMatch(hashTwo, topHashes, idx) {
-		t.Errorf("top hash mismatch for hash two: %#b, %#b", hashTwo, topHashes)
+	if !TopHashMatch(hashTwo, *topHashes, idx) {
+		t.Errorf("top hash mismatch for hash two: %#b, %#b", hashTwo, *topHashes)
 	}
 }
 
diff --git a/mapof_test.go b/mapof_test.go
index 2d3b9ed..029e127 100644
--- a/mapof_test.go
+++ b/mapof_test.go
@@ -4,6 +4,7 @@
 package xsync_test
 
 import (
+	"math"
 	"math/rand"
 	"strconv"
 	"testing"
@@ -332,7 +333,7 @@ func TestMapOfResize(t *testing.T) {
 	if stats.Size != numEntries {
 		t.Errorf("size was too small: %d", stats.Size)
 	}
-	expectedCapacity := stats.TableLen * EntriesPerMapBucket
+	expectedCapacity := int(math.RoundToEven(MapLoadFactor+1)) * stats.TableLen * EntriesPerMapBucket
 	if stats.Capacity > expectedCapacity {
 		t.Errorf("capacity was too large: %d, expected: %d", stats.Capacity, expectedCapacity)
 	}