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