用拉链法实现哈希表

In the previous article Core Principles of Hash Tables, I introduced the core principles and several key concepts of hash tables. It mentioned that there are two main methods to resolve hash collisions: the chaining method and open addressing (also known as linear probing):

This article will specifically introduce the implementation principles and code for the chaining method.

First, I will use a visual panel to implement a simplified version of a hash table using the chaining method. This will help you intuitively understand how the chaining method implements the CRUD (Create, Read, Update, Delete) APIs and resolves hash collisions. Finally, I will provide a more complete Java code implementation.

Simplified Implementation of the Chaining Method

The Core Principles of Hash Tables article has already introduced the relationship between the hash function and the type of key, where the role of the hash function is to convert the key into an array index in O(1) time, and the key can be of any immutable type.

However, for ease of understanding, I will make the following simplifications:

1. The hash table we implement only supports key of type int and value of type int. If the key does not exist, it returns -1.

2. Our hash function is simply the modulo operation, i.e., 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) have a value of 1.

3. The size of the underlying table array is fixed when the hash table is created. We do not consider load factor and dynamic resizing.

These simplifications help us focus on the core logic of CRUD operations and can be aided by the visual panel to assist in your understanding.

Simplified Code Version

Visual Panel for Displaying CRUD Operations

Complete Code Implementation

loading...