哈希表数据结构

哈希表是一种以关联方式存储数据的数据结构。在哈希表中，数据以数组格式存储，每个数据值都有其唯一的索引值。如果我们知道所需数据的索引，则访问数据变得非常快。

因此，它成为一种数据结构，其中插入和搜索操作非常快，而不管数据的大小如何。哈希表使用数组作为存储介质，并使用哈希技术生成要插入元素或从中定位元素的索引。

哈希

哈希是一种将一系列键值转换为数组索引范围的技术。我们将使用取模运算符来获取一系列键值。考虑一个大小为 20 的哈希表的例子，并且要存储以下项目。项目采用 (键，值) 格式。

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

线性探测

正如我们所看到的，哈希技术可能会创建数组中已使用的索引。在这种情况下，我们可以通过查找下一个单元格直到找到空单元格来搜索数组中的下一个空位置。这种技术称为线性探测。

基本操作

以下是哈希表的基本主要操作。

• 搜索 - 在哈希表中搜索元素。

• 插入 - 在哈希表中插入元素。

• 删除 - 从哈希表中删除元素。

数据项

定义一个包含一些数据和键的数据项，根据该键在哈希表中进行搜索。

struct DataItem {
   int data;
   int key;
};

哈希方法

定义一个哈希方法来计算数据项键的哈希码。

int hashCode(int key){
   return key % SIZE;
}

搜索操作

每当要搜索元素时，计算传递的键的哈希码，并使用该哈希码作为数组中的索引来定位元素。如果在计算的哈希码处找不到元素，则使用线性探测来获取前面的元素。

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
	
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

示例

以下是各种编程语言中此操作的实现：

#include <stdio.h>
#define SIZE 10 // Define the size of the hash table
struct DataItem {
    int key;
};
struct DataItem *hashArray[SIZE]; // Define the hash table as an array of DataItem pointers
int hashCode(int key) {
    // Return a hash value based on the key
    return key % SIZE;
}
struct DataItem *search(int key) {
    // get the hash
    int hashIndex = hashCode(key);

    // move in array until an empty slot is found or the key is found
    while (hashArray[hashIndex] != NULL) {
        // If the key is found, return the corresponding DataItem pointer
        if (hashArray[hashIndex]->key == key)
            return hashArray[hashIndex];

        // go to the next cell
        ++hashIndex;

        // wrap around the table
        hashIndex %= SIZE;
    }
    // If the key is not found, return NULL
    return NULL;
}

int main() {

    // Initializing the hash table with some sample DataItems
    struct DataItem item2 = {25}; // Assuming the key is 25
    struct DataItem item3 = {64}; // Assuming the key is 64
    struct DataItem item4 = {22}; // Assuming the key is 22

    // Calculate the hash index for each item and place them in the hash table

    int hashIndex2 = hashCode(item2.key);
    hashArray[hashIndex2] = &item2;
    
    int hashIndex3 = hashCode(item3.key);
    hashArray[hashIndex3] = &item3;

    int hashIndex4 = hashCode(item4.key);
    hashArray[hashIndex4] = &item4;

    // Call the search function to test it
    int keyToSearch = 64; // The key to search for in the hash table
    struct DataItem *result = search(keyToSearch);
    printf("The element to be searched: %d", keyToSearch);
    if (result != NULL) {
        printf("\nElement found");
    } else {
        printf("\nElement not found");
    }

    return 0;
}

The element to be searched: 64
Element found

#include <iostream>
#include <unordered_map>
using namespace std;
#define SIZE 10 // Define the size of the hash table
struct DataItem {
   int key;
};
unordered_map<int, DataItem*> hashMap; // Define the hash table as an unordered_map

int hashCode(int key) {
   // Return a hash value based on the key
   return key % SIZE;
}

DataItem* search(int key) {
   // get the hash
   int hashIndex = hashCode(key);
   
   // move in the map until an empty slot is found or the key is found
   while (hashMap[hashIndex] != nullptr) {
      // If the key is found, return the corresponding DataItem pointer
      if (hashMap[hashIndex]->key == key)
         return hashMap[hashIndex];
      
      // go to the next cell
      ++hashIndex;
      
      // wrap around the table
      hashIndex %= SIZE;
   }
   
   // If the key is not found, return nullptr
   return nullptr;
}

