cornelk / hashmap Goto Github PK

View Code? Open in Web Editor NEW

1.7K 41.0 111.0 234 KB

A Golang lock-free thread-safe HashMap optimized for fastest read access.

License: Apache License 2.0

Go 97.43% Makefile 2.57%

golang lock-free hashmap go map fast thread-safe

hashmap's Introduction

hashmap

Overview

A Golang lock-free thread-safe HashMap optimized for fastest read access.

It is not a general-use HashMap and currently has slow write performance for write heavy uses.

The minimal supported Golang version is 1.19 as it makes use of Generics and the new atomic package helpers.

Usage

Example uint8 key map uses:

m := New[uint8, int]()
m.Set(1, 123)
value, ok := m.Get(1)

Example string key map uses:

m := New[string, int]()
m.Set("amount", 123)
value, ok := m.Get("amount")

Using the map to count URL requests:

m := New[string, *int64]()
var i int64
counter, _ := m.GetOrInsert("api/123", &i)
atomic.AddInt64(counter, 1) // increase counter
...
count := atomic.LoadInt64(counter) // read counter

Benchmarks

Reading from the hash map for numeric key types in a thread-safe way is faster than reading from a standard Golang map in an unsafe way and four times faster than Golang's sync.Map:

ReadHashMapUint-8                676ns ± 0%
ReadHaxMapUint-8                 689ns ± 1%
ReadGoMapUintUnsafe-8            792ns ± 0%
ReadXsyncMapUint-8               954ns ± 0%
ReadGoSyncMapUint-8             2.62µs ± 1%
ReadSkipMapUint-8               3.27µs ±10%
ReadGoMapUintMutex-8            29.6µs ± 2%

Reading from the map while writes are happening:

ReadHashMapWithWritesUint-8      860ns ± 1%
ReadHaxMapWithWritesUint-8       930ns ± 1%
ReadGoSyncMapWithWritesUint-8   3.06µs ± 2%

Write performance without any concurrent reads:

WriteGoMapMutexUint-8           14.8µs ± 2%
WriteHashMapUint-8              22.3µs ± 1%
WriteGoSyncMapUint-8            69.3µs ± 0%

The benchmarks were run with Golang 1.19.1 on Linux and a Ryzen 9 5900X CPU using make benchmark-perflock.

Technical details

Technical design decisions have been made based on benchmarks that are stored in an external repository: go-benchmark
The library uses a sorted linked list and a slice as an index into that list.
The Get() function contains helper functions that have been inlined manually until the Golang compiler will inline them automatically.
It optimizes the slice access by circumventing the Golang size check when reading from the slice. Once a slice is allocated, the size of it does not change. The library limits the index into the slice, therefore the Golang size check is obsolete. When the slice reaches a defined fill rate, a bigger slice is allocated and all keys are recalculated and transferred into the new slice.
For hashing, specialized xxhash implementations are used that match the size of the key type where available

hashmap's People

Contributors

Stargazers

Watchers

Forkers

genki askldfhjg songshine pelioniot lalex prateek mayujian thatsmrtalbot seoester brunotm mrdefinite abramd piotrkowalczuk kplachkov bhou zhanglei goniubi priestd09 lubaoyilang sysbot linecode sharmaansh21 ankitm27 leverly xingzegao lisprez denisse-dev killheaven beeketing listen-lavender influx6 wenjun001 rasreee tigrato tsingson ismiyati withlin isgasho backwardn datashit futuretea coraxster amitgoibibo merkles hoang17 ibytechaos qichaoshen82 maheshrkumar cssivision zhangjyr pounze eqto junftnt basnijholt yethu malumar slrkskfzz semaj steeling avivklas vforks abdulrahman-khalid itsabgr lindianfeng ethreads q-meet cootieshots ii64 leeonsoft asad-awadia forkkit dumpmemory developgo tide999 doytsujin sunquancheng soyeon-bak brucearies minxinping0105 pkafma-aon everytt couchbasedeps undertreetech noahnut alvin-tosh sishui phial3 smallnest gandalf1024 fufuok golang-libs hanson-tsai puzpuzpuz bruhitsabunny menglh godcong karlmcguire ss49919201 giddily iq-scm

hashmap's Issues

New release

Hello

When are you gonna make a new release that includes the concurrency fix?
Thanks.

list add method is not correct

Now the add method code is like this:

func (l *List[Key, Value]) Add(searchStart *ListElement[Key, Value], hash uintptr, key Key, value Value) (element *ListElement[Key, Value], existed bool, inserted bool) {
	left, found, right := l.search(searchStart, hash, key)
	if found != nil { // existing item found
		return found, true, false
	}

	element = &ListElement[Key, Value]{
		key:     key,
		keyHash: hash,
	}
	element.value.Store(&value)
	return element, false, l.insertAt(element, left, right)
}

The problem exists :

element.value.Store(&value)
return element, false, l.insertAt(element, left, right)

This is not a atomic operation.The proposal atomicOp may solve this if atomicpointer with other metainfo is supported.

Feature: Del() function returns deleted value

Since Get() function may be delayed by resizing, it's hard to delete just inserted value.

.Get on absent key fatalpanics

When using next code got constantly fatalpanic. Probably it is because I'll try to get value from unexistent hash.
var val int
hKey:="new str"
actual, ok := hashTypeSubtype.Get(hKey)
val = actual.(int)
if !ok {
val = 0
}
val++
hashTypeSubtype.Set(hKey, val)

How to deal with write-delay (Get() function) caused by resizing operation

In the document and issue #21, it says Get() function may return nil value while Insert() already returned true. This may cause BUG that hard to debug.

How to deal with it? May be add new GetNoDelay() function?

the speed for set is really really really low

the size bigger，the speed lower！！！！

for different keys

1000 = 1ms

10000 = 200ms

100000 = 129000ms

