initial hash map

2 files changed, 101 insertions, 0 deletions

diff --git a/search/hash.go b/search/hash.go
new file mode 100644
index 0000000..7611008
--- /dev/null
+++ b/search/hash.go
@@ -0,0 +1,88 @@
+package search
+
+type HashElem struct {
+	key  int
+	val  int
+	next *HashElem
+}
+
+type Hash struct {
+	root *HashElem
+	size int
+}
+
+func NewHash() *Hash {
+	return &Hash{}
+}
+
+func (h *Hash) Empty() bool {
+	return s.root == nil
+}
+
+func (h *Hash) Size() int {
+	return s.size
+}
+
+func (h *Hash) Put(key int, val int) {
+	if s.Empty() {
+		s.root = &HashElem{key, val, nil}
+		s.size++
+		return
+	}
+
+	elem := s.root
+
+	for {
+		if elem.key == key {
+			elem.val = val
+			return
+		}
+		if elem.next == nil {
+			elem.next = &HashElem{key, val, nil}
+			s.size++
+			return
+		}
+		elem = elem.next
+	}
+}
+
+func (h *Hash) Get(key int) (int, error) {
+	elem := s.root
+
+	for elem != nil {
+		if elem.key == key {
+			return elem.val, nil
+		}
+		elem = elem.next
+	}
+
+	return 0, NotFound
+}
+
+func (h *Hash) Del(key int) (int, error) {
+	if s.Empty() {
+		return 0, NotFound
+	}
+
+	if s.root.key == key {
+		defer func() {
+			s.root = s.root.next
+		}()
+		s.size--
+		return s.root.val, nil
+	}
+
+	elem := s.root
+	for elem.next != nil {
+		if elem.next.key == key {
+			defer func() {
+				elem.next = elem.next.next
+			}()
+			s.size--
+			return elem.next.val, nil
+		}
+		elem = elem.next
+	}
+
+	return 0, NotFound
+}
diff --git a/search/search_test.go b/search/search_test.go
index ec977cc..22f56d4 100644
--- a/search/search_test.go
+++ b/search/search_test.go
@@ -33,6 +33,12 @@ func TestRedBlackBST(t *testing.T) {
 	}
 }
 
+func TestHash(t *testing.T) {
+	for i := minLength; i <= maxLength; i *= factor {
+		test(NewHash(), i, t)
+	}
+}
+
 func TestGoMap(t *testing.T) {
 	for i := minLength; i <= maxLength; i *= factor {
 		test(NewGoMap(), i, t)
@@ -121,6 +127,13 @@ func BenchmarkRedBlackBST(t *testing.B) {
 	}
 }
 
+func BenchmarkHash(t *testing.B) {
+	s := NewHash()
+	for i := minLength; i <= maxLength; i *= factor {
+		benchmark(s, i, t)
+	}
+}
+
 func BenchmarkGoMap(t *testing.B) {
 	s := NewGoMap()
 	for i := minLength; i <= maxLength; i *= factor {