int main() {
   
   // Initializing the hash table with some sample DataItems
   DataItem item2 = {25}; // Assuming the key is 25
   DataItem item3 = {64}; // Assuming the key is 64
   DataItem item4 = {22}; // Assuming the key is 22
   
   // Calculate the hash index for each item and place them in the hash table
   
   int hashIndex2 = hashCode(item2.key);
   hashMap[hashIndex2] = &item2;
   
   int hashIndex3 = hashCode(item3.key);
   hashMap[hashIndex3] = &item3;
   
   int hashIndex4 = hashCode(item4.key);
   hashMap[hashIndex4] = &item4;
   
   // Call the search function to test it
   int keyToSearch = 64; // The key to search for in the hash table
   DataItem* result = search(keyToSearch);
   cout<<"The element to be searched: "<<keyToSearch;
   if (result != nullptr) {
      cout << "\nElement found";
   } else {
      cout << "\nElement not found";
   }
   
   return 0;
}

The element to be searched: 64
Element found

import java.util.HashMap;
public class Main {
   static final int SIZE = 10; // Define the size of the hash table
   static class DataItem {
      int key;
   }
   static HashMap<Integer, DataItem> hashMap = new HashMap<>(); // Define the hash table as a HashMap
   
   static int hashCode(int key) {
      // Return a hash value based on the key
      return key % SIZE;
   }
   static DataItem search(int key) {
      // get the hash
      int hashIndex = hashCode(key);
      
      // move in map until an empty slot is found or the key is found
      while (hashMap.get(hashIndex) != null) {
         // If the key is found, return the corresponding DataItem
         if (hashMap.get(hashIndex).key == key)
            return hashMap.get(hashIndex);
         
         // go to the next cell
         ++hashIndex;
         
         // wrap around the table
         hashIndex %= SIZE;
      }
      
      // If the key is not found, return null
      return null;
   }
public static void main(String[] args) {
   // Initializing the hash table with some sample DataItems
   
   DataItem item2 = new DataItem();
   item2.key = 25; // Assuming the key is 25
   
   DataItem item3 = new DataItem();
   item3.key = 64; // Assuming the key is 64
   DataItem item4 = new DataItem();
   item4.key = 22; // Assuming the key is 22
   // Calculate the hash index for each item and place them in the hash table
   
   int hashIndex2 = hashCode(item2.key);
   hashMap.put(hashIndex2, item2);
   
   int hashIndex3 = hashCode(item3.key);
   hashMap.put(hashIndex3, item3);
   
   int hashIndex4 = hashCode(item4.key);
   hashMap.put(hashIndex4, item4);
   
   // Call the search function to test it
   int keyToSearch = 64; // The key to search for in the hash table
   DataItem result = search(keyToSearch);
   System.out.print("The element to be searched: " + keyToSearch);
      if (result != null) {
         System.out.println("\nElement found");
      } else {
         System.out.println("\nElement not found");
      }
   }
}

The element to be searched: 64
Element found

SIZE = 10 # Define the size of the hash table
class DataItem:
    def __init__(self, key):
        self.key = key
hashMap = {} # Define the hash table as a dictionary
def hashCode(key):
    # Return a hash value based on the key
    return key % SIZE

def search(key):
    # get the hash
    hashIndex = hashCode(key)

    # move in map until an empty slot is found or the key is found
    while hashIndex in hashMap:
        # If the key is found, return the corresponding DataItem
        if hashMap[hashIndex].key == key:
            return hashMap[hashIndex]

        # go to the next cell
        hashIndex = (hashIndex + 1) % SIZE

    # If the key is not found, return None
    return None
# Initializing the hash table with some sample DataItems
item2 = DataItem(25) # Assuming the key is 25
item3 = DataItem(64) # Assuming the key is 64
item4 = DataItem(22) # Assuming the key is 22
# Calculate the hash index for each item and place them in the hash table
hashIndex2 = hashCode(item2.key)
hashMap[hashIndex2] = item2

hashIndex3 = hashCode(item3.key)
hashMap[hashIndex3] = item3

hashIndex4 = hashCode(item4.key)
hashMap[hashIndex4] = item4

# Call the search function to test it
keyToSearch = 64 # The key to search for in the hash table
result = search(keyToSearch)
print("The element to be searched: ", keyToSearch)
if result:
    print("Element found")
else:
    print("Element not found")

The element to be searched:  64
Element found

插入操作

每当要插入元素时，计算传递的键的哈希码，并使用该哈希码作为数组中的索引来定位索引。如果在计算的哈希码处找到元素，则使用线性探测来查找空位置。

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