only suit for small size map

Alignment on 32-bit platforms

While this project specifically calls out 64-bit platforms, I have a need to run it on 32-bit ARM as well.

I believe the sync.atomic functions will fail on 32-bit platforms if not properly aligned. This is noted in the bugs section at the bottom of this page.
https://golang.org/pkg/sync/atomic/#AddUint64

and there is an in-depth discussion here:
https://groups.google.com/forum/m/#!topic/golang-nuts/_nHK6P8_lhw

I think I can fix this. However, I just wanted to know if this is an issue you are already handling - or you even care about handling (totally makes since if its not).

[signal SIGSEGV: segmentation violation code=0x1 addr=0x4 pc=0x1a40e0]

goroutine 1 [running]:
panic(0x414338, 0x96f5e008)
	/usr/lib/arm-poky-linux-gnueabi/go/src/runtime/panic.go:500 +0x33c
sync/atomic.addUint64(0x96ff5484, 0x1, 0x0, 0x1, 0x0)
	/usr/lib/arm-poky-linux-gnueabi/go/src/sync/atomic/64bit_arm.go:31 +0x68
github.com/WigWagCo/maestro/vendor/github.com/cornelk/hashmap.(*List).insertAt(0x96ff5480, 0x97012b40, 0x0, 0x0, 0x0)
	/builds/walt/42/wwrelay-rootfs/yocto/build/tmp/work/armv7a-vfp-neon-poky-linux-gnueabi/maestro/1.0+gitAUTOINC+dc7ed7782e-r0/go-workspace/src/github.com/WigWagCo/maestro/vendor/github.com/cornelk/hashmap/list.go:129 +0xa0
