Hash-based Collections

RWSet and RWIdentitySet as well as collections with “Hash” in their names.

Table 32 – Time and space requirements for hashed-based collections
operation	time cost	space cost
Insert	C	p+t
Find (average item)	C	0
Change/replace item	2C	0
Remove	C	p+t (recovered)
Container overhead		((M+2)p+i) + N(p+t)
Comments	Insertion happens based on the hashing function. Constant time costs assume that the items are well scattered in the hash slots. Worst case is linear in the number of items per slot. Replace for dictionary or map: The new value is copied in place. Otherwise, requires remove then insert.	Does not automatically resize. We recommend that the number of items be between one half and double the number of slots for most uses.