Page 9 - Data Structures Interactive Book
P. 9
9.1.3 Comparison with Other Search Techniques ................................................... 96
9.2 Hash Functions ........................................................................................................ 97
9.2.1 Properties of Good Hash Functions ................................................................ 97
9.2.2 Simple Hash Functions (Division, Multiplication) ......................................... 97
9.2.3 Cryptographic Hash Functions (MD5, SHA) ................................................. 99
9.2.4 Practical Examples of Hash Functions ......................................................... 100
9.3 Hash Tables ........................................................................................................... 100
9.3.1 Structure of a Hash Table ............................................................................. 101
9.3.2 Operations: Insertion, Deletion, Searching ................................................... 102
9.3.3 Handling Collisions ...................................................................................... 103
9.4 Collision Resolution Techniques ......................................................................... 105
9.4.1 Chaining ........................................................................................................ 105
9.4.2 Open Addressing (Linear Probing, Quadratic Probing, Double Hashing) ... 106
9.4.3 Comparison of Collision Resolution Methods .............................................. 107
9.5 Performance Analysis .......................................................................................... 109
9.5.1 Load Factor and Efficiency ........................................................................... 109
9.5.2 Average Case vs Worst Case Performance ................................................... 111
9.5.3 Trade-offs in Hash Table Design .................................................................. 112
9.6 Applications of Hashing ....................................................................................... 112
9.6.1 Database Indexing ......................................................................................... 113
9.6.2 Password Storage and Security ..................................................................... 114
9.6.3 Caching and Memory Management .............................................................. 114
9.6.4 Symbol Tables in Compilers ......................................................................... 115
9.7 Limitations of Hashing ......................................................................................... 116
9.7.1 Collision Overhead ....................................................................................... 116
9
