Hashing in Computer Science: Fifty Years of Slicing and Dicing

Content: PREFACE.  <
p>
PART I: MATHEMATICAL PRELIMINARIES.  <
p>
1. Counting.  <
p>
1.1: The Sum and Product Rules.  <
p>
1.2: Mathematical Induction.  <
p>
1.3: Factorial.  <
p>
1.4: Binomial Coefficients.  <
p>
1.5: Multinomial Coefficients.  <
p>
1.6: Permutations.  <
p>
1.7: Combinations.  <
p>
1.8: The Principle of Inclusion-Exclusion.  <
p>
1.9: Partitions.  <
p>
1.10: Relations.  <
p>
1.11: Inverse Relations.  <
p>
Appendix 1: Summations Involving Binomial Coefficients.  <
p>
2. Recurrence and Generating Functions.  <
p>
2.1: Recursions.  <
p>
2.2: Generating Functions.  <
p>
2.3: Linear Constant Coefficient Recursions.  <
p>
2.4: Solving Homogeneous LCCRs Using Generating Functions.  <
p>
2.5: The Catalan Recursion.  <
p>
2.6: The Umbral Calculus.  <
p>
2.7: Exponential Generating Functions.  <
p>
2.8: Partitions of a Set: The Bell and Stirling Numbers.  <
p>
2.9: Rouche   s Theorem and the Lagrange   s Inversion Formula.  <
p>
3. Asymptotic Analysis.  <
p>
3.1: Growth Notation for Sequences.  <
p>
3.2: Asymptotic Sequences and Expansions.  <
p>
3.3: Saddle Points.  <
p>
3.4: Laplace   s Method.  <
p>
3.5: The Saddle Point Method.  <
p>
3.6: When Will the Saddle Point Method Work?  <
p>
3.7: The Saddle Point Bounds.  <
p>
3.8: Examples of Saddle Point Analysis.  <
p>
4. Discrete Probability Theory.  <
p>
4.1: The Origins of Probability Theory.  <
p>
4.2: Chance Experiments, Sample Points, Spaces, and Events.  <
p>
4.3: Random Variables.  <
p>
4.4: Moments   Expectation and Variance.  <
p>
4.5: The Birthday Paradox.  <
p>
4.6: Conditional Probability and Independence.  <
p>
4.7: The Law of Large Numbers (LLN).  <
p>
4.8: The Central Limit Theorem (CLT).  <
p>
4.9: Random Processes and Markov Chains.  <
p>
5. Number Theory and Modern Algebra.  <
p>
5.1: Prime Numbers.  <
p>
5.2: Modular Arithmetic and the Euclidean Algorithm.  <
p>
5.3: Modular Multiplication.  <
p>
5.4: The Theorems of Fermat and Euler.  <
p>
5.5: Fields and Extension Fields.  <
p>
5.6: Factorization of Integers.  <
p>
5.7: Testing Primality.  <
p>
6. Basic Concepts of Cryptography.  <
p>
6.1: The Lexicon of Cryptography.  <
p>
6.2: Stream Ciphers.  <
p>
6.3: Block Ciphers.  <
p>
6.4: Secrecy Systems and Cryptanalysis.  <
p>
6.5: Symmetric and Two-Key Cryptographic Systems.  <
p>
6.6: The Appearance of Public Key Cryptographic systems.  <
p>
6.7: A Multitude of Keys.  <
p>
6.8: The RSA Cryptosystem.  <
p>
6.9: Does PKC Solve the Problem of Key Distribution?  <
p>
6.10: Elliptic Groups Over the Reals.  <
p>
6.11: Elliptic Groups Over the Field Zm,2 .  <
p>
6.12: Elliptic Group Cryptosystems.  <
p>
6.13: The Menezes-Vanstone Elliptic Curve Cryptosystem.  <
p>
6.14: Super-Singular Elliptic Curves.  <
p>
PART II: HASHING FOR STORAGE: DATA MANAGEMENT.  <
p>
7. Basic Concepts.  <
p>
7.1: Overview of the Records Management Problem.  <
p>
7.2: A Simple Storage Management Protocol: Plain Vanilla Chaining.  <
p>
7.3: Record-Management with Sorted Keys.  <
p>
8. Hash Functions.  <
p>
8.1: The Origin of Hashing.  <
p>
8.2: Hash Tables.  <
p>
8.3: A Statistical Model for Hashing.  <
p>
8.4: The Likelihood of Collisions.  <
p>
9. Hashing Functions: Examples and Evaluation.  <
p>
9.1: Overview: The Tradeoff of Randomization Versus Computational Simplicity.  <
p>
9.2: Some Examples of Hashing Functions.  <
p>
9.3: Performance of Hash Functions: Formulation.  <
p>
9.4: The X2-Test.  <
p>
9.5: Testing a Hash Function.  <
p>
9.6: The McKenzie et al. Results.  <
p>
10. Record Chaining with Hash Tables.  <
p>
10.1: Separate Chaining of Records.  <
p>
10.2: Analysis of Separate Chaining Hashing Sequences and the Chains They Create.  <
p>
10.3: A Combinatorial Analysis of Separate Chaining.  <
p>
10.4: Coalesced Chaining.  <
p>
10.5: The Pittel-Yu Analysis of EICH Coalesced Chaining.  <
p>
10.6: To Separate or to Coalesce
 and Which Version? That Is the Question.  <
