Please enable JavaScript.
Coggle requires JavaScript to display documents.
SETS AND DICTIONARIES, SPACE AND TIME TRADE-OFFS - Coggle Diagram
SETS AND DICTIONARIES
SETS
UNORDERED COLLECTION OF DISTINCT ITEMS CALLED ELEMENTS
THE MOST IMPORTANT OPERATION: CHECKING MEMBERSHIP
MULTISET OR BAG
DICTIONARY
OPERATIONS
SEARCHING
ADDING
DELETING
SPACE AND TIME TRADE-OFFS
DYNAMIC PROGRAMMING
INPUT ENHANCEMENT
COUNTING METHODS FOR SORTING
BOYER-MOORE ALGORITHM FOR STRING MATCHING AND ITS SIMPLIFIED VERSION SUGESTED BY HORSPOOL
PRESTRUCTURING
HASHING
HASH TABLE
DISTRIBUTING KEY AMONG A ONE-DIMENSIONAL ARRAY H
A HASH TABLE'S SIZE SHOULD NOT BE EXCESSIVELY LARGE COMPARED TO THE NUMBER OF KEYS, BUT IR SHOULD BE SUFFICIENT TO NOT JEOPARDIZE THE IMPLEMENTATION'S TIME EFFICIENCY
HASH FUNCTION
NEEDS TO BE DISTRIBUTE KEYS AMONG THE CELLS OF THE HASH TABLE AS EVENLY AS POSSIBLE
HAS TO BE EASY TO COMPUTE
COLLISIONS
OPEN HASHING
KEYS ARE STORED IN LINKED LISTS ATTACHED TO CELLS OF A HASH TABLE
SEPARATE CHAINING
CLOSED HASHING
OPEN ADDRESSING
ALL KEYS ARE STORED IN THE HASH TABLE ITSELF
REHASHING
EXTENDIBLE HAHSING
BUCKET
CLUSTER
DOUBLE HASHING
INDEXING WITH B-TREES