{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T19:39:31Z","timestamp":1771616371103,"version":"3.50.1"},"reference-count":14,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T00:00:00Z","timestamp":1647820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Fundaci\u00f3n para el Fomento de la Innovaci\u00f3n Industrial","award":["None"],"award-info":[{"award-number":["None"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Most computer programs or applications need fast data structures. The performance of a data structure is necessarily influenced by the complexity of its common operations; thus, any data-structure that exhibits a theoretical complexity of amortized constant time in several of its main operations should draw a lot of attention. Such is the case of a family of data structures that is called hash tables. However, what is the real efficiency of these hash tables? That is an interesting question with no simple answer and there are some issues to be considered. Of course, there is not a unique hash table; in fact, there are several sub-groups of hash tables, and, even more, not all programming languages use the same variety of hash tables in their default hash table implementation, neither they have the same interface. Nevertheless, all hash tables do have a common issue: they have to solve hash collisions; that is a potential weakness and it also induces a classification of hash tables according to the strategy to solve collisions. In this paper, some key concepts about hash tables are exposed and some definitions about those key concepts are reviewed and clarified, especially in order to study the characteristics of the main strategies to implement hash tables and how they deal with hash collisions. Then, some benchmark cases are designed and presented to assess the performance of hash tables. The cases have been designed to be randomized, to be self-tested, to be representative of a real user cases, and to expose and analyze the impact of different factors over the performance across different hash tables and programming languages. Then, all cases have been programmed using C++, Java and Python and analyzed in terms of interfaces and efficiency (time and memory). The benchmark yields important results about the performance of these structures and its (lack of) relationship with complexity analysis.<\/jats:p>","DOI":"10.3390\/a15030100","type":"journal-article","created":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T13:24:59Z","timestamp":1647869099000},"page":"100","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Key Concepts, Weakness and Benchmark on Hash Table Data Structures"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1418-9276","authenticated-orcid":false,"given":"Santiago","family":"Tapia-Fern\u00e1ndez","sequence":"first","affiliation":[{"name":"Escuela T\u00e9cnica Superior de Ingenier\u00eda Inform\u00e1tica, Universidad Polit\u00e9cnica de Madrid (UPM), Calle Ramiro de Maeztu, 7, 28040 Madrid, Spain"}]},{"given":"Daniel","family":"Garc\u00eda-Garc\u00eda","sequence":"additional","affiliation":[{"name":"Escuela T\u00e9cnica Superior de Ingenier\u00eda Inform\u00e1tica, Universidad Polit\u00e9cnica de Madrid (UPM), Calle Ramiro de Maeztu, 7, 28040 Madrid, Spain"}]},{"given":"Pablo","family":"Garc\u00eda-Hernandez","sequence":"additional","affiliation":[{"name":"Escuela T\u00e9cnica Superior de Ingenier\u00eda Inform\u00e1tica, Universidad Polit\u00e9cnica de Madrid (UPM), Calle Ramiro de Maeztu, 7, 28040 Madrid, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,21]]},"reference":[{"key":"ref_1","unstructured":"ISO\/IEC (2011). ISO International Standard ISO\/IEC 14882:2011(E)\u2014Programming Language C++, International Organization for Standardization (ISO)."},{"key":"ref_2","unstructured":"(2022, February 10). Interface Map<K,V>. Available online: https:\/\/docs.oracle.com\/javase\/8\/docs\/api\/java\/util\/Map.html."},{"key":"ref_3","unstructured":"(2022, February 10). Dictionaries. Available online: https:\/\/docs.python.org\/3\/tutorial\/datastructures.html#dictionaries."},{"key":"ref_4","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."},{"key":"ref_5","first-page":"1259","article-title":"An algorithm for the organization of information","volume":"146","author":"Landis","year":"1962","journal-title":"Proc. USSR Acad. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/367390.367400","article-title":"Trie Memory","volume":"9","author":"Fredkin","year":"1960","journal-title":"Commun. ACM"},{"key":"ref_7","unstructured":"(2022, February 10). Available online: https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libstdc%2B%2B-v3\/include\/bits\/hashtable.h."},{"key":"ref_8","unstructured":"(2022, February 10). Hash-Based Containers. Available online: https:\/\/gcc.gnu.org\/onlinedocs\/libstdc++\/ext\/pb_ds\/hash_based_containers.html."},{"key":"ref_9","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming: Volume 3: Sorting and Searching, Addison Wesley. [2nd ed.]."},{"key":"ref_10","unstructured":"(2022, February 10). Cuckoo Hashing, Available online: https:\/\/xlinux.nist.gov\/dads\/HTML\/cuckooHashing.html."},{"key":"ref_11","unstructured":"(2022, February 10). CMake Reference Documentation. Available online: https:\/\/cmake.org\/cmake\/help\/v3.23\/."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Pagh, R., and Rodler, F.F. (2001, January 28\u201331). Cuckoo Hashing. Proceedings of the Algorithms\u2014ESA 2001: 9th Annual European Symposium, \u00c5rhus, Denmark. Friedhelm Meyer auf der Heide.","DOI":"10.1007\/3-540-44676-1_10"},{"key":"ref_13","unstructured":"Bagwell, P. (2001). Ideal Hash Trees, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne."},{"key":"ref_14","unstructured":"Bagwell, P. (2000). Fast and Space Efficient Trie Searches, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/100\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:40:06Z","timestamp":1760136006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/3\/100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,21]]},"references-count":14,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["a15030100"],"URL":"https:\/\/doi.org\/10.3390\/a15030100","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,21]]}}}