1/3/26, 11:28 AM Hash Tables with Python
❯
Tutorials References Exercises Certificates Search... Upgrade Get Certified Sign In
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Cross Validation
AUC - ROC Curve
K-nearest neighbors
Python DSA
Python DSA
Lists and Arrays
Stacks
Queues
Linked Lists
Hash Tables
Trees
Binary Trees
Binary Search Trees
Hash Tables with Python
AVL Trees COLOR
❮ Previous Next ❯
Graphs PICKER
Linear Search
Binary Search
Bubble Sort Hash Table
Selection Sort
Insertion Sort A Hash Table is a data structure designed to be fast to work with.
The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because
searching for, adding, and deleting data can be done really quickly, even for large amounts
of data.
In a Linked List, finding a person "Bob" takes time because we would have to go from one
node to the next, checking each node, until the node with "Bob" is found.
And finding "Bob" in an list/array could be fast if we knew the index, but when we only
know the name "Bob", we need to compare each element and that takes time.
With a Hash Table however, finding "Bob" is done really fast because there is a way to go
directly to where "Bob" is stored, using something called a hash function.
Building A Hash Table from Scratch
To get the idea of what a Hash Table is, let's try to build one from scratch, to store unique
first names inside it.
We will build the Hash Table in 5 steps:
1. Create an empty list (it can also be a dictionary or a set).
2. Create a hash function.
3. Inserting an element using a hash function.
4. Looking up an element using a hash function.
5. Handling collisions.
Step 1: Create an Empty List
To keep it simple, let's create a list with 10 empty elements.
[Link] 1/6
1/3/26, 11:28 AM Hash Tables with Python
❯
Tutorials References Exercises Certificates
my_list = [None, None, None, None, None, None, None, None, None, None]
Upgrade Get Certified Sign In
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Cross Validation
AUC - ROC Curve
K-nearest neighbors
Each of these elements is called a bucket in a Hash Table.
Python DSA
Python DSA
Lists and Arrays
Stacks Step 2: Create a Hash Function
Queues
Now comes the special way we interact with Hash Tables.
Linked Lists
Hash Tables We want to store a name directly into its right place in the array, and this is where the hash
Trees function comes in.
Binary Trees
Binary Search Trees A hash function can be made in many ways, it is up to the creator of the Hash Table. A
AVL Trees common way is to find a way to convert the value into a number that equals one of the
Graphs Hash Table's index numbers, in this case a number from 0 to 9.
Linear Search
In our example we will use the Unicode number of each character, summarize them and do
Binary Search
a modulo 10 operation to get index numbers 0-9.
Bubble Sort
Selection Sort
Insertion Sort
Example Get your own Python Server
Create a Hash Function that sums the Unicode numbers of each character and return a
number between 0 and 9:
def hash_function(value):
sum_of_chars = 0
for char in value:
sum_of_chars += ord(char)
return sum_of_chars % 10
print("'Bob' has hash code:", hash_function('Bob'))
Try it yourself »
The character B has Unicode number 66 , o has 111 , and b has 98 . Adding those
together we get 275 . Modulo 10 of 275 is 5 , so "Bob" should be stored at index 5 .
The number returned by the hash function is called the hash code.
Unicode number: Everything in our computers are stored as numbers, and the Unicode
code number is a unique number that exist for every character. For example, the character
A has Unicode number 65 .
See this page for more information about how characters are represented as numbers.
Modulo: A modulo operation divides a number with another number, and gives us the
resulting remainder. So for example, 7 % 3 will give us the remainder 1 . (Dividing 7
apples between 3 people, means that each person gets 2 apples, with 1 apple to spare.)
[Link] 2/6
1/3/26, 11:28 AM Hash Tables with Python
In Python and most programming languages, the modolo operator is written as % . ❯
Tutorials References Exercises Certificates Upgrade Get Certified Sign In
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Cross Validation
AUC - ROC Curve
Step 3: Inserting an Element
K-nearest neighbors
According to our hash function, "Bob" should be stored at index 5.
Python DSA
Python DSA
Lets create a function that add items to our hash table:
Lists and Arrays
Stacks
Queues
Example
Linked Lists
def add(name):
Hash Tables
index = hash_function(name)
Trees
my_list[index] = name
Binary Trees
Binary Search Trees add('Bob')
AVL Trees print(my_list)
Graphs
Linear Search Run Example »
Binary Search
Bubble Sort
Selection Sort After storing "Bob" at index 5, our array now looks like this:
Insertion Sort
my_list = [None, None, None, None, None, 'Bob', None, None, None, None]
We can use the same functions to store "Pete", "Jones", "Lisa", and "Siri" as well.
Example
add('Pete')
add('Jones')
add('Lisa')
add('Siri')
print(my_list)
Run Example »
After using the hash function to store those names in the correct position, our array looks
like this:
Example
my_list = [None, 'Jones', None, 'Lisa', None, 'Bob', None, 'Siri', 'Pete',
None]
Step 4: Looking up a name
[Link] 3/6
1/3/26, 11:28 AM Hash Tables with Python
Now that we have a super basic Hash Table, let's see how we can look up a name from it. ❯
Tutorials References Exercises Certificates Upgrade Get Certified Sign In
To find "Pete" in the Hash Table, we give the name "Pete" to our hash function. The hash
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
function returns 8 , meaning that "Pete" is stored at index 8.
Cross Validation
AUC - ROC Curve
K-nearest neighbors
Example
Python DSA
def contains(name):
Python DSA index = hash_function(name)
Lists and Arrays return my_list[index] == name
Stacks
Queues print("'Pete' is in the Hash Table:", contains('Pete'))
Linked Lists
Hash Tables Run Example »
Trees
Binary Trees
Binary Search Trees Because we do not have to check element by element to find out if "Pete" is in there, we
AVL Trees can just use the hash function to go straight to the right element!
Graphs
Linear Search
Binary Search Step 5: Handling collisions
Bubble Sort
Selection Sort Let's also add "Stuart" to our Hash Table.
Insertion Sort
We give "Stuart" to our hash function, which returns 3 , meaning "Stuart" should be stored
at index 3.
Trying to store "Stuart" in index 3, creates what is called a collision, because "Lisa" is
already stored at index 3.
To fix the collision, we can make room for more elements in the same bucket. Solving the
collision problem in this way is called chaining, and means giving room for more elements
in the same bucket.
Start by creating a new list with the same size as the original list, but with empty buckets:
my_list = [
[],
[],
[],
[],
[],
[],
[],
[],
[],
[]
]
Rewrite the add() function, and add the same names as before:
Example
def add(name):
index = hash_function(name)
[Link] 4/6
1/3/26, 11:28 AM Hash Tables with Python
my_list[index].append(name) ❯
Tutorials References Exercises Certificates Upgrade Get Certified Sign In
add('Bob')
HTML CSS JAVASCRIPT SQL PYTHON
add('Pete') JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
Cross Validation
add('Jones')
AUC - ROC Curve
add('Lisa')
K-nearest neighbors add('Siri')
add('Stuart')
Python DSA print(my_list)
Python DSA
Lists and Arrays Run Example »
Stacks
Queues
Linked Lists After implementing each bucket as a list, "Stuart" can also be stored at index 3, and our
Hash Tables Hash Set now looks like this:
Trees
Binary Trees
Binary Search Trees Result
AVL Trees
Graphs my_list = [
Linear Search [None],
['Jones'],
Binary Search
[None],
Bubble Sort
['Lisa', 'Stuart'],
Selection Sort
[None],
Insertion Sort ['Bob'],
[None],
['Siri'],
['Pete'],
[None]
]
Searching for "Stuart" now takes a little bit longer time, because we also find "Lisa" in the
same bucket, but still much faster than searching the entire Hash Table.
Uses of Hash Tables
Hash Tables are great for:
Checking if something is in a collection (like finding a book in a library).
Storing unique items and quickly finding them (like storing phone numbers).
Connecting values to keys (like linking names to phone numbers).
The most important reason why Hash Tables are great for these things is that Hash Tables
are very fast compared Arrays and Linked Lists, especially for large sets. Arrays and Linked
Lists have time complexity O(n) for search and delete, while Hash Tables have just O(1)
on average.
Hash Tables Summarized
Hash Table elements are stored in storage containers called buckets.
A hash function takes the key of an element to generate a hash code.
[Link] 5/6
1/3/26, 11:28 AM Hash Tables with Python
The hash code says what bucket the element belongs to, so now we can go directly to that ❯
Tutorials References Exercises Certificates Upgrade
Hash Table element: to modify it, or to delete it, or just to check if it exists.
Get Certified Sign In
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO [Link] C C++ C# BOOTSTRAP REACT MYS
A collision happens when two Hash Table elements have the same hash code, because
Cross Validation
that means they belong to the same bucket.
AUC - ROC Curve
K-nearest neighbors Collision can be solved by Chaining by using lists to allow more than one element in the
same bucket.
Python DSA
Python DSA
Lists and Arrays ❮ Previous Sign in to track progress Next ❯
Stacks
Queues
Linked Lists
Hash Tables
Trees
Binary Trees
Binary Search Trees
AVL Trees
Graphs
Linear Search
Binary Search
-->Bubble Sort
PLUS SPACES GET CERTIFIED FOR TEACHERS
Selection Sort
Insertion Sort
FOR BUSINESS CONTACT US
Top Tutorials Top References
HTML Tutorial HTML Reference
CSS Tutorial CSS Reference
JavaScript Tutorial JavaScript Reference
How To Tutorial SQL Reference
SQL Tutorial Python Reference
Python Tutorial [Link] Reference
[Link] Tutorial Bootstrap Reference
Bootstrap Tutorial PHP Reference
PHP Tutorial HTML Colors
Java Tutorial Java Reference
C++ Tutorial AngularJS Reference
jQuery Tutorial jQuery Reference
Top Examples Get Certified
HTML Examples HTML Certificate
CSS Examples CSS Certificate
JavaScript Examples JavaScript Certificate
How To Examples Front End Certificate
SQL Examples SQL Certificate
Python Examples Python Certificate
[Link] Examples PHP Certificate
Bootstrap Examples jQuery Certificate
PHP Examples Java Certificate
Java Examples C++ Certificate
XML Examples C# Certificate
jQuery Examples XML Certificate
FORUM ABOUT ACADEMY
W3Schools is optimized for learning and training. Examples might be simplified to improve reading and learning.
Tutorials, references, and examples are constantly reviewed to avoid errors, but we cannot warrant full correctness
of all content. While using W3Schools, you agree to have read and accepted our terms of use, cookies and privacy policy.
Copyright 1999-2026 by Refsnes Data. All Rights Reserved. W3Schools is Powered by [Link].
[Link] 6/6