{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:27:52Z","timestamp":1787387272786,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1979,8]]},"abstract":"<jats:p>We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that, even with a full table, only about 2.13 probes will be required, on the average, to access an element. This scheme has the advantage that the expected time for adding a new element is proportional to that required to determine that an element is not in the table. Attention is then turned to the optimal reordering scheme and the minimax problem of ordering the table so as to minimize the length of the longest probe sequence to find any element. Both arranging problems can be translated to assignment problems. A unified algorithm is presented for these, together with the first method suggested. A number of simulation results are reported, the most interesting being an indication that the optimal reordering scheme will lead to an average of about 1.83 probes per search in a full table.<\/jats:p>","DOI":"10.1137\/0208038","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:03:31Z","timestamp":1109225011000},"page":"463-478","source":"Crossref","is-referenced-by-count":25,"title":["Efficient Ordering of Hash Tables"],"prefix":"10.1137","volume":"8","author":[{"given":"Gaston H.","family":"Gonnet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/361952.361964"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.134.0380"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"R4","unstructured":"G. H. Gonnet, Masters Thesis,  Interpolation and Interpolation Hash Searching, Doctoral Dissertation, University of Waterloo, Computer Science Dept., Waterloo, Ontario, Research Report, 77-02"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90059-5"},{"key":"R6","unstructured":"Gaston H. Gonnet,  Average lower bounds for open-addressing hash coding,  Proceedings of a Conference on Theoretical Computer Science (Univ. Waterloo, Waterloo, Ont., 1977), Comput. Sci. Dept., Univ. Waterloo, Waterloo, Ont.,  1978,  159\u2013162, August MR04952960413.68067"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/322092.322096"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90046-6"},{"key":"R9","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/321138.321140"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1147\/rd.12.0130"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322065"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Andrew C. Yao, F. Frances Yao,  The complexity of searching an ordered random table (extended abstract),  17th Annual Symposium on Foundations of Computer Science (Houston, Tex., 1976), IEEE Comput. Soc., Long Beach, Calif.,  1976,  173\u2013177, Oct. MR0449018","DOI":"10.1109\/SFCS.1976.32"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0208038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:16Z","timestamp":1787337256000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0208038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,8]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1979,8]]}},"alternative-id":["10.1137\/0208038"],"URL":"https:\/\/doi.org\/10.1137\/0208038","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,8]]}}}