Hash Tables

algs4.cs.princeton.edu · 3,587 words · saved by 1 readers

If keys are small integers, we can use an array to implement a symbol table, by interpreting the key as an array index so that we can store the value associated with key i in array position i. In this section, we consider hashing, an extension of this simple method that handles more complicated types of keys. We reference key-value pairs using arrays by doing arithmetic operations to transform keys into array indices. Search algorithms that use hashing consist of two separate parts. The first step is to compute a hash function that transforms the search key into an array index. Ideally, different keys would map to different indices. This ideal is generally beyond our reach, so we have to face the possibility that two or more different keys may hash to the same array index. Thus, the second part of a hashing search is a collision-resolution process that deals with this situation. Program SeparateChainingHashST.java implements a symbol table with a separate-chaining hash table. It mainta

--> --> Hash Tables Algorithms, 4th edition 1. Fundamentals 1.1 Programming Model 1.2 Data Abstraction 1.3 Stacks and Queues 1.4 Analysis of Algorithms 1.5 Case Study: Union-Find 2. Sorting 2.1 Elementary Sorts 2.2 Mergesort 2.3 Quicksort 2.4 Priority Queues 2.5 Sorting Applications 3. Searching 3.1 Symbol Tables 3.2 Binary Search Trees 3.3 Balanced Search Trees 3.4 Hash Tables 3.5 Searching Applications 4. Graphs 4.1 Undirected Graphs 4.2 Directed Graphs 4.3 Minimum Spanning Trees 4.4 Shortest Paths 5. Strings 5.1 String Sorts 5.2 Tries 5.3 Substring Search 5.4 Regular Expressions 5.5 Data Co

Hash Tables

related reading