Quick Index
Video


A video that accompanies this page is here....

The Idea 💡


What if
What if we could look up an object (e.g., customer, employee, etc) using the super-efficient get operation.

In other words, look up the object using simple indexed access on an array.

This is the main idea behind a hash table.

Overview


Purpose


The primary operation of a hash table is searching for a key and returning the value associated with the key.

Note that this chapter will focus on a "chained hash table". For information on another approach, see open-addressing hash table....

Put
A hash table associates a key (1000012) to a value (e.g., a customer object).
hashTable.put(1000012, customerKofi);
Get
A hash table returns the associated value (e.g., matching customer) for a search key (1000012).

We expect that the object (e.g., matching customer) would be equivalent to the object previously passed to the hash table in the "set" operation.
matchingCustomer = hashTable.get(1000012);


Performance


The power of a hash table is it's performance as shown in the table below.

      Hash Table Performance
Collection
Size		Search
Time
10 (Ten)TT
1,000 (Thousand)TT
1,000,000 (Million)TT
1,000,000,000,000,000 (Quadrillion)TT


The table shows us that a hash table searches at Big-O O(n), which is the max efficiency.

In other words, if you need fast key searching, you will not find faster than this structure.

A hash table's internal sub-components (lists) are slow, O(n), searchers. But the hash table's algorithms somehow boil these together to produce O(1). We'll learn how this magic happens.

Terms


The following is a listing of some important hash table terms.

The examples in this chapter will be a deeper dive into the terms.

Hashing
To convert an object into a representative integer.
Hash Function
The function that does the hashing conversion
Hash function input/output:

  • Input is an object
  • Output is a representative integer (called a hash code, hash value, or hash)

More details
Hash Code
A computed integer that represents an object key. A hash function (see above) is used to compute a hash code.
More details
How to Calculate Array Index From Hash Code
Divide the hash code by the array size and take the remainder (the modulus operator can be used)
Hash Table
This discussion is about a chained hash table (not open addressed).
  • Implements the Dictionary ADT (associative array)
  • Stores key-value pairs
  • Will set a given value at a given key (associates key to value)
  • Will return a value associated to a given key (value previously set at key) -- lookup
  • When operating properly, will lookup (find) a key with Big-O time complexity of O(1)

What Is a Hash Table?


Hash Table Goal?


Access Methods
These are the predominant methods in a hash table.
//Get (and return) the value associated with the parameter "key"
get(key)

//Put param "value" at param "key" into this hash table
put(key, value)
Most Efficient Access
The goal of a hash table is to provide the best possible efficiency for accessing data, e.g., O(1).
//Big-O O(1)
get(key)

//Big-O O(1)
put(key, value)
Key Data Type
The data key (search key) may be any data type -- it is not an integer index.
Example Keys:
kofi@foo.com
asha@here.com
chin@here.com
riya@there.com
etc.


Main Idea


Search Options
We have arrayed and linked lists in our context/toolbox but both have poor search performance compared to our ambitious goal of O(1).
Arrayed list search is O(n)
Linked list search is O(n)
Idea
Is there any method available that can get at element at any position in the list at O(1)?


Yes, the method "get(anIndex)" in a DynamicArray is O(1).
What If?
What if we converted the search key to an ______.

What term should we fill the blank with?


array index

What if we could convert a non-numeric key (e.g., "riya@hello.com") to a numeric index?

var match;
match = anArray.get(2);
match = anArray.get(8922920220);
match = anArray.get(2908924);
Converting Key to Index
The conversion of a key to an index is the magic we need.
//given key (e.g., "riya@hello.com")
let index = this.convertKeyToIndex(key);
let match = list.get(index)






























Data Structures And Algorithms (DSA) (Chapter 601 - Hash Table Concepts)










Chapter 601 - Hash Table Concepts < Prev Introduction Next >

Index Intro Concept Design 1 Algorithms Concept Design 2 Advantages References

Chapter Top Search Site Contents