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