p>
11. Perfect Hashing.  <
p>
11.1: Overview.  <
p>
11.2: Chichelli   s Construction.  <
p>
12. The Uniform Hashing Model.  <
p>
12.1: An Idealized Hashing Model.  <
p>
12.2: The Asymptotics of Uniform Hashing.  <
p>
12.3: Collision-Free Hashing.  <
p>
13. Hashing with Linear Probing.  <
p>
13.1: Formulation and Preliminaries.  <
p>
13.2: Performance Measures for LP Hashing.  <
p>
13.3: All Cells Other than HTn-1 in the Hash-Table of n Cells are Occupied.  <
p>
13.4: m-Keys Hashed into a Hash Table of n Cells Leaving Cell HTn-1 Unoccupied.  <
p>
13.5: The Probability Distribution for the Length of a Search.  <
p>
13.6: Asymptotics.  <
p>
13.7: Hashing with Linear Open Addressing: Coda.  <
p>
13.8: A Possible Improvement to Linear Probing.  <
p>
14. Double Hashing.  <
p>
14.1: Formulation of Double Hashing.  <
p>
14.2: Progressions and Strides.  <
p>
14.3: The Number of Progressions Which Fill a Hash-Table Cell.  <
p>
14.3.1: Progression Graphs.  <
p>
14.4: Dominance.  <
p>
14.5: Insertion-Cost Bounds Relating Uniform and Double Hashing.  <
p>
14.6: UsuallyDoubleHash.  <
p>
14.7: The UDH Chance Experiment and the Cost to Insert the Next Key by Double Hashing.  <
p>
14.8: Proof of Equation (14.12a).  <
p>
14.9: UsuallyDoubleHash.  <
p>
14.10: Proof of Equation (14.12b).  <
p>
15. Optimum Hashing.  <
p>
15.1: The Ullman   Yao Framework.  <
p>
15.1.1: The Ullman   Yao Hashing Functions.  <
p>
15.1.2: Ullman   Yao INSERT(k) and SEARCH(k).  <
p>
15.1.3: The Ullman   Yao Statistical Model.  <
p>
15.2: The Rates at Which a Cell is Probed and Occupied.  <
p>
15.3: Partitions of (i)Scenarios, (i)Subscenarios, and Their Skeletons.  <
p>
15.3.1: (i)Subscenarios.  <
p>
15.3.2: Skeletons.  <
p>
15.4: Randomly Generated m-Scenarios.  <
p>
15.5: Bounds on Random Sums.  <
p>
15.6: Completing the Proof of Theorem 15.1.  <
p>
PART III: SOME NOVEL APPLICATIONS OF HASHING.  <
p>
16. Karp-Rabin String Searching.  <
p>
16.1: Overview.  <
p>
16.2: The Basic Karp-Rabin Hash-Fingerprint Algorithm.  <
p>
16.3: The Plain Vanilla Karp-Rabin Fingerprint Algorithm.  <
p>
16.4: Some Estimates on Prime Numbers.  <
p>
16.5: The Cost of False Matches in the Plain Vanilla Karp-Rabin Fingerprint Algorithm.  <
p>
16.6: Variations on the Plain Vanilla Karp-Rabin Fingerprint Algorithm.  <
p>
16.7: A Nonhashing Karp-Rabin Fingerprint.  <
p>
17. Hashing Rock and Roll.  <
p>
17.1: Overview of Audio Fingerprinting .  <
p>
17.2: The Basics of Fingerprinting Music.  <
p>
17.3: Haar Wavelet Coding.  <
p>
17.4: Min-Hash.  <
p>
17.5: Some Commercial Fingerprinting Products.  <
p>
18. Hashing in E-Commerce.  <
p>
18.1: The Varied Applications of Cryptography.  <
p>
18.2: Authentication.  <
p>
18.3: The Need for Certificates.  <
p>
18.4: Cryptographic Hash Functions.  <
p>
18.5: X.509 Certificates and CCIT Standardization.  <
p>
18.6: The Secure Socket Layer (SSL).  <
p>
18.7: Trust on the Web ... Trust No One Over 40!  <
p>
18.8: MD5.  <
p>
18.9: Criticism of MD5.  <
p>
18.10: The Wang-Yu Collision Attack.  <
p>
18.11: Steven   s Improvement to the Wang-Yu Collision Attack.  <
p>
18.12: The Chosen-Prefix Attack on MD5.  <
p>
18.13: The Rogue CA Attack Scenario.  <
p>
18.14: The Secure Hash Algorithms.  <
p>
18.15: Criticism of SHA-1.  <
p>
18.16: SHA-2.  <
p>
18.17: What Now?  <
p>
Appendix 18: Sketch of the Steven   s Chosen Prefix Attack.  <
p>
19. Hashing and the Secure Distribution of Digital Media.  <
p>
19.1: Overview.  <
p>
19.2: Intellectual Property (Copyrights and Patents).  <
p>
19.3: Steganography.  <
p>
19.4: Boil, Boil, Toil ... and But First, Carefully Mix.  <
p>
19.5: Software Distribution Systems.  <
p>
19.6: Watermarks.  <
p>
19.7: An Image-Processing Technique for Watermarking.  <
p>
19.8: Using Geometric Hashing to Watermark Images.  <
p>
19.9: Biometrics and Hashing.  <
p>
19.10: The Dongle.  <
p>
Appendix 19: Reed-Solomon and Hadamard Coding.  <
p>
Exercises and Solutions.  <
p>
INDEX.