If one wants to store a certain set of similar objects and wants to quickly access a given one (or come back with the result that it is unknown), the first idea would be to store them in a list, possibly sorted for faster access. This however still would need \(\log(n)\) comparisons to find a given element or to decide that it is not yet stored.
Therefore one uses a much bigger array and uses a function on the space of possible objects with integer values to decide, where in the array to store a certain object. If this so called hash function distributes the actually stored objects well enough over the array, the access time is constant in average. Of course, a hash function will usually not be injective, so one needs a strategy what to do in case of a so-called collision
, that is, if more than one object with the same hash value has to be stored. This package provides two ways to deal with collisions, one is implemented in the so called HashTabs
and another in the TreeHashTabs
. The former simply uses other parts of the array to store the data involved in the collisions and the latter uses an AVL tree (see Chapter 8) to store all data objects with the same hash value. Both are used basically in the same way but sometimes behave a bit differently.
The basic functions to work with hash tables are HTCreate (4.3-1), HTAdd (4.3-2), HTValue (4.3-3), HTDelete (4.3-5) and HTUpdate (4.3-4). They are described in Section 4.3.
The legacy functions from older versions of this package to work with hash tables are NewHT (4.4-1), AddHT (4.4-2), and ValueHT (4.4-3). They are described in Section 4.4. In the next section, we first describe the infrastructure for hash functions.
In the orb package hash functions are chosen automatically by giving a sample object together with the length of the hash table. This is done with the following operation:
‣ ChooseHashFunction( ob, len ) | ( operation ) |
Returns: a record
The first argument ob must be a sample object, that is, an object like those we want to store in the hash table later on. The argument len is an integer that gives the length of the hash table. Note that this might be called later on automatically, when a hash table is increased in size. The operation returns a record with two components. The component func is a GAP function taking two arguments, see below. The component data is some GAP object. Later on, the hash function will be called with two arguments, the first is the object for which it should call the hash value and the second argument must be the data stored in the data component.
The hash function has to return values between \(1\) and the hash length len inclusively.
This setup is chosen such that the hash functions can be global objects that are not created during the execution of ChooseHashFunction but still can change their behaviour depending on the data.
In the following we just document, for which types of objects there are hash functions that can be found using ChooseHashFunction.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for compressed vectors over the field GF(2) of two elements. Note that there is no hash function for non-compressed vectors over GF(2) because those objects cannot efficiently be recognised from their type.
Note that you can only use the resulting hash functions for vectors of the same length.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for compressed vectors over a finite field with up to \(256\) elements. Note that there is no hash function for non-compressed such vectors because those objects cannot efficiently be recognised from their type.
Note that you can only use the resulting hash functions for vectors of the same length.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for compressed matrices over the field GF(2) of two elements. Note that there is no hash function for non-compressed matrices over GF(2) because those objects cannot efficiently be recognised from their type.
Note that you can only use the resulting hash functions for matrices of the same size.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for compressed matrices over a finite field with up to \(256\) elements. Note that there is no hash function for non-compressed such vectors because those objects cannot efficiently be recognised from their type.
Note that you can only use the resulting hash functions for matrices of the same size.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for integers.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for permutations.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for lists of integers.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for kernel Pc words.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for lists of integers.
‣ ChooseHashFunction( ob, len ) | ( method ) |
Returns: a record
This method is for lists of matrices.
‣ HTCreate( sample[, opt] ) | ( operation ) |
Returns: a new hash table object
A new hash table for objects like sample is created. The second argument opt is an optional options record, which will supplied in most cases, if only to specify the length and type of the hash table to be used. The following components in this record can be bound:
treehashsizeIf this component is bound the type of the hash table is a TreeHashTab. The value must be a positive integer and will be the size of the hash table. Note that for this type of hash table the keys to be stored in the hash must be comparable using \(<\). A three-way comparison function can be supplied using the component cmpfunc (see below).
treehashtabIf this component is bound the type of the hash table is a TreeHashTab. This option is superfluous if treehashsize is used.
forflatplainlistsIf this component is set to true then the user guarantees that all the elements in the hash will be flat plain lists, that is, plain lists with no subobjects. For example lists of immediate integers will fulfill this requirement, but ranges don't. In this case, a particularly good and efficient hash function will automatically be taken and the components hashfunc, hfbig and hfdbig are ignored. Note that this cannot be automatically detected because it depends not only on the sample point but also potentially on all the other points to be stored in the hash table.
hf and hfdIf these components are bound, they are used as the hash function. The value of hf must be a function taking two arguments, the first being the object for which the hash function shall be computed and the second being the value of hfd. The returned value must be an integer in the range from \(1\) to the length of the hash. If either of these components is not bound, an automatic choice for the hash function is done using ChooseHashFunction (4.2-1) and the supplied sample object sample.
Note that if you specify these two components and are using a HashTab table then this table cannot grow unless you also bind the components hfbig, hfdbig and cangrow.
cmpfuncThis component can be bound to a three-way comparison function taking two arguments a and b (which will be keys for the TreeHashTab) and returns \(-1\) if \(\textit{a}<\textit{b}\), \(0\) if \(\textit{a} = \textit{b}\) and \(1\) if \(\textit{a} > \textit{b}\). If this component is not bound the function AVLCmp (8.2-2) is taken, which simply calls the generic operations < and = to do the job.
hashlenIf this component is bound the type of the hash table is a standard HashTab table. That is, collisions are dealt with by storing additional entries in other slots. This is the traditional way to implement a hash table. Note that currently deleting entries in such a hash table is not implemented, since it could only be done by leaving a deleted
mark which could pollute that hash table. Use TreeHashTabs instead if you need deletion. The value bound to hashlen must be a positive integer and will be the initial length of the hash table.
Note that it is a good idea to choose a prime number as the hash length due to the algorithm for collision handling which works particularly well in that case. The hash function is chosen automatically.
hashtabIf this component is bound the type of the hash table is a standard HashTab table. This component is superfluous if hashlen is bound.
eqfFor HashTab tables the function taking two arguments bound to this component is used to compare keys in the hash table. If this component is not bound the usual = operation is taken.
hfbig and hfdbig and cangrowIf you have used the components hf and hfd then your hash table cannot automatically grow when it fills up. This is because the length of the table is built into the hash function. If you still want your hash table to be able to grow automatically, then bind a hash function returning arbitrary integers to hfbig, the corresponding data for the second argument to hfdbig and bind cangrow to true. Then the hash table will automatically grow and take this new hash function modulo the new length of the hash table as hash function.
‣ HTAdd( ht, key, value ) | ( operation ) |
Returns: a hash value
Stores the object key into the hash table ht and stores the value val together with ob. The result is fail if an error occurred, which can be that an object equal to key is already stored in the hash table or that the hash table is already full. The latter can only happen, if the hash table is no TreeHashTab and cannot grow automatically.
If no error occurs, the result is an integer indicating the place in the hash table where the object is stored. Note that once the hash table grows automatically this number is no longer the same!
If the value val is true for all objects in the hash, no extra memory is used for the values. All other values are stored in the hash. The value fail cannot be stored as it indicates that the object is not found in the hash.
See Section 4.5 for details on the data structures and especially about memory requirements.
‣ HTValue( ht, key ) | ( operation ) |
Returns: fail or true or a value
Looks up the object key in the hash table ht. If the object is not found, fail is returned. Otherwise, the value stored with the object is returned. Note that if this value was true no extra memory is used for this.
‣ HTUpdate( ht, key, value ) | ( operation ) |
Returns: fail or true or a value
The object key must already be stored in the hash table ht, otherwise this operation returns fail. The value stored with key in the hash is replaced by value and the previously stored value is returned.
‣ HTDelete( ht, key ) | ( operation ) |
Returns: fail or true or a value
The object key along with its stored value is removed from the hash table ht. Note that this currently only works for TreeHashTabs and not for HashTab tables. It is an error if key is not found in the hash table and fail is returned in this case.
‣ HTGrow( ht, ob ) | ( function ) |
Returns: nothing
This is a more or less internal operation. It is called when the space in a hash table becomes scarce. The first argument ht must be a hash table object, the second a sample point. The function increases the hash size by a factor of 2. This makes it necessary to choose a new hash function. Usually this is done with the usual ChooseHashFunction method. However, one can bind the two components hfbig and hfdbig in the options record of HTCreate (4.3-1) to a function and a record respectively and bind cangrow to true. In that case, upon growing the hash, a new hash function is created by taking the function hfbig together with hfdbig as second data argument and reducing the resulting integer modulo the hash length. In this way one can specify a hash function suitable for all hash sizes by simply producing big enough hash values.
Note that the functions described in this section are obsolete since version 3.0 of orb and are only kept for backward compatibility. Please use the functions in Section 4.3 in new code.
The following functions are needed to use hash tables. For details about the data structures see Section 4.5.
‣ NewHT( sample, len ) | ( function ) |
Returns: a new hash table object
A new hash table for objects like sample of length len is created. Note that it is a good idea to choose a prime number as the hash length due to the algorithm for collision handling which works particularly well in that case. The hash function is chosen automatically. The resulting object can be used with the functions AddHT (4.4-2) and ValueHT (4.4-3). It will start with length len but will grow as necessary.
‣ AddHT( ht, ob, val ) | ( function ) |
Returns: an integer or fail
Stores the object ob into the hash table ht and stores the value val together with ob. The result is fail if an error occurred, which can only be that the hash table is already full. This can only happen, if the hash table cannot grow automatically.
If no error occurs, the result is an integer indicating the place in the hash table where the object is stored. Note that once the hash table grows automatically this number is no longer the same!
If the value val is true for all objects in the hash, no extra memory is used for the values. All other values are stored in the hash. The value fail cannot be stored as it indicates that the object is not found in the hash.
See Section 4.5 for details on the data structures and especially about memory requirements.
‣ ValueHT( ht, ob ) | ( function ) |
Returns: the stored value, true, or fail
Looks up the object ob in the hash table ht. If the object is not found, fail is returned. Otherwise, the value stored with the object is returned. Note that if this value was true no extra memory is used for this.
The following function is only documented for the sake of completeness and for emergency situations, where NewHT (4.4-1) tries to be too intelligent.
‣ InitHT( len, hfun, eqfun ) | ( function ) |
Returns: a new hash table object
This is usually only an internal function. It is called from NewHT (4.4-1). The argument len is the length of the hash table, hfun is the hash function record as returned by ChooseHashFunction (4.2-1) and eqfun is a comparison function taking two arguments and returning true or false.
Note that automatic growing is switched on for the new hash table which means that if the hash table grows, a new hash function is chosen using ChooseHashFunction (4.2-1). If you do not want this, change the component cangrow to false after creating the hash table.
‣ GrowHT( ht, ob ) | ( function ) |
Returns: nothing
This is a more or less internal function. It is called when the space in a hash table becomes scarce. The first argument ht must be a hash table object, the second a sample point. The function increases the hash size by a factor of 2 for hash tables and 20 for tree hash tables. This makes it necessary to choose a new hash function. Usually this is done with the usual ChooseHashFunction method. However, one can assign the two components hfbig and hfdbig to a function and a record respectively. In that case, upon growing the hash, a new hash function is created by taking the function hfbig together with hfdbig as second data argument and reducing the resulting integer modulo the hash length. In this way one can specify a hash function suitable for all hash sizes by simply producing big enough hash values.
A legacy hash table object is just a record with the following components:
elsA GAP list storing the elements. Its length can be as long as the component len indicates but will only grow as necessary when elements are stored in the hash.
valsA GAP list storing the corresponding values. If a value is true nothing is stored here to save memory.
lenLength of the hash table.
nrNumber of elements stored in the hash table.
hfThe hash function (value of the func component in the record returned by ChooseHashFunction (4.2-1)).
hfdThe data for the second argument of the hash function (value of the data component in the record returned by ChooseHashFunction (4.2-1)).
eqfA comparison function taking two arguments and returning true for equality or false otherwise.
collisionsNumber of collisions (see below).
accessesNumber of lookup or store accesses to the hash.
cangrowA boolean value indicating whether the hash can grow automatically or not.
ishashIs true to indicate that this is a hash table record.
hfbig and hfdbigUsed for hash tables which need to be able to grow but where the user supplied the hash function. See Section HTCreate (4.3-1) for more details.
A new style HashTab objects are component objects with the same components except that there is no component ishash since these objects are recognised by their type.
A TreeHashTab is very similar. It is a positional object with basically the same components, except that eqf is replaced by the three-way comparison function cmpfunc. Since TreeHashTabs do not grow, the components hfbig, hfdbig and cangrow are never bound. Each slot in the els component is either unbound (empty), or bound to the only key stored in the hash which has this hash value or, if there is more than one key for that hash value, the slot is bound to an AVL tree containing all such keys (and values).
Due to the data structure defined above the hash table will need one machine word (\(4\) bytes on 32bit machines and \(8\) bytes on 64bit machines) per possible entry in the hash if all values corresponding to objects in the hash are true and two machine words otherwise. This means that the memory requirement for the hash itself is proportional to the hash table length and not to the number of objects actually stored in the hash!
In addition one of course needs the memory to store the objects themselves.
For TreeHashTabs there are additional memory requirements. As soon as there are more than one key hashing to the same value, the memory for an AVL tree object is needed in addition. An AVL tree objects needs about 10 machine words for the tree object and then another 4 machine words for each entry stored in the tree. Note that for many collisions this can be significantly more than for HashTab tables. However, the advantage of TreeHashTabs is that even for a bad hash function the performance is never worse than \(log(n)\) for each operation where \(n\) is the number of keys in the hash with the same hash value.
This section is only relevant for HashTab objects.
If two or more objects have the same hash value, the following is done: If the hash value is coprime to the hash length, the hash value is taken as the increment
, otherwise \(1\) is taken. The code to find the proper place for an object just repeatedly adds the increment to the current position modulo the hash length. Due to the choice of the increment this will eventually try all places in the hash table. Every such increment step is counted as a collision in the collisions component in the hash table. This algorithm explains why it is sensible to choose a prime number as the length of a hash table.
Hashing is efficient as long as there are not too many collisions. It is not a problem if the number of collisions (counted in the collisions component) is smaller than the number of accesses (counted in the accesses component).
A high number of collisions can be caused by a bad hash function, because the hash table is too small (do not fill a hash table to more than about 80%), or because the objects to store are just not well enough distributed. Hash tables will grow automatically if too many collisions are detected or if they are filled to 80%.
The advantage of TreeHashTabs is that even for a bad hash function the performance is never worse than \(log(n)\) for each operation where \(n\) is the number of keys in the hash with the same hash value. However, they need a bit more memory.
generated by GAPDoc2HTML