{"entities":{"Q1069703":{"pageid":1080455,"ns":120,"title":"Item:Q1069703","lastrevid":66786504,"modified":"2026-04-12T12:51:08Z","type":"item","id":"Q1069703","labels":{"en":{"language":"en","value":"Two results on tables"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3936523"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$D1F2AA7F-CC21-4744-BDE8-398E6E4228CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"531e1d6f6ab59a77ab5e58c4835744364ed017fe","datavalue":{"value":{"text":"Two results on tables","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069703$553E5501-AB39-4135-8E39-A43D20D37EE2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8b101d03748c0d8d7d4983f31200c0b3d78b9bce","datavalue":{"value":"0584.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069703$F8871CD8-83C7-4ECA-AD26-4040B00F5F24","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"94f085ae296fe68ce24de4576cd81babe93e8235","datavalue":{"value":"10.1016/0020-0190(86)90041-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069703$0BF542B7-D83D-41DF-B9DE-B76135DA00AD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d16bba0f3ec28feefb6703b2a58b153a635b6911","datavalue":{"value":{"entity-type":"item","numeric-id":1069702,"id":"Q1069702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$FF9E46D6-7EE8-49C1-82D1-234DB38D57AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"01f2b44bd5296f1967545dd7a615bd568b590239","datavalue":{"value":{"entity-type":"item","numeric-id":582045,"id":"Q582045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$FC2D0473-7349-478B-B6E5-C6E019376311","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$7E19DF45-3689-4E50-902C-8CCBB340C05D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1069703$E5AD9CF9-D511-425A-9E8D-FC457B5F6739","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"db58cab2443c48cd5e2aef0e5d701e568a534242","datavalue":{"value":"\\textit{A. C. Yao} [J. Assoc. Comput. Mach. 28, 615-628 (1981; Zbl 0462.68079)] has determined the maximal size of a finite universe U such that it is possible to store all subsets A of U with k elements in a table of k slots in such a way that membership in A can be determined in a single probe. In his model it is assumed that all elements of A are physically stored in the table. If this assumption is relaxed and arbitrary elements in U can be stored in order to encode subsets A, then Yao's upper bound is no longer valid. It fails for trivial reasons only: a single probe lookup strategy only exists when it is possible to encode arbitrary subsets of U by a bitmap.    Our second result is an improvement of the optimal program size for perfect hash functions, solving an open problem from a paper by \\textit{C. Slot} and \\textit{P. van Emde Boas} [Proc. 16th ACM Symp. Theory of Computing, 391-400 (1984)]: For every value u, value \\(k\\leq u\\), and every subset A of \\(U=\\{0,...,u-1\\}\\) there exists a perfect hash function F which scatters A completely into a hash table of size O(k), such that the program size of F is \\(O(k\\cdot \\log \\log k+\\log \\log u)\\) and the evaluation time of F is O(1). These estimates are expressed in standard RAM space and instructions respectively. This improves the \\(O(k\\cdot \\log k+\\log \\log u)\\) upper bound established by \\textit{K. Mehlhorn} [Data structures and algorithms. Vol. I: Sorting and searching (Berlin, 1984; Zbl 0556.68003)] and Slot and van Emde Boas [loc. cit.].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069703$6049BD1F-53EC-4B66-849A-A83332D07F4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069703$1F67007B-AC9A-4669-817B-606CEA550DBF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"832931a1c0581f59836fc20647b0a07a1ba75c9c","datavalue":{"value":"3936523","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069703$CFB52214-82D8-408E-BCA3-89437416A229","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bef080406329f54862a9acac2d8f1caf2e89d675","datavalue":{"value":"single-probe table lookup strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069703$2873EBE0-F360-4ED0-8C9C-FDB63224302D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d738ce07b4e2d927b4c22f360defbb5172d4f48","datavalue":{"value":"perfect hashing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069703$BBA9DE99-2C02-4599-A58F-02FE7E22A932","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$495A8048-4F2E-4BF2-9CE0-2C09C9D4CE60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d2540cdbe3fa1e5dbc8aa3ed42737038b2e53780","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90041-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069703$3E47C007-BFEA-4013-AB02-5B96F885F278","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c672b7668d114fd74403ef88e522e33d0ee7c3db","datavalue":{"value":"W2055618684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069703$FC54E86A-5AB4-433B-9BC8-939DB7384A94","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"501eed559ada8b9e8d4026a1f777749d89dc401f","datavalue":{"value":{"entity-type":"item","numeric-id":3766870,"id":"Q3766870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$EF7AABA5-A3C1-4634-88B6-C1A8C344A767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$585035A1-8168-4091-A73E-B76C8857CDB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1c5883e6a323dea257e285e0caa569b30daff64","datavalue":{"value":{"entity-type":"item","numeric-id":3912073,"id":"Q3912073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069703$8B3E56E3-B8A0-483A-9F24-5AE721A406FB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58ac353fe00f7c3a8c1c6be79477939f997ab939","datavalue":{"value":{"entity-type":"item","numeric-id":4796170,"id":"Q4796170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd6cdb39b602abd34c70887b1279ffd18b7fef81","datavalue":{"value":{"amount":"+0.8407666087150574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069703$EE629878-FC28-43CB-89D0-5B5B17BA3D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"737e809b156a29b672a50425dbadeb3d094baf5d","datavalue":{"value":{"entity-type":"item","numeric-id":1198971,"id":"Q1198971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efa6c75398b2f03248672dfff0030a5bf4a614a5","datavalue":{"value":{"amount":"+0.8391760587692261","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069703$5AB3A15E-D215-499D-ACDA-51A676FCD715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bdcb0299a10e237ec74855c32a65c68cb73769b","datavalue":{"value":{"entity-type":"item","numeric-id":2762514,"id":"Q2762514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41ef9d0e9b564b3eb746936115c510e131ef854c","datavalue":{"value":{"amount":"+0.8384419679641724","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069703$1CF6916D-182A-46AF-82FD-D5D0D1D37A0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"273a14d9bdd4ddc4d5529acecdb6ef7e9b58ae40","datavalue":{"value":{"entity-type":"item","numeric-id":3719841,"id":"Q3719841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20be1f2628e4f2347e1f11067038d6f82dbcaeb7","datavalue":{"value":{"amount":"+0.8237560391426086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069703$3D53295E-7445-4527-A51B-83FBD56149B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3389c2c5d2b5336e3f3276473691e091daec6f6","datavalue":{"value":{"entity-type":"item","numeric-id":3603522,"id":"Q3603522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b3e63c4ea4a426d59f5cb5a3e5d9906e8992cf5","datavalue":{"value":{"amount":"+0.8102392554283142","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069703$DD7A9251-0466-4873-B5AE-922E7EC6A3D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two results on tables","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_results_on_tables"}}}}}