4 Hashing techniques
  
  
  4.1 The idea of hashing
  
  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 so-called "collision", that is, if
  more than one object with the same hash value has to be stored.
  
  The  basic  functions  to  work  with  hash  tables are NewHT (4.3-1), AddHT
  (4.3-2), and ValueHT (4.3-3). They are described in Section 4.3. In the next
  section, we first describe the infrastructure for hash functions.
  
  
  4.2 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:
  
  4.2-1 ChooseHashFunction
  
  > 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.
  
  4.2-2 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.
  
  4.2-3 ChooseHashFunction
  
  > 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.
  
  4.2-4 ChooseHashFunction
  
  > 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.
  
  4.2-5 ChooseHashFunction
  
  > 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.
  
  4.2-6 ChooseHashFunction
  
  > ChooseHashFunction( ob, len ) ______________________________________method
  Returns:  a record
  
  This method is for integers.
  
  4.2-7 ChooseHashFunction
  
  > ChooseHashFunction( ob, len ) ______________________________________method
  Returns:  a record
  
  This method is for permutations.
  
  4.2-8 ChooseHashFunction
  
  > ChooseHashFunction( ob, len ) ______________________________________method
  Returns:  a record
  
  This method is for lists of integers.
  
  4.2-9 ChooseHashFunction
  
  > ChooseHashFunction( ob, len ) ______________________________________method
  Returns:  a record
  
  This method is for kernel Pc words.
  
  4.2-10 ChooseHashFunction
  
  > ChooseHashFunction( ob, len ) ______________________________________method
  Returns:  a record
  
  This method is for lists of integers.
  
  4.2-11 ChooseHashFunction
  
  > ChooseHashFunction( ob, len ) ______________________________________method
  Returns:  a record
  
  This method is for lists of matrices.
  
  
  4.3 Using hash tables
  
  The following functions are needed to use hash tables. For details about the
  data structures see Section 4.4.
  
  4.3-1 NewHT
  
  > 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.3-2) and ValueHT (4.3-3). It will start with
  length len but will grow as necessary.
  
  4.3-2 AddHT
  
  > 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.4  for  details  on the data structures and especially about
  memory requirements.
  
  4.3-3 ValueHT
  
  > 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.3-1) tries to be too intelligent.
  
  4.3-4 InitHT
  
  > InitHT( len, hfun, eqfun ) _______________________________________function
  Returns:  a new hash table object
  
  This  is usually only an internal function. It is called from NewHT (4.3-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.
  
  4.3-5 GrowHT
  
  > 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. 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.
  
  
  4.4 The data structures for hash tables
  
  A hash table object is just a record with the following components:
  
  els
        A  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.
  
  vals
        A  GAP  list  storing  the  corresponding  values.  If a value is true
        nothing is stored here to save memory.
  
  len
        Length of the hash table.
  
  nr
        Number of elements stored in the hash table.
  
  hf
        The  hash function (value of the func component in the record returned
        by ChooseHashFunction (4.2-1)).
  
  hfd
        The  data  for  the second argument of the hash function (value of the
        data component in the record returned by ChooseHashFunction (4.2-1)).
  
  eqf
        A  comparison  function  taking  two  arguments and returning true for
        equality or false otherwise.
  
  collisions
        Number of collisions (see below).
  
  accesses
        Number of lookup or store accesses to the hash.
  
  cangrow
        A  boolean value indicating whether the hash can grow automatically or
        not.
  
  ishash
        Is true to indicate that this is a hash table record.
  
  
  4.4-1 Memory requirements
  
  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.
  
  
  4.4-2 Handling of collisions
  
  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.
  
  
  4.4-3 Efficiency
  
  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.