Quadratic probing (original) (raw)
Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found. An example sequence using quadratic probing is:
| Property | Value |
|---|---|
| dbo:abstract | Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found. An example sequence using quadratic probing is: Quadratic probing can be a more efficient algorithm in an open addressing table, since it better avoids the clustering problem that can occur with linear probing, although it is not immune. It also provides good memory caching because it preserves some locality of reference; however, linear probing has greater locality and, thus, better cache performance. (en) In de informatica is quadratic probing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een kwadratische functie verhoogd totdat een positie gevonden is of totdat na een aantal keer nog geen positie gevonden is (deze methode garandeert namelijk niet dat een mogelijk nog lege positie ook gevonden wordt). De berekende positie wordt modulo m berekend waarbij m de grootte van de hashtabel is. Hierdoor blijft de berekende waarde in het interval [0, m) van gehele getallen en dus binnen de hashtabel: mod m, met i = 0,1,2, ... en (nl) |
| dbo:wikiPageExternalLink | http://research.cs.vt.edu/AVresearch/hashing/quadratic.php |
| dbo:wikiPageID | 1852324 (xsd:integer) |
| dbo:wikiPageLength | 4744 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1069712932 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Search_algorithms dbr:Open_addressing dbr:Computer_programming dbr:Hash_function dbr:Linear_probing dbr:Locality_of_reference dbr:Hash_collisions dbc:Hashing dbr:Hash_table dbc:Articles_with_example_C_code dbc:Articles_with_example_Java_code dbr:Triangular_numbers dbr:Quadratic_polynomial |
| dbp:wikiPageUsesTemplate | dbt:Cn dbt:Dubious dbt:Explain dbt:Refimprove dbt:Reflist |
| dct:subject | dbc:Search_algorithms dbc:Hashing dbc:Articles_with_example_C_code dbc:Articles_with_example_Java_code |
| rdf:type | yago:Abstraction100002137 yago:Function113783816 yago:MathematicalRelation113783581 yago:Relation100031921 yago:WikicatHashFunctions |
| rdfs:comment | Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables. Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found. An example sequence using quadratic probing is: (en) In de informatica is quadratic probing een manier om collisies ('botsingen') bij het invoegen van een item in hashtabellen te verhelpen. Wanneer het invoegen op de positie die door de hashfunctie berekend is niet mogelijk is (doordat er al een item aanwezig is), wordt deze positie met een kwadratische functie verhoogd totdat een positie gevonden is of totdat na een aantal keer nog geen positie gevonden is (deze methode garandeert namelijk niet dat een mogelijk nog lege positie ook gevonden wordt). mod m, met i = 0,1,2, ... en (nl) |
| rdfs:label | Quadratic probing (nl) Quadratic probing (en) |
| owl:sameAs | freebase:Quadratic probing wikidata:Quadratic probing dbpedia-nl:Quadratic probing dbpedia-sr:Quadratic probing https://global.dbpedia.org/id/4tn4R yago-res:Quadratic probing |
| prov:wasDerivedFrom | wikipedia-en:Quadratic_probing?oldid=1069712932&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Quadratic_probing |
| is dbo:wikiPageRedirects of | dbr:Quadratic_hashing |
| is dbo:wikiPageWikiLink of | dbr:Cuckoo_hashing dbr:Double_hashing dbr:Quadratic dbr:Open_addressing dbr:Hopscotch_hashing dbr:Hash_collision dbr:Hash_function dbr:Linear_probing dbr:Hash_table dbr:Prime_number dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Primary_clustering dbr:Quadratic_hashing |
| is foaf:primaryTopic of | wikipedia-en:Quadratic_probing |