github.com/WigWagCo/maestro/vendor/github.com/cornelk/hashmap.(*List).AddOrUpdate(0x96ff5480, 0x97012b40, 0x970127e0, 0x97012820)```

how can it work?

I stumble upon this when I try to write a lock free LRU and took a quick peek at the latest change and see the below code in the list.go and I am very confused

func (l *List) insertAt(element *ListElement, left *ListElement, right *ListElement) bool {
	if left == nil {
		//element->previous = head
		element.previousElement = unsafe.Pointer(l.head)
		//element->next = right
		element.nextElement = unsafe.Pointer(right)

		// insert at head, head-->next = element
		if !atomic.CompareAndSwapPointer(&l.head.nextElement, unsafe.Pointer(right), unsafe.Pointer(element)) {
			return false // item was modified concurrently
		}

		//right->previous = element
		if right != nil {
			if !atomic.CompareAndSwapPointer(&right.previousElement, unsafe.Pointer(l.head), unsafe.Pointer(element)) {
				return false // item was modified concurrently
			}
		}
	} else {
		element.previousElement = unsafe.Pointer(left)
		element.nextElement = unsafe.Pointer(right)

		if !atomic.CompareAndSwapPointer(&left.nextElement, unsafe.Pointer(right), unsafe.Pointer(element)) {
			return false // item was modified concurrently
		}

		if right != nil {
			if !atomic.CompareAndSwapPointer(&right.previousElement, unsafe.Pointer(left), unsafe.Pointer(element)) {
				return false // item was modified concurrently
			}
		}
	}

IIRC, the second return parts in each if/else branch will leave the list in a broken state. Is that intended?

`[]byte` keys panic on Get

Calling Get() with a key that is a []byte fails. Get converts the key with getHashKey, but then attempts to compare the raw []byte key with

		if element.keyHash == h && element.key == key {

This results in a panic:

panic: runtime error: comparing uncomparable type []uint8 [recovered]
	panic: runtime error: comparing uncomparable type []uint8

Sample test case that causes this:

func TestBAHashMap(t *testing.T) {
	hm := &hashmap.HashMap{}
	key := []byte(`Hello, how are you doing today?`)
	hm.Set(key, 1234)

	if v, ok := hm.Get(key); !ok {
		t.Fail()
	} else if v != 1234 {
		t.Fail()
	}
}

1.19.4

Describe the bug
After upgrade Go to 1.19.4 always got error on build

github.com/cornelk/hashmap

../../GOLANG/pkg/mod/github.com/cornelk/[email protected]/list_element.go:17:13: invalid recursive type atomic.Pointer
../../GOLANG/pkg/mod/github.com/cornelk/[email protected]/list_element.go:17:13: atomic.Pointer refers to
../../GOLANG/pkg/mod/github.com/cornelk/[email protected]/list_element.go:17:22: ListElement refers to
../../GOLANG/pkg/mod/github.com/cornelk/[email protected]/list_element.go:17:13: atomic.Pointer

To Reproduce
install go 1.19.4
use hash map

Expected behavior
compile without errors

System (please complete the following information):

Mac OS 13.0.1:
hash map 1.0.8:

Additional context

Why keys limited to uint64?

Hi, Why keys limited to uint64? Can they be strings?

can it be write safe ？

Benchmark https://github.com/a8m/syncmap

Panic with Mac M1 and Delve debuger

Describe the bug
The library panics when running code with the Delve debugger used by VSCode.
This only happens for me on my M1 Mac and not on a Linux machine.

To Reproduce
Create test file main.go

package main

import (
	"github.com/cornelk/hashmap"
)

func main() {
	hm := hashmap.New[int, string]()

	for i := 0; i < 1000; i++ {
		hm.Set(i, "test")
	}
}

Start up your shell, and make sure you have Delve installed

~/go/bin/dlv debug main.go

Now enter this to the Delve client

continue

PANIC

Expected behavior
Code runs as advertised

System (please complete the following information):

OS: MacOS Monterey M1 - 12.1
Version / Commit: 1.0.4

Additional context

(⎈ |k8s:namespace) ➜  tests git:(main) ✗ cat main.go 
package main

import (
	"github.com/cornelk/hashmap"
)

func main() {
	hm := hashmap.New[int, string]()

	for i := 0; i < 1000; i++ {
		hm.Set(i, "test")
	}
}
(⎈ |k8s:namespace) ➜  tests git:(main) ✗ ~/go/bin/dlv debug main.go
Type 'help' for list of commands.
(dlv) continue
> [unrecovered-panic] runtime.fatalpanic() /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/panic.go:1143 (hits goroutine(1):1 total:1) (PC: 0x1020df2b0)
Warning: debugging optimized function
	runtime.curg._panic.arg: interface {}(string) "runtime error: slice bounds out of range [::8] with capacity 0"
  1138:	// fatalpanic implements an unrecoverable panic. It is like fatalthrow, except
  1139:	// that if msgs != nil, fatalpanic also prints panic messages and decrements
  1140:	// runningPanicDefers once main is blocked from exiting.
  1141:	//
  1142:	//go:nosplit
=>1143:	func fatalpanic(msgs *_panic) {
  1144:		pc := getcallerpc()
  1145:		sp := getcallersp()
  1146:		gp := getg()
  1147:		var docrash bool
  1148:		// Switch to the system stack to avoid any stack growth, which
(dlv) stack
0  0x00000001020df2b0 in runtime.fatalpanic
   at /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/panic.go:1143
1  0x00000001020debc0 in runtime.gopanic
   at /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/panic.go:987
2  0x00000001020dd27c in runtime.goPanicSlice3Acap
   at /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/panic.go:173
3  0x00000001021528e0 in github.com/cespare/xxhash.Sum64
   at /Users/sirakav/go/pkg/mod/github.com/cespare/[email protected]/xxhash_other.go:41
4  0x0000000102155dd0 in github.com/cornelk/hashmap.(*HashMap[go.shape.int_0,go.shape.string_1]).uintptrHasher
   at /Users/sirakav/go/pkg/mod/github.com/cornelk/[email protected]/util_hash.go:26
5  0x0000000102153198 in github.com/cornelk/hashmap.(*HashMap[go.shape.int_0,go.shape.string_1]).setDefaultHasher.func2
   at /Users/sirakav/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237
6  0x0000000102154b68 in github.com/cornelk/hashmap.(*HashMap[go.shape.int_0,go.shape.string_1]).Set
   at /Users/sirakav/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:165
7  0x0000000102152d60 in main.main
   at ./main.go:11
8  0x00000001020e1420 in runtime.main
   at /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/proc.go:250
9  0x000000010210b0c4 in runtime.goexit
   at /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/asm_arm64.s:1165
(dlv)

[BUG] - Doesn't seem to be thread safe

Describe the bug
I've been trying to build a full-text search on the top of this library. There seems a problem related to the library. For a specific set of indexing documents, the length of indexed documents should have been the same at any time of program execution but it's returning different index lengths on each execution of the problem

To Reproduce
https://gist.github.com/sujit-baniya/7f462e8fedbddbe1ede1f0669cada9f7

Expected behavior
The index length and indexed documents should have been the same throughout the multiple executions

System (please complete the following information):

OS: Ubuntu
Version / Commit: Latest

Possible concurrency problem in `grow`

https://github.com/cornelk/hashmap/blob/master/hashmap.go#L329-L333

func (m *HashMap) grow(newSize uintptr, loop bool) {
    // ...

    m.fillIndexItems(newdata) // initialize new index slice with longer keys

    atomic.StorePointer(&m.datamap, unsafe.Pointer(newdata))

    m.fillIndexItems(newdata) // make sure that the new index is up to date with the current state of the linked list

    // ...
}

If there is any data added while grow is running at first m.fillIndexItems(newdata), such data may not be visible when newdata is set to m.datamap and second m.fillIndexItems(newdata) isn't done.

The first element is never deleted from the list

If you delete all the elements from the map, the first one in the list is never deleted.

If you add
for item := range m.Iter() {
t.Errorf("map should be empty but got %v in the iterator.", item)
}

to TestDelete() (shown below) you will see the error.

func TestDelete(t *testing.T) {
m := &HashMap{}
m.Del(0)

elephant := &Animal{"elephant"}
monkey := &Animal{"monkey"}
m.Set(1, unsafe.Pointer(elephant))
m.Set(2, unsafe.Pointer(monkey))
m.Del(0)
m.Del(3)
if m.Len() != 2 {
	t.Error("map should contain exactly two elements.")
}

m.Del(1)
m.Del(1)
m.Del(2)
if m.Len() != 0 {
	t.Error("map should be empty.")
}

for item := range m.Iter() {
	t.Errorf("map should be empty but got %v in the iterator.", item)
}

val, ok := m.Get(1) // Get a missing element.
if ok {
	t.Error("ok should be false when item is missing from map.")
}
if val != nil {
	t.Error("Missing values should return as nil.")
}

m.Set(1, unsafe.Pointer(elephant))

}

About previousElement

I just noticed that previousElement is not necessary for both set and get keys. Why do you still keep it?

Benchmark failed

I add log line before b.fai
b.Logf("%s: error when i==%d", funcName, i)

and i noticed most i is 742, some is 178

if i change benchmarkItemCount to 512 (1<<9), i change to 385 390 403... seems it is not very random

CPU: amd ryzen 2600, ram 16G, os windows 7 64bit

BTW: race detect has no problem

my first log with an error log line:

benchmark_test.go:88: BenchmarkReadHashMapUint: error when i:742 j: %!d(<nil>)

goos: windows
goarch: amd64
pkg: github.com/cornelk/hashmap
--- FAIL: BenchmarkReadHashMapWithWritesUint-12
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:178 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:742 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:178 j:%!d()
benchmark_test.go:114: BenchmarkReadHashMapWithWritesUint: error when i:178 j:%!d()

benchmarkItemCount changed to 512
--- FAIL: BenchmarkReadHashMapUint-12
benchmark_test.go:109: BenchmarkReadHashMapUint: error when i==390
benchmark_test.go:109: BenchmarkReadHashMapUint: error when i==390
benchmark_test.go:109: BenchmarkReadHashMapUint: error when i==390
benchmark_test.go:109: BenchmarkReadHashMapUint: error when i==390
benchmark_test.go:109: BenchmarkReadHashMapUint: error when i==390

Getting this error when there are many go routines trying to access the value

unexpected fault address 0x186a0
fatal error: fault
[signal SIGSEGV: segmentation violation code=0x1 addr=0x186a0 pc=0x560fdd]

goroutine 65484531 [running]:
runtime.throw(0x11ac531, 0x5)
/usr/local/go/src/runtime/panic.go:1116 +0x72 fp=0xc0723f3de8 sp=0xc0723f3db8 pc=0x4a14b2
runtime.sigpanic()
/usr/local/go/src/runtime/signal_unix.go:727 +0x405 fp=0xc0723f3e18 sp=0xc0723f3de8 pc=0x4b7a05
github.com/dchest/siphash.Hash(0xdda7806a4847ec61, 0xb5940c2623a5aabd, 0x186a0, 0x8c7daf5b52fa, 0x8c7daf5b52fa, 0xc0723f3ee8)
/app_data/price_feed_websocket/src/github.com/dchest/siphash/hash_amd64.s:27 +0x5d fp=0xc0723f3e20 sp=0xc0723f3e18 pc=0x560fdd
hashmap.getStringHash(0x186a0, 0x8c7daf5b52fa, 0x8)

Support compound keys

We would like to use struct keys, but do not need a general "supports all structs" approach being asked for in #53 . We can chain hashmaps together, but that is not a good solution for us.

In particular, we were wondering if a few new key types could be added.

type Key128 struct {
    One, Two uint64
}

This would be generally useful for a number of things such as IPv6 address lookups.

These next two would be useful for IPv6 + some other tuple information or two IPv6 addresses.

type Key192 struct {
    One, Two, Three uint64
}

type Key256 struct {
    One, Two, Three, Four uint64
}

Lost writes on table growth

The map loses writes and it looks a lot (I didn't verify that) that the problem is in missing happens-before edges between growth and concurrent writes.

Most like this issue is the same as #46, but I didn't check their reproducer.

Here is a simple reproducer:

func TestMapParallelStores(t *testing.T) {
	const (
		numStorers = 8
		numEntries = 10000
	)
	m := &HashMap{}
	cdone := make(chan bool)
	// Write to the map in parallel.
	for i := 0; i < numStorers; i++ {
		go func(id int) {
			for j := 0; j < numEntries; j++ {
				m.Set(strconv.Itoa(id)+":"+strconv.Itoa(j), j)
			}
			cdone <- true
		}(i)
	}
	// Wait for the goroutines to finish.
	for i := 0; i < numStorers; i++ {
		<-cdone
	}
	// Verify map contents.
	l := m.Len()
	if l != numStorers*numEntries {
		t.Errorf("invalid map length: got %d, expected %d", l, numStorers*numEntries)
	}
	for i := 0; i < numStorers; i++ {
		for j := 0; j < numEntries; j++ {
			k := strconv.Itoa(i) + ":" + strconv.Itoa(j)
			v, ok := m.GetStringKey(k)
			if !ok {
				t.Errorf("value not found for %s", k)
			}
			if vi, ok := v.(int); ok && vi != j {
				t.Errorf("values do not match for %s: %v", k, v)
			}
		}
	}
}

Environment: Ubuntu 20.04, Go 1.16.7.

Expected result: the test passes.
Note: the test may pass with a certain probability. For instance, the test always succeeds if numEntries set to 1 since no rehashing happens in such scenario.

Actual result: the test fails.

$ go test -count=10 -run=TestMapParallelStores
--- FAIL: TestMapParallelStores (3.79s)
    hashmap_test.go:700: value not found for 5:6070
...
--- FAIL: TestMapParallelStores (3.46s)
    hashmap_test.go:700: value not found for 4:3905
    hashmap_test.go:700: value not found for 7:4212
FAIL
exit status 1
FAIL	github.com/cornelk/hashmap	36.795s

DelHashedKey function does not delete the right key

Current implementation lacks key validation since element is grabbed using the right shift and the element key is never compared with the desired key to be deleted.

So what is happening is that the first element returned by indexElement function is deleted

        h := hashmap.New(hashmap.DefaultSize)

	h.SetHashedKey(13698742122855696605, 6)

	h.SetHashedKey(13698742122855696606, 1)

	h.DelHashedKey(13698742122855696606)
	fmt.Println(h.GetHashedKey(13698742122855696606))
	fmt.Println(h.GetHashedKey(13698742122855696605))

Returns:

1 true
<nil> false

Instead of

<nil> false
6 true

Hang when using GetOrInsert and DEL

Describe the bug
Hang when using GetOrInsert and DEL

To Reproduce

func TestDebug(t *testing.T) {
    m := hashmap.New[string, int]()

    var wg sync.WaitGroup
    key := "key"

    wg.Add(1)
    go func() {
        defer wg.Done()
        m.GetOrInsert(key, 9)
        m.Del(key)
    }()

    wg.Add(1)
    go func() {
        defer wg.Done()
        m.GetOrInsert(key, 9)
        m.Del(key)
    }()

    wg.Wait()
}

Expected behavior
not hang

System (please complete the following information):

OS: macos
Version / Commit: latest

Lost Set() while growing

Hi.
Check out this branch. It made to reproduce possible lost with set and grow in the same time.
coraxster@fd471c5

Having break statement while iterating causes goroutine leak

// Iter returns an iterator which could be used in a for range loop.
// The order of the items is sorted by hash keys.
func (m *HashMap) Iter() <-chan KeyValue {
	ch := make(chan KeyValue) // do not use a size here since items can get added during iteration

	go func() {
		list := m.list()
		if list == nil {
			close(ch)
			return
		}
		item := list.First()
		for item != nil {
			value := item.Value()
			ch <- KeyValue{item.key, value}
			item = item.Next()
		}
		close(ch)
	}()

	return ch
}

If you have code like

for e := range m.Iter() {
    break
}

You will block on writing to the channel in Iter() function, and this goroutine will never return. May I suggest implementing a secondary iterator function? Perhaps the usage can be something like this:

iterator := m.GetIterator()
for iterator.Next() {
    // do something
}

Race detector warnings

Hi, I'm getting race detector warnings when accessing a hashmap from multiple goroutines:

WARNING: DATA RACE
Read at 0x00c001b7dbd0 by goroutine 64:
  sync/atomic.LoadInt64()
      /usr/local/Cellar/go/1.11.1/libexec/src/runtime/race_amd64.s:211 +0xb
  .../vendor/github.com/cornelk/hashmap.(*ListElement).Next()
      /.../vendor/github.com/cornelk/hashmap/listelement.go:25 +0x3e
  .../vendor/github.com/cornelk/hashmap.(*HashMap).fillIndexItems()
      /.../vendor/github.com/cornelk/hashmap/hashmap.go:373 +0x77
  .../vendor/github.com/cornelk/hashmap.(*HashMap).grow()
      /.../vendor/github.com/cornelk/hashmap/hashmap.go:339 +0x292

Previous write at 0x00c001b7dbd0 by main goroutine:
  .../vendor/github.com/cornelk/hashmap.(*List).insertAt()
      /.../vendor/github.com/cornelk/hashmap/list.go:128 +0x234
  .../vendor/github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /.../vendor/github.com/cornelk/hashmap/list.go:65 +0xcf
  .../vendor/github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /.../vendor/github.com/cornelk/hashmap/hashmap.go:237 +0xc8
  core-next/vendor/github.com/cornelk/hashmap.(*HashMap).Set()
      /.../vendor/github.com/cornelk/hashmap/hashmap.go:211 +0x172
      /.../main.go:45 +0xd3

But the strange part is, this is code running in a single goroutine - just iterating over set of data and calling .Set() on the hashmap.Hashmap.

Example:

var dataMap hashmap.HashMap
for _, data := range listOfData {
	var innerMap hashmap.HashMap
	for _, innerData := range data.InnerList {
		innerMap.Set(innerData, struct{}{})
	}
	dataMap.Set(data.ID, innerMap)
}

Any ideas what to do here? Am I using the hashmap.Hashmap wrong?

i changed some case with grow and the write speed is more quickly than others

go: downloading github.com/alphadose/haxmap v1.1.0
go: downloading github.com/zhangyunhao116/skipmap v0.10.1
go: downloading github.com/puzpuzpuz/xsync/v2 v2.3.1
go: downloading github.com/zhangyunhao116/fastrand v0.3.0
___gobench_benchmark_test_go.test.exe -test.v -test.paniconexit0 -test.bench ^\QBenchmarkReadHashMapUint\E|\QBenchmarkReadHashMapWithWritesUint\E|\QBenchmarkReadHashMapString\E|\QBenchmarkReadHaxMapUint\E|\QBenchmarkReadHaxMapWithWritesUint\E|\QBenchmarkReadXsyncMapUint\E|\QBenchmarkReadXsyncMapWithWritesUint\E|\QBenchmarkReadSkipMapUint\E|\QBenchmarkReadGoMapUintUnsafe\E|\QBenchmarkReadGoMapUintMutex\E|\QBenchmarkReadGoMapWithWritesUintMutex\E|\QBenchmarkReadGoSyncMapUint\E|\QBenchmarkReadGoSyncMapWithWritesUint\E|\QBenchmarkReadGoMapStringUnsafe\E|\QBenchmarkReadGoMapStringMutex\E|\QBenchmarkWriteHashMapUint\E|\QBenchmarkWriteGoMapMutexUint\E|\QBenchmarkWriteGoSyncMapUint\E$ -test.run ^$ #gosetup
goos: windows
goarch: amd64
pkg: github.com/cornelk/hashmap/benchmarks
cpu: 12th Gen Intel(R) Core(TM) i7-12700H
BenchmarkReadHashMapUint
BenchmarkReadHashMapUint-20                      1873369               637.8 ns/
op
BenchmarkReadHashMapWithWritesUint
BenchmarkReadHashMapWithWritesUint-20            1692416               931.1 ns/
op
BenchmarkReadHashMapString
BenchmarkReadHashMapString-20                     669466              1855 ns/op

BenchmarkReadHaxMapUint
BenchmarkReadHaxMapUint-20                       1306148               908.1 ns/
op
BenchmarkReadHaxMapWithWritesUint
BenchmarkReadHaxMapWithWritesUint-20             1000000              1012 ns/op

BenchmarkReadXsyncMapUint
BenchmarkReadXsyncMapUint-20                     2135721               558.0 ns/
op
BenchmarkReadXsyncMapWithWritesUint
BenchmarkReadXsyncMapWithWritesUint-20           1880142               639.1 ns/
op
BenchmarkReadSkipMapUint
BenchmarkReadSkipMapUint-20                       292872              3739 ns/op

BenchmarkReadGoMapUintUnsafe
BenchmarkReadGoMapUintUnsafe-20                  1429987               826.3 ns/
op
BenchmarkReadGoMapUintMutex
BenchmarkReadGoMapUintMutex-20                     27703             42727 ns/op

BenchmarkReadGoMapWithWritesUintMutex
BenchmarkReadGoMapWithWritesUintMutex-20           16222             74400 ns/op

BenchmarkReadGoSyncMapUint
BenchmarkReadGoSyncMapUint-20                     498957              2874 ns/op

BenchmarkReadGoSyncMapWithWritesUint
BenchmarkReadGoSyncMapWithWritesUint-20           370120              3121 ns/op

BenchmarkReadGoMapStringUnsafe
BenchmarkReadGoMapStringUnsafe-20                 815277              1415 ns/op

BenchmarkReadGoMapStringMutex
BenchmarkReadGoMapStringMutex-20                   26961             45183 ns/op

BenchmarkWriteHashMapUint
BenchmarkWriteHashMapUint-20                       49916             22889 ns/op

BenchmarkWriteGoMapMutexUint
BenchmarkWriteGoMapMutexUint-20                    42570             25949 ns/op

BenchmarkWriteGoSyncMapUint
BenchmarkWriteGoSyncMapUint-20                     16687             71979 ns/op

PASS

minor version updates break the API

We updated our deps today, and discovered the new updates to hashmap have API changes even though the version changes are minor. We're excited with the new changes, but we now have unexpected work to do.

Consider following this guidance: https://go.dev/doc/modules/release-workflow

We were using version 1.0.1, but all minor/patch versions past that are incompatible.

Lost add when deleting concurrently

List implementation has potentional deadlock.
I've made a branch with random Sleeps to reproduce.
Please run TestList_insertAt() few times to get deadlock.
https://github.com/coraxster/hashmap/tree/list-deadlock

Is it safe to call Del or Set during iterating via Range?

When iterating the header via

hashmap/hashmap.go

Line 224 in 28d6fb9

func (m *Map[Key, Value]) Range(f func(Key, Value) bool) {

will call Del or Set in the given f cause skipping of the header or repeat header access?

Stable release

Is public API already stable? If it is the case, can we expect tag v1.0.0 being released?

Question: is possible the values in `left` and `right` are change when inserting a new element?

When inserting a new element into the double-linked sorted list,
is there a chance that just before line 139, the node left and node right are replaced by another thread, but the address of left and right are still the same as before being replaced?

If possible, the list looks the same but node left and node right may already have different values.

Because the following CAS operations are based on pointer addresses, they can succeed.
But the element may be placed in an incorrect place since the values in left and right are already changed.

Is such a case prevented somewhere else if I missed something?

hashmap/list.go

Lines 136 to 148 in c93d96c

 element.previousElement = unsafe.Pointer(left) 

 element.nextElement = unsafe.Pointer(right) 

 if !atomic.CompareAndSwapPointer(&left.nextElement, unsafe.Pointer(right), unsafe.Pointer(element)) { 

 return false // item was modified concurrently 

 } 

 if right != nil { 

 if !atomic.CompareAndSwapPointer(&right.previousElement, unsafe.Pointer(left), unsafe.Pointer(element)) { 

 return false // item was modified concurrently 

 } 

 } 

 }

Seemingly obvious race condition?

Dear reader!

Thank you for the work that you put into this library! I'm looking forward to using it but it seems to (easily?) trigger a race condition with the go race detector. Am I doing something wrong?

package main_test

import (
	"strconv"
	"sync"
	"testing"

	"github.com/cornelk/hashmap"
)

func TestRace(t *testing.T) {
	blocks := &hashmap.HashMap{}

	var wg sync.WaitGroup
	for i := 0; i < 100; i++ {

		wg.Add(1)
		go func(blocks *hashmap.HashMap, i int) {
			defer wg.Done()

			blocks.Set(strconv.Itoa(i), struct{}{})

			wg.Add(1)
			go func(blocks *hashmap.HashMap, i int) {
				defer wg.Done()

				blocks.Get(strconv.Itoa(i))
			}(blocks, i)
		}(blocks, i)
	}

	wg.Wait()
}

When then running something like GO111MODULE=on go test -v -race -count=10

=== RUN   TestRace
==================
WARNING: DATA RACE
Write at 0x00c000058088 by goroutine 8:
  sync/atomic.CompareAndSwapInt64()
      /usr/local/go/src/runtime/race_amd64.s:298 +0xb
  sync/atomic.CompareAndSwapPointer()
      /usr/local/go/src/runtime/atomic_pointer.go:89 +0x45
  github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:65 +0xcf
  github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237 +0xc8
  github.com/cornelk/hashmap.(*HashMap).Set()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:211 +0x172
  coil/engine/race_test.TestRace.func1()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:21 +0xce

Previous write at 0x00c000058088 by goroutine 7:
  github.com/cornelk/hashmap.(*List).insertAt()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:126 +0x207
  github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:65 +0xcf
  github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237 +0xc8
  github.com/cornelk/hashmap.(*HashMap).Set()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:211 +0x172
  coil/engine/race_test.TestRace.func1()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:21 +0xce

Goroutine 8 (running) created at:
  coil/engine/race_test.TestRace()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:18 +0x10b
  testing.tRunner()
      /usr/local/go/src/testing/testing.go:827 +0x162

Goroutine 7 (running) created at:
  coil/engine/race_test.TestRace()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:18 +0x10b
  testing.tRunner()
      /usr/local/go/src/testing/testing.go:827 +0x162
==================
==================
WARNING: DATA RACE
Read at 0x00c0000c6050 by goroutine 10:
  sync/atomic.LoadInt64()
      /usr/local/go/src/runtime/race_amd64.s:211 +0xb
  github.com/cornelk/hashmap.(*ListElement).Next()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/listelement.go:25 +0x3e
  github.com/cornelk/hashmap.(*List).search()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:111 +0xd9
  github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:59 +0x50
  github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237 +0xc8
  github.com/cornelk/hashmap.(*HashMap).Set()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:211 +0x172
  coil/engine/race_test.TestRace.func1()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:21 +0xce

Previous write at 0x00c0000c6050 by goroutine 8:
  github.com/cornelk/hashmap.(*List).insertAt()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:128 +0x234
  github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:65 +0xcf
  github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237 +0xc8
  github.com/cornelk/hashmap.(*HashMap).Set()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:211 +0x172
  coil/engine/race_test.TestRace.func1()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:21 +0xce

Goroutine 10 (running) created at:
  coil/engine/race_test.TestRace()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:18 +0x10b
  testing.tRunner()
      /usr/local/go/src/testing/testing.go:827 +0x162

Goroutine 8 (running) created at:
  coil/engine/race_test.TestRace()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:18 +0x10b
  testing.tRunner()
      /usr/local/go/src/testing/testing.go:827 +0x162
==================
==================
WARNING: DATA RACE
Read at 0x00c0000c6050 by goroutine 12:
  sync/atomic.LoadInt64()
      /usr/local/go/src/runtime/race_amd64.s:211 +0xb
  github.com/cornelk/hashmap.(*ListElement).Next()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/listelement.go:25 +0x3e
  github.com/cornelk/hashmap.(*List).search()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:111 +0xd9
  github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:59 +0x50
  github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237 +0xc8
  github.com/cornelk/hashmap.(*HashMap).Set()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:211 +0x172
  coil/engine/race_test.TestRace.func1()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:21 +0xce

Previous write at 0x00c0000c6050 by goroutine 8:
  github.com/cornelk/hashmap.(*List).insertAt()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:128 +0x234
  github.com/cornelk/hashmap.(*List).AddOrUpdate()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/list.go:65 +0xcf
  github.com/cornelk/hashmap.(*HashMap).insertListElement()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:237 +0xc8
  github.com/cornelk/hashmap.(*HashMap).Set()
      /Users/adam/Projects/go/pkg/mod/github.com/cornelk/[email protected]/hashmap.go:211 +0x172
  coil/engine/race_test.TestRace.func1()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:21 +0xce

Goroutine 12 (running) created at:
  coil/engine/race_test.TestRace()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:18 +0x10b
  testing.tRunner()
      /usr/local/go/src/testing/testing.go:827 +0x162

Goroutine 8 (finished) created at:
  coil/engine/race_test.TestRace()
      /Users/adam/Projects/go/src/github.com/advanderveer/coil/engine/race/main_test.go:18 +0x10b
  testing.tRunner()
      /usr/local/go/src/testing/testing.go:827 +0x162
==================
--- FAIL: TestRace (0.01s)
    testing.go:771: race detected during execution of test
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
=== RUN   TestRace
--- PASS: TestRace (0.01s)
FAIL
exit status 1
FAIL	coil/engine/race	0.123s

Where can I find a `for range` example ?

Unexpected behaviors under large number of data

Describe the bug
Under certain cases of large data it seems that the map performs unexpectedly, meaning it performs differently from sync.Map, a normal map with a RWMutex, and what's expected. I don't know whether these behaviors are expected or whether I'm using the map wrong, but I think I used it correctly.

To Reproduce
Code 1:

func BenchmarkHashMap_Case1(b *testing.B) {
	b.StopTimer()
	wg := sync.WaitGroup{}
	for i := 0; i < b.N; i++ {
		M := hashmap.New[int, int]()
		b.StartTimer()
		for k := 0; k < iter0; k++ {
			wg.Add(1)
			go func(l, h int) {
				for j := l; j < h; j++ {
					M.Insert(j, j)
				}
				for j := l; j < h; j++ {
					_, a := M.Get(j)
					if !a {
						b.Error("key doesn't exist", j)
					}
				}
				for j := l; j < h; j++ {
					x, _ := M.Get(j)
					if x != j {
						b.Error("incorrect value", j, x)
					}
				}
				wg.Done()
			}(k*elementNum0, (k+1)*elementNum0)
		}
		wg.Wait()
		b.StopTimer()
	}
}

Code 2:

func BenchmarkHashMap_Case3(b *testing.B) {
	b.StopTimer()
	wg := &sync.WaitGroup{}
	for a := 0; a < b.N; a++ {
		M := hashmap.New[int, int]()
		b.StartTimer()
		for j := 0; j < iter0; j++ {
			wg.Add(1)
			go func(l, h int) {
				defer wg.Done()
				for i := l; i < h; i++ {
					M.Insert(i, i)
				}

				for i := l; i < h; i++ {
					_, x := M.Get(i)
					if !x {
						b.Errorf("not put: %v\n", O(i))
					}
				}
				for i := l; i < h; i++ {
					M.Del(i)

				}
				for i := l; i < h; i++ {
					_, x := M.Get(i)
					if x {
						b.Errorf("not removed: %v\n", O(i))
					}
				}

			}(j*elementNum0, (j+1)*elementNum0)
		}
		wg.Wait()
	
```	b.StopTimer()
	}

}
Set `elementNum0=1024; iter0=8`. You can remove the benchmark part and all those timing stuffs.

