Data Structures Using Java

12

Searching

Objectives

 An introduction to binary search trees

 An introduction to hash functions and hash tables

 A brief introduction to random number generation

 An introduction to Java Collections Framework structures supporting

search: List, Map, Set, HashSet, TreeMap, TreeSet,andHashMap

Key Terms

associative search

binary search tree

content-addressable search

document authentica-

tion

document integrity

document nonrepudia-

tion

hash collision

hash function

hash table load factor

index

JCF

map

mixed-linear-

congruential

probe

pseudorandom number

Introduction

Much of this course and text have been about the efficient storage and retrieval of

data. The interest ...