src.pydasa.structs.tables.scht ============================== .. py:module:: src.pydasa.structs.tables.scht .. autoapi-nested-parse:: Module scht.py =========================================== Module to represent the **SCHashTable** data structure for the **Hash Table** in *PyDASA*. Classes: **Bucket**: Represents a bucket in the hash table using a single linked list. **SCHashTable**: Implements a hash table with separate chaining for collision resolution, supporting dynamic resizing and customizable comparison functions. *IMPORTANT:* based on the implementations proposed by the following authors/books: # . Algorithms, 4th Edition, Robert Sedgewick and Kevin Wayne. # . Data Structure and Algorithms in Python, M.T. Goodrich, R. Tamassia, M.H. Goldwasser. Attributes ---------- .. autoapisummary:: src.pydasa.structs.tables.scht.DFLT_SC_ALPHA src.pydasa.structs.tables.scht.MAX_SC_ALPHA src.pydasa.structs.tables.scht.MIN_SC_ALPHA Classes ------- .. autoapisummary:: src.pydasa.structs.tables.scht.Bucket src.pydasa.structs.tables.scht.SCHashTable Module Contents --------------- .. py:data:: DFLT_SC_ALPHA :type: float :value: 4.0 Default load factor (*alpha*) for the *SCHashTable*, by default is 4.0. .. py:data:: MAX_SC_ALPHA :type: float :value: 8.0 Maximum load factor (*alpha*) for the *SCHashTable*, by default is 8.0. .. py:data:: MIN_SC_ALPHA :type: float :value: 2.0 Minimum load factor (*alpha*) for the *SCHashTable*, by default is 2.0. .. py:class:: Bucket Bases: :py:obj:`Generic`\ [\ :py:obj:`pydasa.structs.types.generics.T`\ ], :py:obj:`pydasa.structs.lists.sllt.SingleLinkedList`\ [\ :py:obj:`pydasa.structs.tables.htme.MapEntry`\ [\ :py:obj:`pydasa.structs.types.generics.T`\ ]\ ] **Bucket** class to represent a bucket in the **Hash Table** with the *Separate Chaining* method. The structure is based (inherits) on a custom singly linked list (*SingleLinkedList*) for *PyDASA*. :param SingleLinkedList: *PyDASA* custom class for a single linked list. :type SingleLinkedList: dataclass :param Generic: Generic type for a Python data structure. :type Generic: T .. py:method:: __str__() *__str__()* function to return a string representation of the *Bucket*. It also extends the *Node* class. :returns: string representation of the *Bucket*. :rtype: str .. py:method:: __repr__() *__repr__()* function to return a string representation of the *Bucket*. It also extends the *Node* class. :returns: string representation of the *Bucket*. :rtype: str .. py:class:: SCHashTable Bases: :py:obj:`Generic`\ [\ :py:obj:`pydasa.structs.types.generics.T`\ ] Abstract base class for generic types. A generic type is typically declared by inheriting from this class parameterized with one or more type variables. For example, a generic mapping type might be defined as:: class Mapping(Generic[KT, VT]): def __getitem__(self, key: KT) -> VT: ... # Etc. This class can then be used as follows:: def lookup_name(mapping: Mapping[KT, VT], key: KT, default: VT) -> VT: try: return mapping[key] except KeyError: return default .. py:attribute:: rehashable :type: bool :value: True Boolean to indicate if the hash table can be rehashed. By default is True. .. py:attribute:: nentries :type: int :value: 1 Inicial number of entries (n) for the hash table. By default is 1, but should be set according to the number of entries expected to be stored. NOTE: the reserved space (n) is NOT the capacity (M) of the hash table. .. py:attribute:: mcapacity :type: int :value: 1 The capacity (M) of the hash table. By default is 1, but should be set according to the number of entries expected to be stored. .. py:attribute:: alpha :type: Optional[float] :value: 4.0 Load factor (*alpha*) for the hash table. By default is 4.0. NOTE: alpha = n/M (n: number of expected entries, M: capacity of the hash table). .. py:attribute:: cmp_function :type: Optional[Callable[[Any, pydasa.structs.tables.htme.MapEntry[pydasa.structs.types.generics.T]], int]] :value: None Customizable comparison function for *SCHashTable* and its *MapEntry* objects. Defaults to *dflt_cmp_function_ht()* from *PyDASA*, but can be overridden by the user. .. py:attribute:: hash_table :type: Optional[pydasa.structs.lists.arlt.ArrayList[Bucket[pydasa.structs.types.generics.T]]] :value: None Index of the hash table where the *Buckets* are stored. By default is an empty *ArrayList* initialized with the configured capacity (M). .. py:attribute:: key :type: Optional[str] :value: '_idx' Customizable key name for identifying elements in the *SCHashTable*. Defaults to *DFLT_DICT_KEY = '_id'* from *PyDASA*, but can be overridden by the user. .. py:attribute:: prime :type: int :value: 109345121 Prime number (P) for the MAD compression function. By default is 109345121, but can be overridden by the user. NOTE: the MAD compression function is: *h(k) = ((a*k + b) mod P) mod M*, where *a* and *b* are two random integers, *P* is a prime number and *M* is the hash table capacity. .. py:attribute:: min_alpha :type: float :value: 2.0 Minimum load factor (*alpha*) for the hash table. By default is 2.0. But can be overridden by the user. .. py:attribute:: max_alpha :type: float :value: 8.0 Maximum load factor (*alpha*) for the hash table. By default is 8.0. But can be overridden by the user. .. py:attribute:: iodata :type: Optional[List[pydasa.structs.types.generics.T]] :value: None Optional Python list for loading external data intho the *SCHashTable*. Defaults to *None* but can be provided during creation. .. py:method:: __post_init__() *__post_init__()* Initializes the *SCHashTable* after creation by setting attributes like *rehashable*, *mcapacity*, *alpha*, *cmp_function*, *key*, *prime*, *scale*, *shift*, and *iodata*. It also sets the default values for the *min_alpha* and *max_alpha* attributes, which are used to control the load factor of the hash table. *NOTE:* Special method called automatically after object creation. .. py:method:: default_compare(key1, entry2) *default_compare()* Default comparison function for the *SCHashTable* and its *MapEntry* objects. Compares the key of the *MapEntry* with the provided key *key1* and reurns: - 0 if they are equal. - 1 if the *MapEntry* key is less than *key1*. - -1 if the *MapEntry* key is greater than *key1*. :param key1: Key from the first *MapEntry* to compare. :type key1: Hashable :param entry2: Second *MapEntry* to compare. :type entry2: MapEntry :returns: Comparison result. :rtype: int .. py:property:: size :type: int *size* Property to retrieve the number if entries (n) in the *SCHashTable*. :returns: Number of entries (n) in the *SCHashTable*. :rtype: int .. py:property:: empty :type: bool *empty* Property to check if the *SCHashTable* has entries or not. :returns: True if the *SCHashTable* is empty, False otherwise. :rtype: bool .. py:property:: collisions :type: int *collisions* Property to retrieve the number of collisions in the *SCHashTable*. :returns: Number of collisions in the *SCHashTable*. :rtype: int .. py:method:: clear() *clear()* function to reset the *SCHashTable* to its initial state. It clears all the entries in the hash table and resets the size, collisions and current load factor. .. py:method:: insert(key, value) *insert()* adds a new entry to the *SCHashTable*. It creates a new *MapEntry* object with the key-value pair. :param key: key for the entry. :type key: T :param value: value for the entry. :type value: T .. py:method:: get_entry(key) *get_entry()* retrieves an entry from the *SCHashTable* using the provided key. :param key: key for the entry. :type key: T :raises IndexError: error if the *SCHashTable* is empty. :returns: *MapEntry* object with the key-value pair if found, None otherwise. :rtype: Optional[MapEntry] .. py:method:: get_bucket(key) *get_bucket()* retrieves the bucket containing the key-value pair from the *SCHashTable* using the provided key. :param key: key for the entry. :type key: T :raises IndexError: error if the *SCHashTable* is empty. :returns: *Bucket* object containing the key-value pair if found, None otherwise. :rtype: Optional[Bucket] .. py:method:: is_present(key) *is_present()* checks if the provided key is present in the *SCHashTable*. :param key: key for the entry. :type key: T :raises IndexError: error if the *SCHashTable* is empty. :returns: True if the key is present in the *SCHashTable*, False otherwise. :rtype: bool .. py:method:: delete(key) *delete()* removes an entry from the *SCHashTable* using the provided key. :param key: key for the entry. :type key: T :raises IndexError: error if the *SCHashTable* is empty. :returns: *MapEntry* object with the key-value pair if found, None otherwise. :rtype: Optional[MapEntry] .. py:method:: keys() *keys()* returns a single linked list of keys from the *SCHashTable*. :returns: list of keys from the *SCHashTable*. e.g. [key1, key2, ...]. :rtype: SingleLinkedList[T] .. py:method:: values() *values()* returns a single linked list of values from the *SCHashTable*. :returns: list of values from the *SCHashTable*. e.g. [value1, value2, ...]. :rtype: SingleLinkedList[T] .. py:method:: entries() *entries()* returns a list of tuples with the key and value of each entry in the hash table. :returns: list of tuples with the key-value pair of each entry in the hash table. e.g. [(key1, value1), (key2, value2), ...]. :rtype: SingleLinkedList[T] .. py:method:: resize() *resize()* rehashes the *SCHashTable* by creating a new hash table with a new capacity (M) and rehashing all the entries from the old hash table to the new one. It also updates the size, collisions and current load factor. .. py:method:: __len__() *__len__()* function to return the number of entries (n) in the *SCHashTable*. :returns: Number of entries (n) in the *SCHashTable*. :rtype: int .. py:method:: __str__() *__str__()* function to return a string representation of the *SCHashTable*. :returns: string representation of the *SCHashTable*. :rtype: str .. py:method:: __repr__() *__repr__()* function to return a string representation of the *SCHashTable*. :returns: string representation of the *SCHashTable*. :rtype: str