**Expected behavior**
What these 2 functions are doing is that each thread is performing operations(read/write/delete) on different set of keys. Since different threads aren't interfering with each other, so operations are performed sequentially with respect to each thread; therefore, no errors should occur. This is the behavior for sync.Map and a default map with RWMutex. However, errors occur for this implementation. 

**System (please complete the following information): AMD **
 - OS: win10 64 bit
 - Version / Commit: newest
 - Go 1.19.2

**Additional context**
I didn't thoroughly read the code of this hashmap, but I assume that this behavior is potentially caused by concurrent modifications during resizing?
I also have a case2 benchmark which involves using M.set(), but I don't know whether is M.set() really slow or performing unexpectedly, the benchmark usually results in a timeout. 
Thanks.

List.Delete stucks in infinite loop

List.Delete stucks in infinite loop:
The following is my test case:

package main
import (
"github.com/cornelk/hashmap"
)
func main() {
num := 128
map1 := hashmap.New(uintptr(num))
map1.Set("aa1", true)
map1.Set("aa2", true)
map1.Del("aa1")
}

//////////////////////////////////////////////////////////

But if I delete aa2 it work fine.
map1.Set("aa1", true)
map1.Set("aa2", true)
map1.Del("aa2")

//////////////////////////////////////////////////////////
2. And the following is also work fine.
map1.Set("a1", true)
map1.Set("a2", true)
map1.Del("a2")

