Title: An analysis on the performance of hash table-based dictionary implementations with different data usage models

Authors: M. Thenmozhi; H. Srimathi

Addresses: Department of Information Technology, SRM University, Chennai-603 203, India ' Department of Computer Applications, SRM University, Chennai-603 203, India

Abstract: The efficiency of in-memory computing applications depends on the choice of mechanism to store and retrieve strings. The tree and trie are the abstract data types (ADTs) that offer better efficiency for ordered dictionary. Hash table is one among the several other ADTs that provides efficient implementation for unordered dictionary. The performance of a data structure will depend on hardware capabilities of computing devices such as RAM size, cache memory size and even the speed of the physical storage media. Hence, an application which will be running on real or virtualised hardware environment certainly will have restricted access to memory and hashing is heavily used for such applications for speedy process. In this work, an analysis on the performance of six hash table based dictionary ADT implementations with different data usage models is carried out. The six different popular hash table based dictionary ADT implementations are Khash, Uthash, GoogleDenseHash, TommyHashtable, TommyHashdyn and TommyHashlin, tested under different hardware and software configurations.

Keywords: RAM size; cache memory size; hash tables; trie; abstract data types; dictionary ADTs; data usage models; unordered dictionaries.

DOI: 10.1504/IJHPCN.2017.083203

International Journal of High Performance Computing and Networking, 2017 Vol.10 No.1/2, pp.78 - 90

Received: 29 Jun 2015
Accepted: 22 Sep 2015
Published online: 22 Mar 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article