{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:59Z","timestamp":1787340659814,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,5]]},"abstract":"<jats:p>Direct chaining is a popular and efficient class of hashing algorithms. In this paper we study optimum algorithms among direct chaining methods, under the restrictions that the records in the hash table are not moved after they are inserted, that for each chain the relative ordering of the records in the chain does not change after more insertions, and that only one link field is used per table slot. The varied-insertion coalesced hashing method (VICH), which is proposed and analyzed in [CV84], is conjectured to be optimum among all direct chaining algorithms in this class. We give strong evidence in favor of the conjecture by showing that VICH is optimum under fairly general conditions.<\/jats:p>","DOI":"10.1137\/0214036","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"490-499","source":"Crossref","is-referenced-by-count":1,"title":["Optimum Algorithms for a Model of Direct Chaining"],"prefix":"10.1137","volume":"14","author":[{"given":"Jeffrey Scott","family":"Vitter","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wen-Chin","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RBRE73","doi-asserted-by":"publisher","DOI":"10.1145\/361952.361964"},{"key":"RCV83","doi-asserted-by":"publisher","DOI":"10.1137\/0212046"},{"key":"RCV84","doi-asserted-by":"publisher","DOI":"10.1145\/1994.2205"},{"key":"RGK81","unstructured":"Daniel H. Greene, Donald E. Knuth, Mathematics for the analysis of algorithms, Progress in Computer Science, Vol. 1, Birkh\u00e4user Boston, Mass., 1981, 107\u201383c:680450481.68042"},{"key":"RGUI76","unstructured":"L. J. Guibas,  The analysis of hashing algorithms, Technical Report, STAN-CS-76-556, Computer Science Dept., Stanford Univ., Stanford, CA,  1976, PhD dissertation, August"},{"key":"RKNO84","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90036-1"},{"key":"RKNU73","volume-title":"The art of computer programming. Volume 3","author":"Knuth Donald E.","year":"1973"},{"key":"RVIT82A","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90024-4"},{"key":"RVIT82B","doi-asserted-by":"publisher","DOI":"10.1145\/358728.358745"},{"key":"RVIT83","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322375"},{"key":"RWI159","doi-asserted-by":"publisher","DOI":"10.1145\/368336.368352"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:01Z","timestamp":1787337781000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,5]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1985,5]]}},"alternative-id":["10.1137\/0214036"],"URL":"https:\/\/doi.org\/10.1137\/0214036","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,5]]}}}