示例

以下是各种编程语言中此操作的实现：

#include <stdio.h>
#include <stdlib.h>
#define SIZE 4 // Define the size of the hash table
struct DataItem {
    int key;
};
struct DataItem *hashArray[SIZE]; // Define the hash table as an array of DataItem pointers
int hashCode(int key) {
    // Return a hash value based on the key
    return key % SIZE;
}
void insert(int key) {
   // Create a new DataItem using malloc
   struct DataItem *newItem = (struct DataItem*)malloc(sizeof(struct DataItem));
   
   if (newItem == NULL) {
      // Check if malloc fails to allocate memory
      fprintf(stderr, "Memory allocation error\n");
      return;
   }
   
   newItem->key = key;
   // Initialize other data members if needed
   
   // Calculate the hash index for the key
   int hashIndex = hashCode(key);
   
   // Handle collisions (linear probing)
   while (hashArray[hashIndex] != NULL) {
      // Move to the next cell
      ++hashIndex;
      // Wrap around the table if needed
      hashIndex %= SIZE;
   }
   
   // Insert the new DataItem at the calculated index
   hashArray[hashIndex] = newItem;
}
int main() {
   // Call the insert function with different keys to populate the hash table
   insert(42); // Insert an item with key 42
   insert(25); // Insert an item with key 25
   insert(64); // Insert an item with key 64
   insert(22); // Insert an item with key 22
   
   // Output the populated hash table
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != NULL) {
         printf("Index %d: Key %d\n", i, hashArray[i]->key);
      } else {
         printf("Index %d: Empty\n", i);
      }
   }
   
   return 0;
}

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

#include <iostream>
#include <vector>
#define SIZE 4 // Define the size of the hash table

struct DataItem {
   int key;
};
std::vector<DataItem*> hashArray(SIZE, nullptr); // Define the hash table as a vector of DataItem pointers
int hashCode(int key)
{
   // Return a hash value based on the key
   return key % SIZE;
}
void insert(int key)
{
   // Create a new DataItem using new (dynamic memory allocation)
   DataItem *newItem = new DataItem;
   
   newItem->key = key;
   // Initialize other data members if needed
   
   // Calculate the hash index for the key
   int hashIndex = hashCode(key);
   
   // Handle collisions (linear probing)
   while (hashArray[hashIndex] != nullptr) {
      // Move to the next cell
      ++hashIndex;
      // Wrap around the table if needed
      hashIndex %= SIZE;
   }
   
   // Insert the new DataItem at the calculated index
   hashArray[hashIndex] = newItem;
}

int main()
{
   // Call the insert function with different keys to populate the hash table
   
   insert(42); // Insert an item with key 42
   insert(25); // Insert an item with key 25
   insert(64); // Insert an item with key 64
   insert(22); // Insert an item with key 22
   
   // Output the populated hash table
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != nullptr) {
         std::cout << "Index " << i << ": Key " << hashArray[i]->key << std::endl;
      } else {
         std::cout << "Index " << i << ": Empty" << std::endl;
      }
   }
   return 0;
}

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

import java.util.Arrays;
public class Main {
   static final int SIZE = 4; // Define the size of the hash table
   static class DataItem {
      int key;
   }
   static DataItem[] hashArray = new DataItem[SIZE]; // Define the hash table as an array of DataItem pointers
   static int hashCode(int key) {
      // Return a hash value based on the key
      return key % SIZE;
   }
   static void insert(int key) {
      // Create a new DataItem
      DataItem newItem = new DataItem();
      newItem.key = key;
      // Initialize other data members if needed
      
      // Calculate the hash index for the key
      int hashIndex = hashCode(key);
      
      // Handle collisions (linear probing)
      while (hashArray[hashIndex] != null) {
         // Move to the next cell
         hashIndex++;
         // Wrap around the table if needed
         hashIndex %= SIZE;
      }
      // Insert the new DataItem at the calculated index
      hashArray[hashIndex] = newItem;
   }
public static void main(String[] args) {
   // Call the insert function with different keys to populate the hash table
   insert(42); // Insert an item with key 42
   insert(25); // Insert an item with key 25
   insert(64); // Insert an item with key 64
   insert(22); // Insert an item with key 22
   // Output the populated hash table
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != null) {
         System.out.println("Index " + i + ": Key " + hashArray[i].key);
      } else {
         System.out.println("Index " + i + ": Empty");
      }
   }
   }
}

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

