O'Reilly logo

Data Structures and Algorithms Using Java by William McAllister

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required