90 lines
1.7 KiB
Go
90 lines
1.7 KiB
Go
package main
|
|
|
|
const ArraySize2 = 7
|
|
|
|
// HashTable structure
|
|
type HashTable2 struct {
|
|
array [ArraySize2]*bucket2
|
|
}
|
|
|
|
// bucket structure
|
|
type bucket2 struct {
|
|
key string
|
|
value int
|
|
next *bucket2
|
|
}
|
|
|
|
// Insert will take in a key and will add the item to the hash table array.
|
|
func (h *HashTable2) Insert(key string, value int) {
|
|
index := hash(key)
|
|
h.array[index].insert(key, value)
|
|
}
|
|
|
|
// Search will take in a key and RETURN true if that key is stored in the hash table.
|
|
func (h *HashTable2) Search(key string) bool {
|
|
index := hash(key)
|
|
return h.array[index].search(key)
|
|
}
|
|
|
|
// Delete will take in a key and DELETE it from the hash table.
|
|
func (h *HashTable2) Delete(key string) {
|
|
index := hash(key)
|
|
h.array[index].delete(key)
|
|
}
|
|
|
|
// insert will take in a key and add it to the bucket.
|
|
func (b *bucket2) insert(k string, v int) {
|
|
if b.search(k) {
|
|
b.value = v
|
|
} else {
|
|
newBucket := &bucket2{k, v, nil}
|
|
newBucket.next = b
|
|
*b = *newBucket
|
|
}
|
|
}
|
|
|
|
// search will take in a key and return true if it's in the bucket.
|
|
func (b *bucket2) search(k string) bool {
|
|
if b == nil {
|
|
return false
|
|
}
|
|
if b.key == k {
|
|
return true
|
|
}
|
|
|
|
return b.next.search(k)
|
|
}
|
|
|
|
// delete will take in a key and delete the corresponding node in the bucket.
|
|
func (b *bucket2) delete(k string) {
|
|
if b.key == k {
|
|
b = b.next
|
|
return
|
|
}
|
|
prevB := b
|
|
for b != nil && b.key != k {
|
|
prevB = b
|
|
b = b.next
|
|
}
|
|
if b != nil {
|
|
prevB.next = b.next
|
|
}
|
|
}
|
|
|
|
// hash is the basic hashing function.
|
|
func hash2(key string) int {
|
|
sum := 0
|
|
for _, v := range key {
|
|
sum += int(v)
|
|
}
|
|
return sum % ArraySize2
|
|
}
|
|
|
|
func Init() *HashTable2 {
|
|
result := &HashTable2{}
|
|
for i := range result.array {
|
|
result.array[i] = &bucket2{}
|
|
}
|
|
return result
|
|
}
|