使用 Java 的 DSA - 哈希表

概述

HashTable 是一种数据结构，无论哈希表的大小如何，插入和搜索操作都非常快。它几乎是一个常数或 O(1)。哈希表使用数组作为存储介质，并使用哈希技术生成要插入元素或从中定位元素的索引。

哈希

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

• (1,20)

• (2,70)

• (42,80)

• (4,25)

• (12,44)

• (14,32)

• (17,11)

• (13,78)

• (37,98)

线性探测

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

基本操作

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

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

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

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

DataItem

定义一个具有一些数据的数据项，以及在哈希表中进行搜索所基于的键。

public class DataItem {
   private int key;
   private int data;

   public DataItem(int key, int data){
      this.key = key;
      this.data = data;
   }

   public int getKey(){
      return key;
   }

   public int getData(){
      return data;
   }   
}

哈希方法

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

public int hashCode(int key){
    return key % size;
}

搜索操作

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

public DataItem search(int key){
    //获取哈希值
    int hashIndex = hashCode(key);
    //在数组中移动直到为空
    while(hashArray[hashIndex] !=null){
        if(hashArray[hashIndex].getKey() == key)
        return hashArray[hashIndex];
        //转到下一个单元格
        ++hashIndex;
        //环绕表格
        hashIndex %= size;
    }
    return null;
}

插入操作

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

public void insert(DataItem item){
    int key = item.getKey();
    
    //获取哈希值
    int hashIndex = hashCode(key);
    
    //在数组中移动直到单元格为空或已删除
    while(hashArray[hashIndex] !=null
    && hashArray[hashIndex].getKey() != -1){
        //转到下一个单元格
        ++hashIndex;
        //环绕表格
        hashIndex %= size;
    }
    
    hashArray[hashIndex] = item;
}

删除操作

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

public DataItem delete(DataItem item){
    int key = item.getKey();
    
    //获取哈希值
    int hashIndex = hashCode(key);
    
    //在数组中移动直到为空
    while(hashArray[hashIndex] !=null){
        if(hashArray[hashIndex].getKey() == key){
            DataItem temp = hashArray[hashIndex];
            //在已删除的位置分配一个虚拟项
            hashArray[hashIndex] = dummyItem;
            return temp;
        }
        //转到下一个单元格
        ++hashIndex;
        //环绕表格
        hashIndex %= size;
    }
    return null;   
}

HashTable 实现

DataItem.java

package com.tutorialspoint.datastructure;

public class DataItem {
   private int key;
   private int data;

   public DataItem(int key, int data){
      this.key = key;
      this.data = data;
   }

   public int getKey(){
      return key;
   }

   public int getData(){
      return data;
   }   
}

HashTable.java

package com.tutorialspoint.datastructure;

public class HashTable {
    
   private DataItem[] hashArray;    
   private int size;
   private DataItem dummyItem;

   public HashTable(int size){
      this.size = size;
      hashArray = new DataItem[size];
      dummyItem = new DataItem(-1,-1);
   }

   public void display(){
      for(int i=0; i<size; i++) {
         if(hashArray[i] != null)
            System.out.print(" ("
               +hashArray[i].getKey()+","
               +hashArray[i].getData() + ") ");
         else
            System.out.print(" ~~ ");
      }
      System.out.println("");
   }
   
   public int hashCode(int key){
      return key % size;
   }

    public DataItem search(int key){
        //获取哈希值
        int hashIndex = hashCode(key);
        //在数组中移动直到为空
        while(hashArray[hashIndex] !=null){
            if(hashArray[hashIndex].getKey() == key)
            return hashArray[hashIndex];
            //转到下一个单元格
            ++hashIndex;
            //环绕表格
            hashIndex %= size;
        }
        return null;
    }
  
    public void insert(DataItem item){
        int key = item.getKey();
        
        //获取哈希值
        int hashIndex = hashCode(key);
        
        //在数组中移动直到单元格为空或已删除
        while(hashArray[hashIndex] !=null
        && hashArray[hashIndex].getKey() != -1){
            //转到下一个单元格
            ++hashIndex;
            //环绕表格
            hashIndex %= size;
        }
        
        hashArray[hashIndex] = item;
    }

    public DataItem delete(DataItem item){
        int key = item.getKey();
        
        //获取哈希值
        int hashIndex = hashCode(key);
        
        //在数组中移动直到为空
        while(hashArray[hashIndex] !=null){
            if(hashArray[hashIndex].getKey() == key){
                DataItem temp = hashArray[hashIndex];
                //在已删除的位置分配一个虚拟项
                hashArray[hashIndex] = dummyItem;
                return temp;
            }
            //转到下一个单元格
            ++hashIndex;
            //环绕表格
            hashIndex %= size;
        }
        return null;
    }
}

演示程序

HashTableDemo.java

package com.tutorialspoint.datastructure;

public class HashTableDemo {
   public static void main(String[] args){
      HashTable hashTable = new HashTable(20);

      hashTable.insert(new DataItem(1, 20));
      hashTable.insert(new DataItem(2, 70));
      hashTable.insert(new DataItem(42, 80));
      hashTable.insert(new DataItem(4, 25));
      hashTable.insert(new DataItem(12, 44));
      hashTable.insert(new DataItem(14, 32));
      hashTable.insert(new DataItem(17, 11));
      hashTable.insert(new DataItem(13, 78));
      hashTable.insert(new DataItem(37, 97));

      hashTable.display();

      DataItem item = hashTable.search(37);

      if(item != null){
         System.out.println("Element found: "+ item.getData());
      }else{
         System.out.println("Element not found");
      }

      hashTable.delete(item);
	
      item = hashTable.search(37);

      if(item != null){
         System.out.println("Element found: "+ item.getData());
      }else{
         System.out.println("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