[MathJax on]

### 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.