Hash tables

The hash table constructors optionally take a size argument that is a non-binding guess as to the maximum size of the table, used to pre-allocate a reasonable amount of hash vector space. All hash tables automatically resize if the table grows too large or small.

In hash-table.diesel:

extend module Stdlib;

module OpenHashTableImpl;
fun next_probe(v:vector[`T], idx:int):int;
fun previous_probe(v:vector[`T], idx:int):int;
fun buckets_in_quadratic_probing_order_do(v:vector[`T], start_idx:int,
                                                 cl:&(int,T):void
                                                 ):void;
abstract class open_table[Key];
fun probe_histogram(t:open_table[`Key <= hashable[Key]]
                           ):histogram[int];

end module OpenHashTableImpl;

module HashTable;

hash_table is an implementation of tables that uses an open hashing algorithm, for hashable keys.

class hash_table[Key <= hashable[Key], Value]
                        isa m_removable_table[Key,Value];
fun check_correctness(t:hash_table[`Key,`Value]):void;
fun new_hash_table[Key <= hashable[Key], Value]()
                                                    :hash_table[Key,Value];
fun new_hash_table[Key <= hashable[Key], Value](size:int)
                                                    :hash_table[Key,Value];
class hash_CR_table[Key <= hashable[Key], Value]
                                                isa hash_table[Key,Value];
fun new_hash_CR_table[Key <= hashable[Key], Value]()
                                               :hash_CR_table[Key,Value];
fun new_hash_CR_table[Key <= hashable[Key], Value](size:int)
                                               :hash_CR_table[Key,Value];

end module HashTable;

In chained-hash-table.diesel:

chained_hash_table is an implementation of tables using a closed hashing algorithm.

extend module Stdlib;

module ChainedHashTable;
class chained_hash_table[Key <= hashable[Key], Value]
                                        isa m_removable_table[Key,Value];
fun new_chained_hash_table[Key <= hashable[Key], Value](
      ):chained_hash_table[Key,Value];
fun new_chained_hash_table[Key <= hashable[Key], Value](
      size:int):chained_hash_table[Key,Value];
fun probe_histogram(t:chained_hash_table[`Key,`Value]):histogram[int];
class chained_hash_CR_table[Key <= hashable[Key], Value]
        isa chained_hash_table[Key,Value];
fun new_chained_hash_CR_table[Key <= hashable[Key], Value](
      ):chained_hash_CR_table[Key,Value];
fun new_chained_hash_CR_table[Key <= hashable[Key], Value](
      size:int):chained_hash_CR_table[Key,Value];

end module ChainedHashTable;