SIZE = 4  # Define the size of the hash table
class DataItem:
    def __init__(self, key):
        self.key = key
hashArray = [None] * SIZE  # Define the hash table as a list of DataItem pointers
def hashCode(key):
    # Return a hash value based on the key
    return key % SIZE

def insert(key):
    # Create a new DataItem
    newItem = DataItem(key)
    # Initialize other data members if needed
    # Calculate the hash index for the key
    hashIndex = hashCode(key)
    # Handle collisions (linear probing)
    while hashArray[hashIndex] is not None:
        # Move to the next cell
        hashIndex += 1
        # Wrap around the table if needed
        hashIndex %= SIZE

    # Insert the new DataItem at the calculated index
    hashArray[hashIndex] = newItem
# Call the insert function with different keys to populate the hash table
insert(42)  # Insert an item with key 42
insert(25)  # Insert an item with key 25
insert(64)  # Insert an item with key 64
insert(22)  # Insert an item with key 22
# Output the populated hash table
for i in range(SIZE):
    if hashArray[i] is not None:
        print(f"Index {i}: Key {hashArray[i].key}")
    else:
        print(f"Index {i}: Empty")

Index 0: Key 64
Index 1: Key 25
Index 2: Key 42
Index 3: Key 22

删除操作

每当要删除元素时，计算传递的键的哈希码，并使用该哈希码作为数组中的索引来定位索引。如果在计算的哈希码处找不到元素，则使用线性探测来获取前面的元素。找到后，在那里存储一个虚拟项以保持哈希表的性能完整。

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
   return NULL;        
}

示例

以下是各种编程语言中哈希表删除操作的实现：

#include <stdio.h>
#include <stdlib.h>
#define SIZE 5 // Define the size of the hash table
struct DataItem {
   int key;
};
struct DataItem *hashArray[SIZE]; // Define the hash table as an array of DataItem pointers

int hashCode(int key) {
   // Implement your hash function here
   // Return a hash value based on the key
}
void insert(int key) {
   // Create a new DataItem using malloc
   struct DataItem *newItem = (struct DataItem*)malloc(sizeof(struct DataItem));
   if (newItem == NULL) {
      // Check if malloc fails to allocate memory
      fprintf(stderr, "Memory allocation error\n");
      return;
   }
   
   newItem->key = key;
   // Initialize other data members if needed
   
   // Calculate the hash index for the key
   int hashIndex = hashCode(key);
   
   // Handle collisions (linear probing)
   while (hashArray[hashIndex] != NULL) {
      // Move to the next cell
      ++hashIndex;
      // Wrap around the table if needed
      hashIndex %= SIZE;
   }
   
   // Insert the new DataItem at the calculated index
   hashArray[hashIndex] = newItem;
   
   // Print the inserted item's key and hash index
   printf("Inserted key %d at index %d\n", newItem->key, hashIndex);
}
void delete(int key) {
   // Find the item in the hash table
   int hashIndex = hashCode(key);
   while (hashArray[hashIndex] != NULL) {
      if (hashArray[hashIndex]->key == key) {
         // Mark the item as deleted (optional: free memory)
         free(hashArray[hashIndex]);
         hashArray[hashIndex] = NULL;
         return;
      }
      // Move to the next cell
      ++hashIndex;
      // Wrap around the table if needed
      hashIndex %= SIZE;
   }
   // If the key is not found, print a message
   printf("Item with key %d not found.\n", key);
}
int main() {
   // Call the insert function with different keys to populate the hash table
   printf("Hash Table Contents before deletion:\n");
   insert(1); // Insert an item with key 42
   insert(2); // Insert an item with key 25
   insert(3); // Insert an item with key 64
   insert(4); // Insert an item with key 22
   int ele1 = 2;
   int ele2 = 4;
   printf("The key to be deleted: %d and %d", ele1, ele2);
   delete(ele1); // Delete an item with key 42
   delete(ele2); // Delete an item with key 25
   // Print the hash table's contents after delete operations
   printf("\nHash Table Contents after deletion:\n");
   for (int i = 1; i < SIZE; i++) {
      if (hashArray[i] != NULL) {
         printf("Index %d: Key %d\n", i, hashArray[i]->key);
      } else {
         printf("Index %d: Empty\n", i);
      }
   }
   return 0;
}

