University of Twente Student Theses


A performance analysis of membership datastructures in Java

Voorberg, M. (2021) A performance analysis of membership datastructures in Java.

[img] PDF
Abstract:We aim to implement a data structure that stores a set of elements in such a way that we can efficiently query whether some element is a member of that set. This research limits itself to sets containing integers in Java. The research examines the setup time, execution time, and memory usage of existing data structures and finds that bitmaps and hash tables offer the best performance. Additionally, we show that altering van Emde Boas trees by replacing the lowest layers with a bitmap improves their performance in the context of this paper. Furthermore, we propose a new data structure: the hash table bitmap. It combines the efficient memory usage of the hash table with the fast experiment time of the bitmap.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Computer Science BSc (56964)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page