# FreeBSD Manual Pages

Hashtbl(3) OCamldoc Hashtbl(3)NAMEHashtbl - Hash tables and hash functions.ModuleModule HashtblDocumentationModuleHashtbl:sigendHash tables and hash functions. Hash tables are hashed association tables, with in-place modification.===Genericinterface===type('a,'b)tThe type of hash tables from type'ato type'b.valcreate:?random:bool->int->('a,'b)tHashtbl.createncreates a new, empty hash table, with initial sizen. For best results,nshould be on the order of the expected number of elements that will be in the table. The table grows as needed, sonis just an initial guess. The optionalrandomparameter (a boolean) controls whether the internal organization of the hash table is randomized at each execution ofHashtbl.createor deterministic over all executions. A hash table that is created with~random:falseuses a fixed hash func- tion (Hashtbl.hash) to distribute keys among buckets. As a conse- quence, collisions between keys happen deterministically. In Web-fac- ing applications or other security-sensitive applications, the deter- ministic collision patterns can be exploited by a malicious user to create a denial-of-service attack: the attacker sends input crafted to create many collisions in the table, slowing the application down. A hash table that is created with~random:trueuses the seeded hash functionHashtbl.seeded_hashwith a seed that is randomly chosen at hash table creation time. In effect, the hash function used is ran- domly selected among2^{30}different hash functions. All these hash functions have different collision patterns, rendering ineffective the denial-of-service attack described above. However, because of random- ization, enumerating all elements of the hash table usingHashtbl.foldorHashtbl.iteris no longer deterministic: elements are enumerated in different orders at different runs of the program. If no~randomparameter is given, hash tables are created in non-random mode by default. This default can be changed either programmatically by callingHashtbl.randomizeor by setting theRflag in theOCAMLRUN-PARAMenvironment variable.Before4.00.0therandomparameter was not present and all hash tables were created in non-randomized mode.valclear:('a,'b)t->unitEmpty a hash table. Useresetinstead ofclearto shrink the size of the bucket table to its initial size.valreset:('a,'b)t->unitEmpty a hash table and shrink the size of the bucket table to its ini- tial size.Since4.00.0valcopy:('a,'b)t->('a,'b)tReturn a copy of the given hashtable.valadd:('a,'b)t->'a->'b->unitHashtbl.addtblxyadds a binding ofxtoyin tabletbl. Previous bindings forxare not removed, but simply hidden. That is, after per- formingHashtbl.removetblx, the previous binding forx, if any, is restored. (Same behavior as with association lists.)valfind:('a,'b)t->'a->'bHashtbl.findtblxreturns the current binding ofxintbl, or raisesNot_foundif no such binding exists.valfind_opt:('a,'b)t->'a->'boptionHashtbl.find_opttblxreturns the current binding ofxintbl, orNoneif no such binding exists.Since4.05valfind_all:('a,'b)t->'a->'blistHashtbl.find_alltblxreturns the list of all data associated withxintbl. The current binding is returned first, then the previous bindings, in reverse order of introduction in the table.valmem:('a,'b)t->'a->boolHashtbl.memtblxchecks ifxis bound intbl.valremove:('a,'b)t->'a->unitHashtbl.removetblxremoves the current binding ofxintbl, restor- ing the previous binding if it exists. It does nothing ifxis not bound intbl.valreplace:('a,'b)t->'a->'b->unitHashtbl.replacetblxyreplaces the current binding ofxintblby a binding ofxtoy. Ifxis unbound intbl, a binding ofxtoyis added totbl. This is functionally equivalent toHashtbl.removetblxfollowed byHashtbl.addtblxy.valiter:('a->'b->unit)->('a,'b)t->unitHashtbl.iterftblappliesfto all bindings in tabletbl.freceives the key as first argument, and the associated value as second argument. Each binding is presented exactly once tof. The order in which the bindings are passed tofis unspecified. How- ever, if the table contains several bindings for the same key, they are passed tofin reverse order of introduction, that is, the most recent binding is passed first. If the hash table was created in non-randomized mode, the order in which the bindings are enumerated is reproducible between successive runs of the program, and even between minor versions of OCaml. For randomized hash tables, the order of enumeration is entirely random. The behavior is not defined if the hash table is modified byfduring the iteration.valfilter_map_inplace:('a->'b->'boption)->('a,'b)t->unitHashtbl.filter_map_inplaceftblappliesfto all bindings in tabletbland update each binding depending on the result off. IffreturnsNone, the binding is discarded. If it returnsSomenew_val, the binding is update to associate the key tonew_val. Other comments forHashtbl.iterapply as well.Since4.03.0valfold:('a->'b->'c->'c)->('a,'b)t->'c->'cHashtbl.foldftblinitcomputes(fkNdN...(fk1d1init)...), wherek1...kNare the keys of all bindings intbl, andd1...dNare the associated values. Each binding is presented exactly once tof. The order in which the bindings are passed tofis unspecified. How- ever, if the table contains several bindings for the same key, they are passed tofin reverse order of introduction, that is, the most recent binding is passed first. If the hash table was created in non-randomized mode, the order in which the bindings are enumerated is reproducible between successive runs of the program, and even between minor versions of OCaml. For randomized hash tables, the order of enumeration is entirely random. The behavior is not defined if the hash table is modified byfduring the iteration.vallength:('a,'b)t->intHashtbl.lengthtblreturns the number of bindings intbl. It takes constant time. Multiple bindings are counted once each, soHashtbl.lengthgives the number of timesHashtbl.itercalls its first argument.valrandomize:unit->unitAfter a call toHashtbl.randomize(), hash tables are created in ran- domized mode by default:Hashtbl.createreturns randomized hash tables, unless the~random:falseoptional parameter is given. The same effect can be achieved by setting theRparameter in theOCAMLRUNPARAMenvi- ronment variable. It is recommended that applications or Web frameworks that need to pro- tect themselves against the denial-of-service attack described inHashtbl.createcallHashtbl.randomize()at initialization time. Note that onceHashtbl.randomize()was called, there is no way to re- vert to the non-randomized default behavior ofHashtbl.create. This is intentional. Non-randomized hash tables can still be created usingHashtbl.create~random:false.Since4.00.0valis_randomized:unit->boolreturn if the tables are currently created in randomized mode by de- faultSince4.03.0typestatistics= { num_bindings :int; (* Number of bindings present in the table. Same value as returned byHashtbl.length. *) num_buckets :int; (* Number of buckets in the table. *) max_bucket_length :int; (* Maximal number of bindings per bucket. *) bucket_histogram :intarray; (* Histogram of bucket sizes. This arrayhistohas lengthmax_bucket_length+1. The value ofhisto.(i)is the number of buckets whose size isi. *) }Since4.00.0valstats:('a,'b)t->statisticsHashtbl.statstblreturns statistics about the tabletbl: number of buckets, size of the biggest bucket, distribution of buckets by size.Since4.00.0===Functorialinterface======Thefunctorialinterfaceallowstheuseofspecificcomparisonandhashfunctions,eitherforperformance/securityconcerns,orbecausekeysarenothashable/comparablewiththepolymorphicbuiltins.Forinstance,onemightwanttospecializeatableforintegerkeys:moduleIntHash=structtypet=intletequalij=i=jlethashi=ilandmax_intendmoduleIntHashtbl=Hashtbl.Make(IntHash)leth=IntHashtbl.create17inIntHashtbl.addh12helloThiscreatesanewmoduleIntHashtbl,withanewtype'aIntHashtbl.toftablesfromintto'a.Inthisexample,hcontainsstringvaluessoitstypeisstringIntHashtbl.t.Notethatthenewtype'aIntHashtbl.tisnotcompatiblewiththetype('a,'b)Hashtbl.tofthegenericinterface.Forexample,Hashtbl.lengthhwouldnottype-check,youmustuseIntHashtbl.length.===moduletypeHashedType=sigendThe input signature of the functorHashtbl.Make.moduletypeS=sigendThe output signature of the functorHashtbl.Make.moduleMake:functor(H:HashedType)->sigendFunctor building an implementation of the hashtable structure. The functorHashtbl.Makereturns a structure containing a typekeyof keys and a type'atof hash tables associating data of type'ato keys of typekey. The operations perform similarly to those of the generic interface, but use the hashing and equality functions specified in the functor argumentHinstead of generic equality and hashing. Since the hash function is not seeded, thecreateoperation of the result struc- ture always returns non-randomized hash tables.moduletypeSeededHashedType=sigendThe input signature of the functorHashtbl.MakeSeeded.Since4.00.0moduletypeSeededS=sigendThe output signature of the functorHashtbl.MakeSeeded.Since4.00.0moduleMakeSeeded:functor(H:SeededHashedType)->sigendFunctor building an implementation of the hashtable structure. The functorHashtbl.MakeSeededreturns a structure containing a typekeyof keys and a type'atof hash tables associating data of type'ato keys of typekey. The operations perform similarly to those of the generic interface, but use the seeded hashing and equality functions specified in the functor argumentHinstead of generic equality and hashing. Thecreateoperation of the result structure supports the~randomoptional parameter and returns randomized hash tables if~random:trueis passed or if randomization is globally on (seeHashtbl.randomize).Since4.00.0===Thepolymorphichashfunctions===valhash:'a->intHashtbl.hashxassociates a nonnegative integer to any value of any type. It is guaranteed that ifx=yorPervasives.comparexy=0, thenhashx=hashy. Moreover,hashalways terminates, even on cyclic structures.valseeded_hash:int->'a->intA variant ofHashtbl.hashthat is further parameterized by an integer seed.Since4.00.0valhash_param:int->int->'a->intHashtbl.hash_parammeaningfultotalxcomputes a hash value forx, with the same properties as forhash. The two extra integer parametersmeaningfulandtotalgive more precise control over hashing. Hashing performs a breadth-first, left-to-right traversal of the structurex, stopping aftermeaningfulmeaningful nodes were encountered, ortotalnodes (meaningful or not) were encountered. Iftotalas specified by the user exceeds a certain value, currently 256, then it is capped to that value. Meaningful nodes are: integers; floating-point numbers; strings; characters; booleans; and constant constructors. Larger values ofmeaningfulandtotalmeans that more nodes are taken into account to compute the final hash value, and therefore collisions are less likely to happen. However, hashing takes longer. The parametersmeaningfulandtotalgovern the tradeoff between accuracy and speed. As default choices,Hashtbl.hashandHashtbl.seeded_hashtakemeaningful=10andtotal=100.valseeded_hash_param:int->int->int->'a->intA variant ofHashtbl.hash_paramthat is further parameterized by an in- teger seed. Usage:Hashtbl.seeded_hash_parammeaningfultotalseedx.Since4.00.0 2020-08-11 source: Hashtbl(3)

NAME | Module | Documentation

Want to link to this manual page? Use this URL:

<https://www.freebsd.org/cgi/man.cgi?query=Hashtbl&sektion=3o&manpath=FreeBSD+12.1-RELEASE+and+Ports>