Hash Table Contents before deletion:
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The key to be deleted: 2 and 4
Hash Table Contents after deletion:
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

#include <iostream>
using namespace std;
const int SIZE = 5; // Define the size of the hash table
struct DataItem {
   int key;
};
struct DataItem* hashArray[SIZE]; // Define the hash table as an array of DataItem pointers

int hashCode(int key) {
   // Implement your hash function here
   // Return a hash value based on the key
   
   // A simple hash function (modulo division)
   return key % SIZE;
}

void insert(int key) {
   // Create a new DataItem using new
   struct DataItem* newItem = new DataItem;
   newItem->key = key;
   // Initialize other data members if needed
   // Calculate the hash index for the key
   int hashIndex = hashCode(key);
   // Handle collisions (linear probing)
   while (hashArray[hashIndex] != nullptr) {
      // Move to the next cell
      ++hashIndex;
      // Wrap around the table if needed
      hashIndex %= SIZE;
   }
   // Insert the new DataItem at the calculated index
   hashArray[hashIndex] = newItem;
   // Print the inserted item's key and hash index
   cout << "Inserted key " << newItem->key << " at index " << hashIndex << endl;
}
void deleteItem(int key) {
   // Find the item in the hash table
   int hashIndex = hashCode(key);
   while (hashArray[hashIndex] != nullptr) {
      if (hashArray[hashIndex]->key == key) {
         // Mark the item as deleted (optional: free memory)
         delete hashArray[hashIndex];
         hashArray[hashIndex] = nullptr;
         return;
      }
      // Move to the next cell
      ++hashIndex;
      // Wrap around the table if needed
      hashIndex %= SIZE;
   }
   // If the key is not found, print a message
   cout << "Item with key " << key << " not found." << endl;
}
int main() {
   // Call the insert function with different keys to populate the hash table
   cout<<"Hash Table Contents before deletion:\n";
   insert(1); // Insert an item with key 42
   insert(2); // Insert an item with key 25
   insert(3); // Insert an item with key 64
   insert(4); // Insert an item with key 22
   int ele1 = 2;
   int ele2 = 4;
   cout<<"The key to be deleted: "<<ele1<<" and "<<ele2<<"\n";
   deleteItem(2); // Delete an item with key 42
   deleteItem(4); // Delete an item with key 25
   cout<<"Hash Table Contents after deletion:\n";
   // Print the hash table's contents after delete operations
   for (int i = 1; i < SIZE; i++) {
      if (hashArray[i] != nullptr) {
         cout << "Index " << i << ": Key " << hashArray[i]->key << endl;
      } else {
         cout << "Index " << i << ": Empty" << endl;
      }
   }
   return 0;
}

Hash Table Contents before deletion:
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The key to be deleted: 2 and 4
Hash Table Contents after deletion:
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

public class Main {
   static final int SIZE = 5; // Define the size of the hash table
   static class DataItem {
      int key;
      DataItem(int key) {
         this.key = key;
      }
   }
   static DataItem[] hashArray = new DataItem[SIZE]; // Define the hash table as an array of DataItem objects
   static int hashCode(int key) {
      // Implement your hash function here
      // Return a hash value based on the key
      return key % SIZE; // A simple hash function using modulo operator
   }
   static void insert(int key) {
      // Calculate the hash index for the key
      int hashIndex = hashCode(key);
      // Handle collisions (linear probing)
      while (hashArray[hashIndex] != null) {
         // Move to the next cell
         hashIndex = (hashIndex + 1) % SIZE;
      }
      
      // Insert the new DataItem at the calculated index
      hashArray[hashIndex] = new DataItem(key);
      
      // Print the inserted item's key and hash index
      System.out.println("Inserted key " + key + " at index " + hashIndex);
   }
   static void delete(int key) {
      // Find the item in the hash table
      int hashIndex = hashCode(key);
      while (hashArray[hashIndex] != null) {
         if (hashArray[hashIndex].key == key) {
            // Mark the item as deleted (optional: free memory)
            hashArray[hashIndex] = null;
            
            // Print the deleted item's key and hash index
            return;
         }
         // Move to the next cell
         hashIndex = (hashIndex + 1) % SIZE;
      }
      // If the key is not found, print a message
      System.out.println("Item with key " + key + " not found.");
   }
public static void main(String[] args) {
   // Call the insert function with different keys to populate the hash table
   System.out.println("Hash Table Contents before deletion: ");
   insert(1); // Insert an item with key 1
   insert(2); // Insert an item with key 2
   insert(3); // Insert an item with key 3
   insert(4); // Insert an item with key 4
   int ele1 = 2;
   int ele2 = 4;
   System.out.print("The keys to be deleted: " + ele1 + " and " + ele2);
   delete(ele1); // Delete an item with key 2
   delete(ele2); // Delete an item with key 4
   // Print the hash table's contents after delete operations
   System.out.println("\nHash Table Contents after deletion:");
   for (int i = 1; i < SIZE; i++) {
      if (hashArray[i] != null) {
         System.out.println("Index " + i + ": Key " + hashArray[i].key);
      } else {
        System.out.println("Index " + i + ": Empty");
      }
     }
   }
}

