Method selection

When choosing one of the methods for representing a sparse array — using a linked list, binary tree, pointer array, or hashing — you must be guided by the requirements for speed and efficient use of memory. In addition, it is necessary to take into account how dense the sparse array will be filled.

If the logical array is filled very rarely, linked lists and binary trees are the most efficient in terms of memory usage, since they allocate memory only for those elements that are actually used. The links themselves require very little additional memory, which can usually be neglected. Representation in the form of an array of pointers involves the creation of the entire array of pointers, even if some elements are not used. In this case, the memory should not only fit the entire array, but also should remain free memory for the application. In some cases this can be a serious problem. You can usually estimate in advance the approximate amount of free memory and decide whether it is sufficient for your program. The hashing method takes an intermediate position between views using an array of pointers and a linked list or binary tree. Despite the fact that the entire primary array, even if it is not used, must be in memory, this array will still be smaller than the array of pointers.

If the logical array is filled fairly densely, the situation changes significantly. In this case, creating an array of pointers and hashing becomes more acceptable methods. Moreover, the search time for an element in the array of pointers is constant and does not depend on the degree of filling of the logical array. Although the search time for hashing is not constant, it is bounded above by some small value. But in the case of a linked list and a binary tree, the average search time increases as the array is filled. This should be remembered if access time is a critical factor.