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.cecil:

concrete object empty_hash_bucket;
concrete object removed_hash_bucket;
let use_linear_probing:bool;
method buckets_in_probing_order_do(v@:vector[`T], start_idx@:int,
                                   cl:&(int,T):void):void;
method buckets_in_linear_probing_order_do(v@:vector[`T], start_idx_oop@:int,
                                          cl:&(int,T):void
                                          ):void;
method next_probe(v@:vector[`T], idx:int):int;
method previous_probe(v@:vector[`T], idx:int):int;
method buckets_in_quadratic_probing_order_do(v@:vector[`T], start_idx@:int,
                                             cl:&(int,T):void
                                             ):void;
let good_table_sizes:vector[int];
let var default_open_table_size:int;
abstract object open_table[Key];
method remove_bucket(t@:open_table[`Key], idx:int):void;
method remove_all(t@:open_table[`Key]):void;
method check_correctness(t@:open_table[`Key <= hashable[Key]]):void;
method probe_histogram(t@:open_table[`Key <= hashable[Key]]):histogram[int];

template object hash_table[Key <= hashable[Key], Value]
                        isa m_removable_table[Key,Value], open_table[Key];
method do_associations(t@:hash_table[`Key,`Value], c:&(Key,Value):void):void;
method do_associations_allowing_updates(t@:hash_table[`Key,`Value],
                                        c:&(Key,Value):void):void;
method fetch(t@:hash_table[`Key,`Value], key:Key, if_absent:&():Value):Value;
method store(t@:hash_table[`Key,`Value], key:Key, value:Value,
             if_absent:&():void):void;
method remove_key(t@:hash_table[`Key,`Value], key:Key,
                  if_absent:&():`Else):Value|Else;
method remove_keys_if(t@:hash_table[`Key,`Value], pred:&(Key):bool):int;
method remove_all(t@:hash_table[`Key,`Value]):void;
method check_correctness(t@:hash_table[`Key,`Value]):void;
method new_hash_table[Key <= hashable[Key], Value]():hash_table[Key,Value];
method new_hash_table[Key <= hashable[Key], Value](size:int)
                                                    :hash_table[Key,Value];
method copy_empty(t@:hash_table[`Key,`Value]):hash_table[Key,Value];
method copy(t@:hash_table[`Key,`Value]):hash_table[Key,Value];
template object hash_CR_table[Key <= hashable[Key], Value]
                                                isa hash_table[Key,Value];
method elem_separator(t@:hash_CR_table[`Key,`Value]):string;
method new_hash_CR_table[Key <= hashable[Key], Value]()
                                               :hash_CR_table[Key,Value];
method new_hash_CR_table[Key <= hashable[Key], Value](size:int)
                                               :hash_CR_table[Key,Value];
method copy_empty(c@:hash_CR_table[`Key,`Value]):hash_CR_table[Key,Value];
method copy(t@:hash_CR_table[`Key,`Value]):hash_CR_table[Key,Value];

hash_table is an implementation of tables that uses an open hashing algorithm, for hashable keys. In chained-hash-table.cecil:

template object chained_hash_table[Key <= hashable[Key], Value]
                                        isa m_removable_table[Key,Value];
method do_associations(t@:chained_hash_table[`Key,`Value],
                       c:&(Key,Value):void):void;
method do_associations_allowing_updates(t@:chained_hash_table[`Key,`Value],
                                        c:&(Key,Value):void):void;
method fetch(t@:chained_hash_table[`Key,`Value], key:Key,
             if_absent:&():`Else):Value|Else;
method store(t@:chained_hash_table[`Key,`Value], key:Key, value:Value,
             if_absent:&():void):void;
method remove_key(t@:chained_hash_table[`Key,`Value], key:Key,
                  if_absent:&():`Else):Value|Else;
method remove_keys_if(t@:chained_hash_table[`Key,`Value],
                        pred:&(Key):bool):int;
method remove_all(t@:chained_hash_table[`Key,`Value]):void;
let var default_chained_hash_table_size:int;
method new_chained_hash_table[Key <= hashable[Key], Value]()
     :chained_hash_table[Key,Value];
method new_chained_hash_table[Key <= hashable[Key], Value](size:int)
     :chained_hash_table[Key,Value];
method copy_empty(t@:chained_hash_table[`Key,`Value]
                  ):chained_hash_table[Key,Value];
method copy(t@:chained_hash_table[`Key,`Value]):chained_hash_table[Key,Value];
method probe_histogram(t@:chained_hash_table[`Key,`Value]):histogram[int];
template object chained_hash_CR_table[Key <= hashable[Key], Value]
        isa chained_hash_table[Key,Value];
method elem_separator(t@:chained_hash_CR_table[`Key,`Value]):string;
method new_chained_hash_CR_table[Key <= hashable[Key], Value]()
     :chained_hash_CR_table[Key,Value];
method new_chained_hash_CR_table[Key <= hashable[Key], Value](size:int)
                                             :chained_hash_CR_table[Key,Value];
method copy_empty(c@:chained_hash_CR_table[`Key,`Value]
                  ):chained_hash_CR_table[Key,Value];

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