Hash Table Contents before deletion: 
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The keys to be deleted: 2 and 4
Hash Table Contents after deletion:
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

SIZE = 5  # Define the size of the hash table

class DataItem:
    def __init__(self, key):
        self.key = key

def hashCode(key):
    # Implement your hash function here
    # Return a hash value based on the key
    return key % SIZE

def insert(key):
    global hashArray  # Access the global hashArray variable
    # Calculate the hash index for the key
    hashIndex = hashCode(key)

    # Handle collisions (linear probing)
    while hashArray[hashIndex] is not None:
        # Move to the next cell
        hashIndex = (hashIndex + 1) % SIZE

    # Insert the new DataItem at the calculated index
    hashArray[hashIndex] = DataItem(key)

    # Print the inserted item's key and hash index
    print(f"Inserted key {key} at index {hashIndex}")

def delete(key):
    global hashArray  # Access the global hashArray variable
    # Find the item in the hash table
    hashIndex = hashCode(key)
    while hashArray[hashIndex] is not None:
        if hashArray[hashIndex].key == key:
            # Mark the item as deleted (optional: free memory)
            hashArray[hashIndex] = None
            return
        # Move to the next cell
        hashIndex = (hashIndex + 1) % SIZE

    # If the key is not found, print a message
    print(f"Item with key {key} not found.")

# Initialize the hash table as a list of None values
hashArray = [None] * SIZE
print("Hash Table Contents before deletion:")
# Call the insert function with different keys to populate the hash table
insert(1)  # Insert an item with key 1
insert(2)  # Insert an item with key 2
insert(3)  # Insert an item with key 3
insert(4)  # Insert an item with key 4
ele1 = 2
ele2 = 4
print("The keys to be deleted: ", ele1, " and ", ele2)
delete(2)  # Delete an item with key 2
delete(4)  # Delete an item with key 4

# Print the hash table's contents after delete operations
print("Hash Table Contents after deletion:")
for i in range(1, SIZE):
    if hashArray[i] is not None:
        print(f"Index {i}: Key {hashArray[i].key}")
    else:
        print(f"Index {i}: Empty")

Hash Table Contents before deletion:
Inserted key 1 at index 1
Inserted key 2 at index 2
Inserted key 3 at index 3
Inserted key 4 at index 4
The keys to be deleted:  2  and  4
Hash Table Contents after deletion:
Index 1: Key 1
Index 2: Empty
Index 3: Key 3
Index 4: Empty

完整实现

以下是各种编程语言中上述操作的完整实现：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define SIZE 20
struct DataItem {
   int data;   
   int key;
};
struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key) {
   return key % SIZE;
}
struct DataItem *search(int key) {
   //get the hash 
   int hashIndex = hashCode(key);  
	
   //move in array until an empty 
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }        
   return NULL;        
}
void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;	
      //wrap around the table
      hashIndex %= SIZE;
   }
   hashArray[hashIndex] = item;
}
struct DataItem* delete(struct DataItem* item) {
   int key = item->key;
   //get the hash 
   int hashIndex = hashCode(key);
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 		
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }	
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }      	
   return NULL;        
}
void display() {
   int i = 0;
	
   for(i = 0; i<SIZE; i++) {
      if(hashArray[i] != NULL)
         printf("(%d,%d) ",hashArray[i]->key,hashArray[i]->data);
   }
	
   printf("\n");
}
int main() {
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;  
   dummyItem->key = -1; 
   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);
   printf("Insertion done: \n");
   printf("Contents of Hash Table: ");
   display();
   int ele = 37;
   printf("The element to be searched: %d", ele);
   item = search(ele);
   if(item != NULL) {
      printf("\nElement found: %d\n", item->key);
   } else {
      printf("\nElement not found\n");
   }
   delete(item);
   printf("Hash Table contents after deletion: ");
   display();
}