Cas with nil old value

I am not sure if this is supposed to work or if there is something fundamentally wrong with it.
What I would want is a "set only once" cas where the I pass nil as the old value to ensure we set the new only if nothing is set.

Possible to break out the list implementation?

I often have need for a concurrent list. Is the one used in hashmap possible to breal out into a library?

invalid recursive type atomic.Pointer

Describe the bug
when I compile my project which indirectly depend this package
github.com\cornelk\[email protected]\list_element.go:17:13: invalid recursive type atomic.Pointer

System (please complete the following information):

OS: windows10
Version / Commit: GO1.19.4

Thank you

Cornelk,

Thank you for putting together this package. It appears to be fast and stable.

Very slow compared to map?

Describe the bug
Trying to benchmark hashmap

To Reproduce
compile and run
https://github.com/kokizzu/kokizzu-benchmark/blob/master/assoc/go-cornelkhashmap/hashmap.go
compared with original map
https://github.com/kokizzu/kokizzu-benchmark/blob/master/assoc/map.go
the diff
https://pastebin.com/diff/0uukeHdL

Expected behavior
works properly, not slow, it's running 2+ minutes and not done yet
while normal map only tok 12-14s

System (please complete the following information):

OS: PopOS/Ubuntu 22.10
Version / Commit: latest

