Book contents
- Frontmatter
- Contents
- Preface
- Chapter 1 An Introduction to Collections, Generics, and the Timing Class
- Chapter 2 Arrays and ArrayLists
- Chapter 3 Basic Sorting Algorithms
- Chapter 4 Basic Searching Algorithms
- Chapter 5 Stacks and Queues
- Chapter 6 The BitArray Class
- Chapter 7 Strings, the String Class, and the StringBuilder Class
- Chapter 8 Pattern Matching and Text Processing
- Chapter 9 Building Dictionaries: The DictionaryBase Class and the SortedList Class
- Chapter 10 Hashing and the Hashtable Class
- Chapter 11 Linked Lists
- Chapter 12 Binary Trees and Binary Search Trees
- Chapter 13 Sets
- Chapter 14 Advanced Sorting Algorithms
- Chapter 15 Advanced Data Structures and Algorithms for Searching
- Chapter 16 Graphs and Graph Algorithms
- Chapter 17 Advanced Algorithms
- References
- Index
Chapter 10 - Hashing and the Hashtable Class
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Chapter 1 An Introduction to Collections, Generics, and the Timing Class
- Chapter 2 Arrays and ArrayLists
- Chapter 3 Basic Sorting Algorithms
- Chapter 4 Basic Searching Algorithms
- Chapter 5 Stacks and Queues
- Chapter 6 The BitArray Class
- Chapter 7 Strings, the String Class, and the StringBuilder Class
- Chapter 8 Pattern Matching and Text Processing
- Chapter 9 Building Dictionaries: The DictionaryBase Class and the SortedList Class
- Chapter 10 Hashing and the Hashtable Class
- Chapter 11 Linked Lists
- Chapter 12 Binary Trees and Binary Search Trees
- Chapter 13 Sets
- Chapter 14 Advanced Sorting Algorithms
- Chapter 15 Advanced Data Structures and Algorithms for Searching
- Chapter 16 Graphs and Graph Algorithms
- Chapter 17 Advanced Algorithms
- References
- Index
Summary
Hashing is a very common technique for storing data in such a way the data can be inserted and retrieved very quickly. Hashing uses a data structure called a hash table. Although hash tables provide fast insertion, deletion, and retrieval, operations that involve searching, such as finding the minimum or maximum value, are not performed very quickly. For these types of operations, other data structures are preferred (see, for example, Chapter 12 on binary search trees).
The .NET Framework library provides a very useful class for working with hash tables, the Hashtable class. We will examine this class in the chapter, but we will also discuss how to implement a custom hash table. Building hash tables is not very difficult and the programming techniques used are well worth knowing.
AN OVERVIEW OF HASHING
A hash table data structure is designed around an array. The array consists of elements 0 through some predetermined size, though we can increase the size later if necessary. Each data item is stored in the array based on some piece of the data, called the key. To store an element in the hash table, the key is mapped into a number in the range of 0 to the hash table size using a function called a hash function.
- Type
- Chapter
- Information
- Data Structures and Algorithms Using C# , pp. 176 - 193Publisher: Cambridge University PressPrint publication year: 2007