p0705_design_hash_set

package

v0.0.0-...-ca37d48 Latest Latest Go to latest Published: Jun 10, 2023 License: BSD-2-Clause Imports: 1 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/daominah/leetcode

Documentation ¶

Index ¶

Constants
func Div(key int, NSlots int) int
func DivisionHash(s string, nSlot int) int
type KeyValue
type MyHashSet
- func Constructor() MyHashSet
type MyMap
- func NewMyMap() *MyMap

Constants ¶

View Source

const NSlot = 10000019 // number of slots for hashing, should be a prime number

Variables ¶

This section is empty.

Functions ¶

func Div ¶

func Div(key int, NSlots int) int

func DivisionHash ¶

func DivisionHash(s string, nSlot int) int

A good hash func satisfies each key is equally likely to hash to any of the slots This func take a string as a represent of a radix-128 integer, return remainder when the string is divided by number of slots

Types ¶

type KeyValue ¶

type KeyValue struct {
	Key   string
	Value interface{}
}

type MyHashSet ¶

type MyHashSet struct {
	// contains filtered or unexported fields
}

func Constructor ¶

func Constructor() MyHashSet

func (*MyHashSet) Add ¶

func (m *MyHashSet) Add(key int)

worst case time of hashing with chaining is O(n), when all n keys hash to the same list, creating a list of length n average case time O(1+n/NSlots). Reference "Introduction to Algorithms", chap 11 Hash Tables

func (*MyHashSet) Contains ¶

func (m *MyHashSet) Contains(key int) bool

func (*MyHashSet) Remove ¶

func (m *MyHashSet) Remove(key int)

type MyMap ¶

type MyMap struct {
	Table []*list.List // 1 hash slot is a linked list
	Len   int
}

MyMap implements map data structure, key data type is string, (average time to insert , search , delete is O(1)) using division method as hash function and resolve collision by chaining

func NewMyMap ¶

func NewMyMap() *MyMap

func (*MyMap) Add ¶

func (m *MyMap) Add(key string, value interface{})

worst case time of hashing with chaining is O(n), when all n keys hash to the same list, creating a list of length n average case time O(1+n/nSlot). Reference "Introduction to Algorithms", chap 11 Hash Tables

func (*MyMap) Remove ¶

func (m *MyMap) Remove(key string)

func (*MyMap) Search ¶

func (m *MyMap) Search(key string) interface{}

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL