APPENDIX B
Derivation of the Average Search Length of a Nondirect Hashed Data Structure
The derivation will be based on the following assumptions:
• There are n nodes in the structure, and the size of the primary storage area is N.
• All N primary storage area locations are equally probable to be generated each pass through the collision algorithm.
The easiest way to present the derivation for average search length is to consider the search for an unused location in which to perform an Insert operation. By our first assumption, n of the N locations are used. Therefore, the probability of hashing into an occupied location is n/N. For example, if there are 700 nodes in the structure, and the size of the primary storage area array is 1000, ...
Get Data Structures and Algorithms Using Java now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
