README
¶
This package provides implementations for symbol table data structures.
| Symbol Table | Ordered | Self-Balancing | Description |
|---|---|---|---|
| ChainHashTable | No | N/A | Separate Chaining Hash Table |
| LinearHashTable | No | N/A | Linear Probing Hash Table |
| QuadraticHashTable | No | N/A | Quadratic Probing Hash Table |
| DoubleHashTable | No | N/A | Double Hashing Hash Table |
| BST | Yes | No | Binary Search Tree |
| AVL | Yes | Yes | AVL Binary Search Tree |
| RedBlack | Yes | Yes | Left-Leaning Red-Black Binary Search Tree |
Documentation
¶
Overview ¶
Package symboltable implements symbol table data structures.
Symbol tables are also known as maps, dictionaries, etc. Symbol tables can be ordered or unordered.
Index ¶
- type HashOpts
- type OrderedSymbolTable
- type SymbolTable
- func NewChainHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
- func NewDoubleHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
- func NewLinearHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
- func NewQuadraticHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HashOpts ¶
type HashOpts struct {
// The initial capacity of the hash table (must be a power of 2 for efficient hashing).
InitialCap int
// The minimum load factor before resizing (shrinking) the hash table.
MinLoadFactor float32
// The maximum load factor before resizing (expanding) the hash table.
MaxLoadFactor float32
}
HashOpts represents configuration options for a hash table.
type OrderedSymbolTable ¶
type OrderedSymbolTable[K, V any] interface { SymbolTable[K, V] Tree2[K, V] Height() int Min() (K, V, bool) Max() (K, V, bool) Floor(K) (K, V, bool) Ceiling(K) (K, V, bool) DeleteMin() (K, V, bool) DeleteMax() (K, V, bool) Select(int) (K, V, bool) Rank(K) int Range(K, K) []KeyValue[K, V] RangeSize(K, K) int }
OrderedSymbolTable represents an ordered symbol table abstract data type.
func NewAVL ¶
func NewAVL[K, V any](cmpKey CompareFunc[K], eqVal EqualFunc[V]) OrderedSymbolTable[K, V]
NewAVL creates a new AVL tree.
AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the left and right subtrees of any node differ by at most 1.
The second parameter (eqVal) is needed only if you want to use the Equal method.
func NewBST ¶
func NewBST[K, V any](cmpKey CompareFunc[K], eqVal EqualFunc[V]) OrderedSymbolTable[K, V]
NewBST creates a new binary search tree.
A binary search tree (BST) is a binary tree in symmetric order. Every node's key is:
Larger than all keys in its left sub-tree. Smaller than all keys in its right sub-tree.
The second parameter (eqVal) is needed only if you want to use the Equal method.
func NewRedBlack ¶
func NewRedBlack[K, V any](cmpKey CompareFunc[K], eqVal EqualFunc[V]) OrderedSymbolTable[K, V]
NewRedBlack creates a new Red-Black tree.
A Red-Black tree is 2-3 Tree represented as a binary search tree. In a left-leaning Red-Black tree, left-leaning red links are used to construct 3-nodes. A left-leaning Red-Black tree is a BST such that:
Red links lean left. No node has two red links connect to it. Every path from root to null link has the same number of black links.
The second parameter (eqVal) is needed only if you want to use the Equal method.
type SymbolTable ¶
type SymbolTable[K, V any] interface { fmt.Stringer Equaler[SymbolTable[K, V]] Collection2[K, V] // contains filtered or unexported methods }
SymbolTable represents an unordered symbol table abstract data type.
func NewChainHashTable ¶
func NewChainHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
NewChainHashTable creates a new hash table with separate chaining for conflict resolution.
A hash table is an unordered symbol table providing efficient insertion, deletion, and lookup operations. It resolves hash collisions, where multiple keys hash to the same bucket, by maintaining a linked list of all key-values that hash to the same bucket. Each bucket contains a chain of elements.
func NewDoubleHashTable ¶
func NewDoubleHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
NewDoubleHashTable creates a new hash table with double hashing for conflict resolution.
A hash table is an unordered symbol table providing efficient insertion, deletion, and lookup operations. This hash table implements open addressing with double hashing, where collisions are resolved by applying a second hash function to determine the step size for probing. The indices are computed as h₁, h₁ + h₂, h₁ + 2h₂, h₁ + 3h₂, ..., where h₁ is the primary hash and h₂ is the secondary hash.
func NewLinearHashTable ¶
func NewLinearHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
NewLinearHashTable creates a new hash table with linear probing for conflict resolution.
A hash table is an unordered symbol table providing efficient insertion, deletion, and lookup operations. This hash table implements open addressing with linear probing, where collisions are resolved by checking subsequent indices in a linear fashion (i+1, i+2, i+3, ...) until an empty slot is found.
func NewQuadraticHashTable ¶
func NewQuadraticHashTable[K, V any](hashKey HashFunc[K], eqKey EqualFunc[K], eqVal EqualFunc[V], opts HashOpts) SymbolTable[K, V]
NewQuadraticHashTable creates a new hash table with quadratic probing for conflict resolution.
A hash table is an unordered symbol table providing efficient insertion, deletion, and lookup operations. This hash table implements open addressing with quadratic probing, where collisions are resolved by checking subsequent indices using a quadratic function (i+1², i+2², i+3², ...) until an empty slot is found.
Source Files