Insertion done: 
Contents of Hash Table: (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (37,97) 
The element to be searched: 37
Element found: 37
Hash Table contents after deletion: (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (-1,-1) 

#include <iostream>
#include <vector>
using namespace std;
using namespace std;
#define SIZE 20
struct DataItem {
   int data;
   int key;
};
std::vector<DataItem*> hashArray(SIZE, nullptr);
DataItem* dummyItem;
DataItem* item;
int hashCode(int key) {
   return key % SIZE;
}
DataItem* search(int key) {
   //get the hash 
   int hashIndex = hashCode(key);
   //move in array until an empty 
   while (hashArray[hashIndex] != nullptr) {
      if (hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
         //go to next cell
         //wrap around the table
      hashIndex = (hashIndex + 1) % SIZE;
   }
   return nullptr;
}
void insert(int key, int data) {
   DataItem* item = new DataItem;
   item->data = data;
   item->key = key;
    //get the hash 
   int hashIndex = hashCode(key);
   //move in array until an empty or deleted cell
   while (hashArray[hashIndex] != nullptr && hashArray[hashIndex]->key != -1) {
      hashIndex = (hashIndex + 1) % SIZE;
   }
   hashArray[hashIndex] = item;
}
DataItem* deleteItem(DataItem* item) {
   int key = item->key;
   int hashIndex = hashCode(key);
   while (hashArray[hashIndex] != nullptr) {
      if (hashArray[hashIndex]->key == key) {
         DataItem* temp = hashArray[hashIndex];
         hashArray[hashIndex] = dummyItem;
         return temp;
      }
      hashIndex = (hashIndex + 1) % SIZE;
   }
   return nullptr;
}
void display() {
   for (int i = 0; i < SIZE; i++) {
      if (hashArray[i] != nullptr)
         cout << " (" << hashArray[i]->key << "," << hashArray[i]->data << ")";
   }
   cout << std::endl;
}
int main() {
   dummyItem = new DataItem;
   dummyItem->data = -1;
   dummyItem->key = -1;
   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);
   cout<<"Insertion Done";
   cout<<"\nContents of Hash Table: ";
   display();
   int ele = 37;
   cout<<"The element to be searched: "<<ele;
   item = search(ele);
   if (item != nullptr) {
      cout << "\nElement found: " << item->key;
   } else {
      cout << "\nElement not found" << item->key;
   }
   // Clean up allocated memory
   delete(item);
   cout<<"\nHash Table contents after deletion: ";
   display();
}

Insertion Done
Contents of Hash Table:  (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (37,97)
The element to be searched: 37
Element found: 37
Hash Table contents after deletion:  (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (5,1666768001)

public class HashTableExample {
   static final int SIZE = 20;
   static class DataItem {
      int data;
      int key;
      DataItem(int data, int key) {
         this.data = data;
         this.key = key;
      }
   }
   static DataItem[] hashArray = new DataItem[SIZE];
   static DataItem dummyItem = new DataItem(-1, -1);
   static DataItem item;
   static int hashCode(int key) {
      return key % SIZE;
   }
   static DataItem search(int key) {
      int hashIndex = hashCode(key);
      
      while (hashArray[hashIndex] != null) {
         if (hashArray[hashIndex].key == key)
            return hashArray[hashIndex];
         
         hashIndex = (hashIndex + 1) % SIZE;
      }
      return null;
   }
   static void insert(int key, int data) {
       DataItem item = new DataItem(data, key);
       int hashIndex = hashCode(key);
   
       while (hashArray[hashIndex] != null && hashArray[hashIndex].key != -1) {
           hashIndex = (hashIndex + 1) % SIZE;
       }
       hashArray[hashIndex] = item;
   }
   static DataItem deleteItem(DataItem item) {
      int key = item.key;
      int hashIndex = hashCode(key);
      while (hashArray[hashIndex] != null) {
          if (hashArray[hashIndex].key == key) {
              DataItem temp = hashArray[hashIndex];
              hashArray[hashIndex] = dummyItem;
              return temp;
          }
      
          hashIndex = (hashIndex + 1) % SIZE;
      }
      return null;
   }
   static void display() {
      for (int i = 0; i < SIZE; i++) {
         if (hashArray[i] != null)
            System.out.print(" (" + hashArray[i].key + "," + hashArray[i].data + ")");
      }
      System.out.println();
   }
public static void main(String[] args) {
   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);
   System.out.print("Insertion done");
   System.out.print("\nContents of Hash Table:");
   display();
   int ele = 37;
   System.out.print("The element to be searched: " + ele);
   item = search(37);
   
   if (item != null) {
      System.out.println("\nElement found: " + item.key);
   } else {
      System.out.println("\nElement not found");
   }
   deleteItem(item);
   System.out.print("Hash Table contents after deletion:");
   display();
   }
}

Insertion done
Contents of Hash Table: (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (37,97)
The element to be searched: 37
Element found: 37
Hash Table contents after deletion: (1,20) (2,70) (42,80) (4,25) (12,44) (13,78) (14,32) (17,11) (-1,-1)

SIZE = 20
class DataItem:
    def __init__(self, data, key):
        self.data = data
        self.key = key
# Initialize the hash array with None values
hashArray = [None] * SIZE
# Create a dummy item to mark deleted cells in the hash table
dummyItem = DataItem(-1, -1)
# Variable to hold the item found in the search operation
item = None
# Hash function to calculate the hash index for the given key
def hashCode(key):
    return key % SIZE
# Function to search for an item in the hash table by its key
def search(key):
    # Calculate the hash index using the hash function
    hashIndex = hashCode(key)
    # Traverse the array until an empty cell is encountered
    while hashArray[hashIndex] is not None:
        if hashArray[hashIndex].key == key:
            # Item found, return the item
            return hashArray[hashIndex]
        # Move to the next cell (linear probing)
        hashIndex = (hashIndex + 1) % SIZE

    # If the loop terminates without finding the item, it means the item is not present
    return None
# Function to insert an item into the hash table
def insert(key, data):
    # Create a new DataItem object
    item = DataItem(data, key)
    # Calculate the hash index using the hash function
    hashIndex = hashCode(key)
    # Handle collisions using linear probing (move to the next cell until an empty cell is found)
    while hashArray[hashIndex] is not None and hashArray[hashIndex].key != -1:
        hashIndex = (hashIndex + 1) % SIZE
    # Insert the item into the hash table at the calculated index
    hashArray[hashIndex] = item
# Function to delete an item from the hash table
def deleteItem(item):
    key = item.key
    # Calculate the hash index using the hash function
    hashIndex = hashCode(key)
    # Traverse the array until an empty or deleted cell is encountered
    while hashArray[hashIndex] is not None:
        if hashArray[hashIndex].key == key:
            # Item found, mark the cell as deleted by replacing it with the dummyItem
            temp = hashArray[hashIndex]
            hashArray[hashIndex] = dummyItem
            return temp
        # Move to the next cell (linear probing)
        hashIndex = (hashIndex + 1) % SIZE

    # If the loop terminates without finding the item, it means the item is not present
    return None
# Function to display the hash table
def display():
    for i in range(SIZE):
        if hashArray[i] is not None:
            # Print the key and data of the item at the current index
            print(" ({}, {})".format(hashArray[i].key, hashArray[i].data), end="")
        else:
            # Print ~~ for an empty cell
            print(" ~~ ", end="")
    print()
if __name__ == "__main__":
    # Test the hash table implementation
    # Insert some items into the hash table
    insert(1, 20)
    insert(2, 70)
    insert(42, 80)
    insert(4, 25)
    insert(12, 44)
    insert(14, 32)
    insert(17, 11)
    insert(13, 78)
    insert(37, 97)
	print("Insertion done")
	print("Hash Table contents: ");
    # Display the hash table
    display()
    display()
    # Search for an item with a specific key (37)
    item = search(37)

    # Check if the item was found or not and print the result
    if item is not None:
        print("Element found:", item.data)
    else:
        print("Element not found")

    # Delete the item with key 37 from the hash table
    deleteItem(item)

    # Search again for the item with key 37 after deletion
    item = search(37)

    # Check if the item was found or not and print the result
    if item is not None:
        print("Element found:", item.data)
    else:
        print("Element not found")

~~  (1, 20) (2, 70) (42, 80) (4, 25) ~~  ~~  ~~  ~~  ~~  ~~  ~~  (12, 44) (13, 78) (14, 32) ~~  ~~  (17, 11) (37, 97) ~~ 
Element found: 97
Element not found