Skip to Main Content
Mastering Algorithms with C
book

Mastering Algorithms with C

by Kyle Loudon
August 1999
Intermediate to advanced content levelIntermediate to advanced
560 pages
18h 57m
English
O'Reilly Media, Inc.
Content preview from Mastering Algorithms with C

Related Topics

Direct-address tables

A simple type of hash table in which there is a one-to-one mapping between all possible keys and positions in the table. Since no two keys map to the same position, there is no need for collision resolution. However, if there are many possible keys, the table will be large. Generally, direct addressing works well when the universe of possible keys is small.

Linear congruential generators

A common class of random number generators. Understanding the principles behind random number generators can help in devising good hash functions.

Quadratic probing

An alternative to linear probing and double hashing for probing an open-addressed hash table. In quadratic probing, the sequence of positions probed is determined using a quadratic-form hash function. In general, quadratic probing performs better than linear probing, but it does not perform as well as double hashing. Quadratic probing results in secondary clustering , a form of clustering that is less severe than the primary clustering of linear probing.

Universal hashing

A hashing method in which hashing functions are generated randomly at runtime so that no particular set of keys is likely to produce a bad distribution of elements in the hash table. Because the hash functions are generated randomly, even hashing the same set of keys during different executions may result in different measures of performance.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Luciano Manelli
Head First C

Head First C

David Griffiths, Dawn Griffiths

Publisher Resources

ISBN: 1565924533Supplemental ContentErrata Page