Is Is Slow When Convert File To HashMap

//t.DataMap = &hashmap.HashMap{}
// Insert or Set cost long time when i read records from File To Hashmap when may app start
for _, item := range Records {
//t.DataMap.Set(item.K, item)
t.DataMap.Insert(item.K, item)

// i use pprof show than List.search cost most time
//by command:go tool pprof http://localhost:6060/debug/pprof/profile
// github.com/cornelk/hashmap.(*List).search (29.72s)
//list.go(line:49) left, found, right := l.search(searchStart, element)
//so how can i avoid search when my app start?

How about use as counter map ？

I use a map for recording api invoke count in high conccurrency QPS which key is api , value is uint64，what's the efficient way to use this hashmap to implements 'increase value atomiclly as value++' which actually don't need change unsafe.Pointer ?

I think that we should add extra handles in Delete call.

For example,List has items as {header,item1,item2,item3}.
When I want to delete item2 and item3 from List by asynchronous goroutines,as below.

[G2 ] go Delete(item2)
[G3 ] go Delete(item3)

If G2 got runtime and deleted item2 first,and then G3 executed CAS to delete item3.
The item3's left was item2 before G3 executed CAS .
While item2's next was not be nil,in which case the CAS in G3 will not return false but go on.
In this case,item2's next was be set to item3's next,but the right result should be that item1's next is item3's next.

I think the next of item should be set to nil every Delete.

Panic during BenchmarkReadHashMapWithWritesUint test

It seems to occur with low frequency but I managed to trigger it multiple times.

go.exe test -v github.com/cornelk/hashmap -bench ^BenchmarkReadHashMapWithWritesUint$ -run ^$

panic: runtime error: invalid memory address or nil pointer dereference

[signal 0xc0000005 code=0x0 addr=0x0 pc=0x50a758]

goroutine 9 [running]:

github.com/cornelk/hashmap.BenchmarkReadHashMapWithWritesUint.func2(0xc04208c020)

	.../Go/src/github.com/cornelk/hashmap/benchmark_test.go:124 +0x78

testing.(*B).RunParallel.func1(0xc042398070, 0xc042398068, 0xc042398060, 0xc0420b2160, 0xc042002260)

	C:/Go/src/testing/benchmark.go:605 +0xc9

created by testing.(*B).RunParallel

	C:/Go/src/testing/benchmark.go:606 +0x1b6
exit status 2
FAIL	github.com/cornelk/hashmap	0.242s

Tested on windows 10 x64.

panic: unsupported key type *foo

Apparently it is not currently possible to add a reference to a struct as a key in the hashmap. This is valid in the native map, sync.Map, etc.

In this example, i create an "Attribute" and "Value" struct, then try to create a map of key: *Attribute, value:*Value...
https://play.golang.org/p/m2RkogzD-82

Error returned is: panic: unsupported key type *main.Attribute

ထ

Hello.

"github.com/cornelk/hashmap"
)

func main() {
m := &hashmap.HashMap{}
t0 := time.Now()
for i := 1; i < 1000000; i++ {
m.Set(i, "abc")
}
fmt.Println(time.Now().Sub(t0))

infinity wait time

sync.Map nearly 1.1080342s
thank you

How to deal with hash conflicts.

Hi, I have a doubt. how to deal with same hashcode, different key. #24

	element.previousElement = unsafe.Pointer(left)
	element.nextElement = unsafe.Pointer(right)

	if !atomic.CompareAndSwapPointer(&left.nextElement, unsafe.Pointer(right), unsafe.Pointer(element)) {
	return false // item was modified concurrently
	}

	if right != nil {
	if !atomic.CompareAndSwapPointer(&right.previousElement, unsafe.Pointer(left), unsafe.Pointer(element)) {
	return false // item was modified concurrently
	}
	}
	}

cornelk / hashmap Goto Github PK

hashmap's Introduction

hashmap

Overview

Usage

Benchmarks

Technical details

hashmap's People

Contributors

Stargazers

Watchers

Forkers

hashmap's Issues

github.com/cornelk/hashmap

Recommend Projects

Recommend Topics

Recommend Org