Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

### 6 Hash Functions

#### 6.1 Introduction

A hash function in datastructures is a function $$H$$ which maps a value $$X$$ to a small integer (where a small integer is an integer in the range [-2^28..2^28-1] on a 32-bit system, and [-2^60..2^60-1] on a 64-bit system), under the requirement that if $$X=Y$$, then $$H(X)=H(Y)$$.

A variety of hash functions is provided by datastructures, with different behaviours. A bad choice of hash function can lead to serious performance problems.

datastructures does not guarantee consistency of hash values across release or GAP sessions.

#### 6.2 Hash Functions for Basic Types

##### 6.2-1 HashBasic
 ‣ HashBasic( obj... ) ( function )

Returns: a small integer

Hashes any values built inductively from

• built-in types, namely integers, booleans, permutations, transformations, partial permutations, and

• constructors for lists and records.

This function is variadic, treating more than one argument as equivalent to a list containing the arguments, that is HashBasic(x,y,z) = HashBasic([x,y,z]).

#### 6.3 Hash Functions for Permutation Groups

datastructures provides two hash functions for permutation groups; Hash_PermGroup_Fast (6.3-1) is the faster one, with higher likelihood of collisions and Hash_PermGroup_Complete (6.3-2) is slower but provides a lower likelihood of collisions.

##### 6.3-1 Hash_PermGroup_Fast
 ‣ Hash_PermGroup_Fast( group ) ( function )

Returns: a small integer

Hash_PermGroup_Fast is faster than Hash_PermGroup_Complete (6.3-2), but will return the same value for groups with the same size, orbits and degree of transitivity.

##### 6.3-2 Hash_PermGroup_Complete
 ‣ Hash_PermGroup_Complete( group ) ( function )

Returns: a small integer

Hash_PermGroup_Complete is slower than Hash_PermGroup_Fast (6.3-1), but is extremely unlikely to return the same hash for two different groups.

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

generated by GAPDoc2HTML