LeetCode Study Notes - Hash Table Hash Table - Concept Introduction

Github link

1. What is Hash Table?

• Hash table, also known as hash table
• According to the key value (Key), and through the Hash Function to query the data structure in the memory storage location
• In fact, it is a technology for data storage and access.
• It consists of pairs of (key, value). In Python, it is usually implemented using a dictionary. One key corresponds to one value, and there will not be multiple keys with the same name at the same time.
• Mainly composed of Keys, Hash Function and Hash Table, Hash Table is composed of N buckets, and each bucket is composed of M Slots, each Slot can access a piece of data

2. Implementation process (as shown below):

When we want to get the value of Jack ( Keys ), we need to calculate the Hashing Address (or Home Address) through the Hash Function, and then find the corresponding Bucket in the Hash Table to get the basketball ( values )

3. Advantages of Hash Table

• Main advantages: The time complexity of executing insert/search/delete/modify is O(1), that is, it is super fast regardless of the amount of data

( But when Hash Collision occurs, the above advantages do not hold )

• Data has nothing to do with the sorting order, so when searching for data, it does not need to be sorted in advance
• Since there is a Hash Function in the middle, it is difficult to obtain Data without knowing what operation it does, so the security and confidentiality are very high

4. Application Scope of Hash Table

• The data itself has nothing to do with the order in which it is arranged
• There is no repeated access to the value (ex. Jack is the corresponding basketball)
• Or when it is necessary to count the number of times in a repetitive situation, like today Jack may have taken several basketballs from the gym, we are going to count how many times he has taken it.
• When you need to quickly access DATA in O(1) time complexity

5. What is Hash Collision?

Different pieces of data, such as (a, b), get the same Hashing Address after the calculation of the intermediate Hash Function, that is, H(a) = H(b)

6. How to operate Dictionary in Python

• Create a dictionary: {} or dict()

 ## create dictionary python_dict = {'x': 1, 'y': 4}
python_dict
{'x': 1, 'y': 4}

• insert:

 ## Insert new data python_dict['z'] = 10
python_dict
{'x': 1, 'y': 4, 'z': 10}

• Access value:

 ## Access data print(python_dict.get('z'))
print(python_dict['z'])
10
10

• delete:

 ## delete a set of data del python_dict['z']
python_dict
{'x': 1, 'y': 4}

• Check if a key exists in the dictionary

 ## First method print(python_dict.__contains__('z'))
## The second method print('x' in python_dict)
false
True

• Get a set of keys and values: for k, v in python_dict.items():

 ## Get a group of keys and values
for k, v in python_dict.items():
print(k)
print(v)
x
1
y
4

Reference

Since this article is based on the courses I have learned and online resources, and then comes from my own digestion, if there is something the original author thinks is inappropriate, please contact me immediately, I will remove it immediately, thank you

https://hiskio.com/courses/319/lectures/15376

https://en.wikipedia.org/wiki/Hashtable

https://blog.kennycoder.io/2020/02/18/Notes on Data Structure and Algorithm-Hashing-Introduction to Hash Principle/