| http://dbpedia.org/ontology/abstract
|
In computer science, tabulation hashing is … In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; later work by Carter and Wegman extended this method to arbitrary fixed-length keys. Generalizations of tabulation hashing have also been developed that can handle variable-length keys such as text strings. Despite its simplicity, tabulation hashing has strong theoretical properties that distinguish it from some other hash functions. In particular, it is 3-independent: every 3-tuple of keys is equally likely to be mapped to any 3-tuple of hash values. However, it is not 4-independent. More sophisticated but slower variants of tabulation hashing extend the method to higher degrees of independence. Because of its high degree of independence, tabulation hashing is usable with hashing methods that require a high-quality hash function, including hopscotch hashing, cuckoo hashing, and the MinHash technique for estimating the size of set intersections. estimating the size of set intersections.
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf +
, https://www.cs.wisc.edu/techreports/1970/TR88.pdf%7Ctitle=A +
, http://opendatastructures.org/%7Cdate=February +
, https://books.google.com/books%3Fid=vMqSAwAAQBAJ&pg=SA11-PA3 +
|
| http://dbpedia.org/ontology/wikiPageID
|
33467978
|
| http://dbpedia.org/ontology/wikiPageLength
|
19606
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1078929262
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Symposium_on_Foundations_of_Computer_Science +
, http://dbpedia.org/resource/Journal_of_Computer_and_System_Sciences +
, http://dbpedia.org/resource/Flajolet%E2%80%93Martin_algorithm +
, http://dbpedia.org/resource/Hash_collision +
, http://dbpedia.org/resource/Zobrist_hashing +
, http://dbpedia.org/resource/Exclusive_or +
, http://dbpedia.org/resource/Chess +
, http://dbpedia.org/resource/K-independent_hashing +
, http://dbpedia.org/resource/SIAM_Journal_on_Computing +
, http://dbpedia.org/resource/Separate_chaining +
, http://dbpedia.org/resource/Linear_probing +
, http://dbpedia.org/resource/Polynomial +
, http://dbpedia.org/resource/Mark_N._Wegman +
, http://dbpedia.org/resource/Expander_graph +
, http://dbpedia.org/resource/Albert_Lindsey_Zobrist +
, http://dbpedia.org/resource/Transposition_table +
, http://dbpedia.org/resource/Journal_of_the_ACM +
, http://dbpedia.org/resource/Hopscotch_hashing +
, http://dbpedia.org/resource/International_Colloquium_on_Automata%2C_Languages_and_Programming +
, http://dbpedia.org/resource/Lookup_table +
, http://dbpedia.org/resource/MinHash +
, http://dbpedia.org/resource/Cache_memory +
, http://dbpedia.org/resource/Computer_science +
, http://dbpedia.org/resource/Cuckoo_hashing +
, http://dbpedia.org/resource/Category:Hash_functions +
, http://dbpedia.org/resource/Discrete_Applied_Mathematics +
, http://dbpedia.org/resource/Category:Hashing +
, http://dbpedia.org/resource/Bit +
, http://dbpedia.org/resource/Hash_table +
, http://dbpedia.org/resource/Universal_hashing +
, http://dbpedia.org/resource/Lecture_Notes_in_Computer_Science +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Refbegin +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Sfnp +
, http://dbpedia.org/resource/Template:Citation +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Hashing +
, http://dbpedia.org/resource/Category:Hash_functions +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Method +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Tabulation_hashing?oldid=1078929262&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Tabulation_hashing +
|
| owl:sameAs |
http://dbpedia.org/resource/Tabulation_hashing +
, http://www.wikidata.org/entity/Q7673640 +
, http://rdf.freebase.com/ns/m.0h946b3 +
, http://yago-knowledge.org/resource/Tabulation_hashing +
, https://global.dbpedia.org/id/4vpu6 +
|
| rdf:type |
http://dbpedia.org/class/yago/Relation100031921 +
, http://dbpedia.org/class/yago/MathematicalRelation113783581 +
, http://dbpedia.org/class/yago/WikicatHashFunctions +
, http://dbpedia.org/ontology/Software +
, http://dbpedia.org/class/yago/Function113783816 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
|
| rdfs:comment |
In computer science, tabulation hashing is … In computer science, tabulation hashing is a method for constructing universal families of hash functions by combining table lookup with exclusive or operations. It was first studied in the form of Zobrist hashing for computer games; later work by Carter and Wegman extended this method to arbitrary fixed-length keys. Generalizations of tabulation hashing have also been developed that can handle variable-length keys such as text strings.variable-length keys such as text strings.
|
| rdfs:label |
Tabulation hashing
|
