线性探查法的两种代码实现

In the previous article Core Principles of Hash Tables, I introduced the core principles and key concepts of hash tables. In Principles and Implementation of the Chaining Method, I discussed the implementation of the chaining method. The article Two Difficulties of Linear Probing covered the challenges of implementing hash tables using linear probing and provided two solutions for handling empty slots when deleting elements. This article will provide reference code implementations for both methods.

We will first present a simplified implementation using a visual panel to help you understand the processes of adding, deleting, searching, and updating elements. Finally, we will provide a complete implementation.

In the simplified implementation, the specific simplifications are as follows:

1. Our hash table only supports key and value types of int. If the key does not exist, it returns -1.

2. Our hash function is simply the modulo operation: hash(key) = key % table.length. This also makes it easy to simulate hash collisions. For example, when table.length = 10, both hash(1) and hash(11) will equal 1.

3. The size of the underlying table array is fixed when the hash table is created. We assume the table array will not be fully occupied and do not consider load factors or dynamic resizing.

These simplifications help us focus on the core logic of adding, deleting, searching, and updating elements. You can also use the visual panel to aid your understanding.

Simplified Code

Linear Probing for Data Relocation

Linear Probing with Special Placeholder

Complete Code

Rehash Version

Sentinel Value Version

loading...