哈希表的java实现

分手后的思念是犯贱 2022-07-11 05:38 150阅读 0赞

一、为什么要用哈希表

树的操作通常需要O(N)的时间级，而哈希表中无论存有多少数据，它的插入和查找（有时包括删除）只需要接近常量级的时间，即O(1)的时间级。

但是哈希表也有一定的缺点：它是基于数组的，数组创建后难以扩展。而某些哈希表在基本填满时，性能下降明显，所以事先必须清楚哈希表中将要存储多少数据。而且目前没有一种简便的方法可以对哈希表进行有序（从大到小或者从小到大）的遍历，除非哈希表本身是有序的，但事实上这是违背哈希原则的。

综合以上：当不需要有序遍历数据，而且可以提前预测需要存储的数据项的数目，使用哈希表的结构是十分方便的。

二、哈希化

把巨大的整数（关键字）范围压缩到一个可接受的数组范围内，便于存储和查找。通常来说，我们要存储5000个数据，但数据的关键字范围可能是0-200000。我们不可能去开辟200000的数组去存储这5000个数据，这就需要一个函数把关键字和数组下标对应起来。这就是哈希函数。通常的做法是取余操作。i=N%size；i为下标，N为关键字，size为数组大小。不过通常来说，size设为要存储数据项数目的两倍。

如果哈希表存满时，需要扩展哈希表。我们需要新建一个更大的数组来存储数据，然后把原表中数据一一取出放入新表中。需要注意的是数据放入新表时需要重新用哈希函数计算哈希值，不能直接进行数组的复制，因为哈希函数的size已经变了。

通常而言我们把哈希数组的容量设为一个质数。首先来说假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。对于除法哈希表h(k)=k mod m，注意二进制数对取余就是该二进制数最后r位数。这样一来，Hash函数就和键值（用二进制表示）的前几位数无关了，这样我们就没有完全用到键值的信息，这种选择m的方法是不好的。所以好的方法就是用质数来表示m，使得这些质数，不太接近2的幂或者10的幂。

三、解决冲突

首先一般哈希表是不允许重复的关键字，否则查找函数只能返回最先查到的关键字，无法找到所有的对应数据项。如果重写查找函数让它可以找到所有的对应数据项，这又会使得无论是否是重复关键字，查找操作都要搜索整个表，非常耗时。

存储过程中可能出现存储的数据项关键字不同，但计算出来的哈希值是相同的，这就是冲突。

通常采用以下两种方法来解决冲突。

1、开放地址法

直接在哈希表中找到一个空位，把冲突的数据项存进去。

2、链地址法

把哈希表中存储的数据格式设为链表，这样可以把冲突的数据放入对应位置的链表中即可。

四、开放地址法的java实现

根据在查找下一个空位置时采用的方法，可以把开放地址法分为三种：线性探测、二次探测和再哈希法。

1、线性探测法

线性探测就是根据数组下标一个挨着一个去检测，直到找到一个空位置。

java实现：

DataItem类定义了哈希表存储的数据内容和关键字。

package hash;
    
    class DataItem    //hash表中存放的数据格式
    {                                
    private int iData;               // 设为关键字
    //--------------------------------------------------------------
    public DataItem(int ii)          // 构造器
       { iData = ii; }
    //--------------------------------------------------------------
    public int getKey()  //获取关键字
       { return iData; }
    //--------------------------------------------------------------
    }  // end class DataItem

HashTable类作为哈希表的实现

package hash;
    
    class HashTable        //定义哈希表
    {
    private DataItem[] hashArray;    // 数组形式
    private int arraySize;           //哈希表的大小
    private DataItem nonItem;        // 删除数据时,将被删除的数据设为nonItem
    //-------------------------------------------------------------
    public HashTable(int size)       //构造器，指定哈希表的大小
       {
       arraySize = size;
       hashArray = new DataItem[arraySize];
       nonItem = new DataItem(-1);   // 把nonItem的关键字设为-1
       }
    //-------------------------------------------------------------
    public void displayTable()       //显示哈希表
       {
       System.out.print("Table: ");
       for(int j=0; j<arraySize; j++)
          {
          if(hashArray[j] != null)
             System.out.print(hashArray[j].getKey() + " ");
          else
             System.out.print("** ");  //该位置没有存数据
          }
       System.out.println("");
       }
    //-------------------------------------------------------------
    public int hashFunc(int key)
       {
       return key % arraySize;       // 哈希函数
       }
    //-------------------------------------------------------------
    public void insert(DataItem item) // 插入数据
    // 默认表未满，事实上哈希表是不允许存满的，哈希表的大小比实际存储的数据数要大。
       {
       int key = item.getKey();      // 获取数据项的关键字，用于计算哈希值
       int hashVal = hashFunc(key);  // 计算哈希值
                                     // 当前位置存有数据并且该数据未被删除
       while(hashArray[hashVal] != null &&
                       hashArray[hashVal].getKey() != -1)
          {
          ++hashVal;                 // 查找下一个位置
          hashVal %= arraySize;      // 到达表的末尾时，hashVal值变成1,。构成循环，从而可以查找整个表
          }
       hashArray[hashVal] = item;    // 找到位置
       }  // end insert()
    //-------------------------------------------------------------
    public DataItem delete(int key)  // 根据关键字删除数据
       {
       int hashVal = hashFunc(key);  // 根据关键字计算哈希值
    
       while(hashArray[hashVal] != null)  // 该位置存有数据
          {                               // 两者的关键字是否相同
          if(hashArray[hashVal].getKey() == key)
             {
             DataItem temp = hashArray[hashVal]; // 保存删除的数据项，用于返回
             hashArray[hashVal] = nonItem;       // 删除
             return temp;                        // 返回删除的数据项
             }
          ++hashVal;                 // 关键字不相同，继续查找下一个
          hashVal %= arraySize;      //循环
          }
       return null;                  // 未找到
       }  // end delete()
    //-------------------------------------------------------------
    public DataItem find(int key)    // 表中是否存在该关键字的数据项
       {
       int hashVal = hashFunc(key);  
    
       while(hashArray[hashVal] != null)  
          {                               
          if(hashArray[hashVal].getKey() == key)
             return hashArray[hashVal];   
          ++hashVal;              
          hashVal %= arraySize;      
          }
       return null;                
       }
    //-------------------------------------------------------------
    }  // end class HashTable

HashTableApp类中包含了主程序

package hash;
    import java.io.*;
    
    class HashTableApp
    {
    public static void main(String[] args) throws IOException
       {
       DataItem aDataItem;
       int aKey, size, n, keysPerCell;
       System.out.print("Enter size of hash table: ");
       size = getInt();//从控制台获取一个整数作为哈希表的大小
       System.out.print("Enter initial number of items: ");
       n = getInt();  //随机生成n个数作为数据存入哈希表
       keysPerCell = 10;//随机生成函数的因子
                                    
      HashTable theHashTable = new HashTable(size);//初始化
    
       for(int j=0; j<n; j++)        // 生成并插入
          {
          aKey = (int)(java.lang.Math.random() *
                                          keysPerCell * size);
          aDataItem = new DataItem(aKey);//封装为哈希表中的数据格式
          theHashTable.insert(aDataItem);//插入
          }
    
       while(true)                   
          {
          System.out.print("Enter first letter of ");
          System.out.print("show, insert, delete, or find: ");
          char choice = getChar();
          switch(choice)
             {
             case 's':
                theHashTable.displayTable();
                break;
             case 'i':
             System.out.print("Enter key value to insert: ");
                aKey = getInt();
                aDataItem = new DataItem(aKey);
                theHashTable.insert(aDataItem);
                break;
             case 'd':
                System.out.print("Enter key value to delete: ");
                aKey = getInt();
                theHashTable.delete(aKey);
                break;
             case 'f':
                System.out.print("Enter key value to find: ");
                aKey = getInt();
                aDataItem = theHashTable.find(aKey);
                if(aDataItem != null)
                   {
                   System.out.println("Found " + aKey);
                   }
                else
                   System.out.println("Could not find " + aKey);
                break;
             default:
                System.out.print("Invalid entry\n");
             }  // end switch
          }  // end while
       }  // end main()
    //--------------------------------------------------------------
    public static String getString() throws IOException
       {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
       }
    //--------------------------------------------------------------
    public static char getChar() throws IOException
       {
       String s = getString();
       return s.charAt(0);
       }
    //-------------------------------------------------------------
    public static int getInt() throws IOException
       {
       String s = getString();
       return Integer.parseInt(s);
       }
    //--------------------------------------------------------------
    }  // end class HashTableApp

2、二次探测法

线性探测法会发生集聚现象，即冲突数据项会集聚在一起，原因是查找空数据项是一步一步移动的。

二次探测法是为了防止集聚产生的一种尝试方法，思想是探测间隔较远的单元，而不是临近的单元。具体方法是把步长设为探测次数的平方，比如第1次探测步长为1，第2次为4，第3次为9以此类推。

但是二次探测法会产生二次集聚。通常不采用该方法，因为有更好的解决方案。

3、再哈希法

方法是对冲突的关键字用另一个哈希函数计算其值，把结果作为搜索时的步长。这就使得不同的关键字步长不同，避免了集聚现象。

第二个哈希函数必须具备以下条件：

（1）与第一个哈希函数不同

（2）不能得出结果为0，否则步长为0.

通常第二个哈希函数采用如下函数：

step=constant-（key%contant）

constant是一个质数且小于数组容量，key是关键字。step范围在1-constant之间。

再哈希法要求表的容量是一个质数，这是为了使查找操作可以遍历整个表。否则假设表的容量为15,不是一个质数。而查找初始位置为4，查找步长为5，那么每次查找都是固定的三个数，即下标为9,14,4对应的数据。设为质数可以避免这种情况。

再哈希法的java实现

package hashDouble;
    
    class DataItem
    {                                 
    private int iData;                // 关键字
    //--------------------------------------------------------------
    public DataItem(int ii)           // 构造器
       { iData = ii; }
    //--------------------------------------------------------------
    public int getKey() //获取关键字
       { return iData; }
    //--------------------------------------------------------------
    }  // end class DataItem

package hashDouble;
    
    class HashTable
    {
    private DataItem[] hashArray; 
    private int arraySize;
    private DataItem nonItem;        
    //-------------------------------------------------------------
    HashTable(int size)               // 构造器
       {
       arraySize = size;
       hashArray = new DataItem[arraySize];
       nonItem = new DataItem(-1);
       }
    //-------------------------------------------------------------
    public void displayTable()
       {
       System.out.print("Table: ");
       for(int j=0; j<arraySize; j++)
          {
          if(hashArray[j] != null)
             System.out.print(hashArray[j].getKey()+ " ");
          else
             System.out.print("** ");
          }
       System.out.println("");
       }
    //-------------------------------------------------------------
    public int hashFunc1(int key)
       {
       return key % arraySize;
       }
    //-------------------------------------------------------------
    public int hashFunc2(int key) //再哈希
       {
       return 5 - key % 5;
       }
    //-------------------------------------------------------------
                                      
    public void insert(int key, DataItem item)
    // 假设表未满
       {
       int hashVal = hashFunc1(key);  // 计算哈希值
       int stepSize = hashFunc2(key); // 计算步长
                                      
       while(hashArray[hashVal] != null &&
                       hashArray[hashVal].getKey() != -1)//非空且数据未删除
          {
          hashVal += stepSize;        // 加步长
          hashVal %= arraySize;       // 循环到表头
          }
       hashArray[hashVal] = item;     // 插入
       }  // end insert()
    //-------------------------------------------------------------
    public DataItem delete(int key)   // 删除
       {
       int hashVal = hashFunc1(key);      //计算哈希值
       int stepSize = hashFunc2(key);     // 计算步长
    
       while(hashArray[hashVal] != null)  // 非空
          {                               
          if(hashArray[hashVal].getKey() == key)//找到
             {
             DataItem temp = hashArray[hashVal]; 
             hashArray[hashVal] = nonItem;       
             return temp;                       
             }
          hashVal += stepSize;           
          hashVal %= arraySize;           
          }
       return null;                   // 无法找到
       }  // end delete()
    //-------------------------------------------------------------
    public DataItem find(int key)     // 查找
    // 假设表未满
       {
       int hashVal = hashFunc1(key);       
       int stepSize = hashFunc2(key);     
    
       while(hashArray[hashVal] != null)  // 非空
          {                               
          if(hashArray[hashVal].getKey() == key)
             return hashArray[hashVal];   // 找到返回
          hashVal += stepSize;            // 加步长
          hashVal %= arraySize;          
          }
       return null;                   // can't find item
       }
    //-------------------------------------------------------------
    }  // end class HashTable

package hashDouble;
    import java.io.*;
    class HashDoubleApp
    {
    public static void main(String[] args) throws IOException
       {
       int aKey;
       DataItem aDataItem;
       int size, n;
                                 
       System.out.print("Enter size of hash table: ");
       size = getInt();
       System.out.print("Enter initial number of items: ");
       n = getInt();
                               
       HashTable theHashTable = new HashTable(size);
    
       for(int j=0; j<n; j++)     
          {
          aKey = (int)(java.lang.Math.random() * 2 * size);
          aDataItem = new DataItem(aKey);
          theHashTable.insert(aKey, aDataItem);
          }
    
       while(true)               
          {
          System.out.print("Enter first letter of ");
          System.out.print("show, insert, delete, or find: ");
          char choice = getChar();
          switch(choice)
             {
             case 's':
                theHashTable.displayTable();
                break;
             case 'i':
                System.out.print("Enter key value to insert: ");
                aKey = getInt();
                aDataItem = new DataItem(aKey);
                theHashTable.insert(aKey, aDataItem);
                break;
             case 'd':
                System.out.print("Enter key value to delete: ");
                aKey = getInt();
                theHashTable.delete(aKey);
                break;
             case 'f':
                System.out.print("Enter key value to find: ");
                aKey = getInt();
                aDataItem = theHashTable.find(aKey);
                if(aDataItem != null)
                   System.out.println("Found " + aKey);
                else
                   System.out.println("Could not find " + aKey);
                break;
             default:
                System.out.print("Invalid entry\n");
             }  // end switch
          }  // end while
       }  // end main()
    //--------------------------------------------------------------
    public static String getString() throws IOException
       {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
       }
    //--------------------------------------------------------------
    public static char getChar() throws IOException
       {
       String s = getString();
       return s.charAt(0);
       }
    //-------------------------------------------------------------
    public static int getInt() throws IOException
       {
       String s = getString();
       return Integer.parseInt(s);
       }
    //--------------------------------------------------------------
    }  // end class HashDoubleApp

五、链地址法的java实现

因为链地址法采用链表作为表中的数据格式，所以允许存储相同的关键字数据。而且我们可以把链设为有序链表。

Link类定义了链表结构

package hashChain;
    
    class Link        //定义链表
    {                                   // 可以动态存储数据，扩充容量
    private int iData;                  // 关键字
    public Link next;                   // 链接到下一个
    //-------------------------------------------------------------
    public Link(int it)                 //构造器
       { iData= it; }
    //-------------------------------------------------------------
    public int getKey()       //获取关键字
       { return iData; }
    //-------------------------------------------------------------
    public void displayLink()           // 显示
       { System.out.print(iData + " "); }
    }  // end class Link

SortedList定义了有序链表

package hashChain;
    
    class SortedList   //有序链表
    {
    private Link first;               // 链表头
    //-------------------------------------------------------------
    public void SortedList()          // 构造器
       { first = null; }
    //-------------------------------------------------------------
    public void insert(Link theLink)  // 插入并有序
       {
       int key = theLink.getKey();
       Link previous = null;          // 前一个数据项
       Link current = first;
                                     
       while( current != null && key > current.getKey() )//非空且关键字大于当前数据关键字
          {                          
          previous = current; //继续查找下一个
          current = current.next;     
          }
       if(previous==null)             // 如果表为空
          first = theLink;            //    表头指向该数据项
       else                           // 表非空
          previous.next = theLink;    //   key<current.getKey()时，数据项应插入previous后,previous-->theLink
       theLink.next = current;        // theLink --> current
       }  // end insert()
    //-------------------------------------------------------------
    public void delete(int key)       //删除
       {                         
       Link previous = null;        
       Link current = first;
                                  
       while( current != null && key != current.getKey() )//未找到
          {                        
          previous = current;
          current = current.next;     // 查找下一个
          }
                                   
       if(previous==null)             //  要删除数据项为表头
          first = first.next;         //      删除表头
       else                           //   不是表头
          previous.next = current.next; //    删除current
       }  // end delete()
    //-------------------------------------------------------------
    public Link find(int key)         // 查找
       {
       Link current = first;       
                                    
       while(current != null &&  current.getKey() <= key)
          {                      
          if(current.getKey() == key)    // 找到
             return current;          // 返回
          current = current.next;     //未找到继续查找下一个
          }
       return null;               //未找到
       }  // end find()
    //-------------------------------------------------------------
    public void displayList()//显示
       {
       System.out.print("List (first-->last): ");
       Link current = first;     
       while(current != null)   
          {
          current.displayLink();  
          current = current.next;  
          }
       System.out.println("");
       }
    }  // end class SortedList

HashTable定义哈希表，表中数据为SortedList形式

package hashChain;
    
    class HashTable
    {
    private SortedList[] hashArray;   
    private int arraySize;
    //-------------------------------------------------------------
    public HashTable(int size)        //构造器
       {
       arraySize = size;
       hashArray = new SortedList[arraySize];  // 初始化数组，数组中存储的是链表
       for(int j=0; j<arraySize; j++)          // 初始化每个数组元素
          hashArray[j] = new SortedList();  
       }
    //-------------------------------------------------------------
    public void displayTable()
       {
       for(int j=0; j<arraySize; j++) 
          {
          System.out.print(j + ". "); 
          hashArray[j].displayList(); 
          }
       }
    //-------------------------------------------------------------
    public int hashFunc(int key)      // 计算哈希值
       {
       return key % arraySize;
       }
    //-------------------------------------------------------------
    public void insert(Link theLink)  // 插入数据
       {
       int key = theLink.getKey();  //获取关键字
       int hashVal = hashFunc(key);   // 计算关键字哈希值
       hashArray[hashVal].insert(theLink); // 插入哈希表中对应的位置
       }  // end insert()
    //-------------------------------------------------------------
    public void delete(int key)       // 根据关键字删除数据
       {
       int hashVal = hashFunc(key);   // 计算关键字哈希值
       hashArray[hashVal].delete(key); // 删除哈希表中对应数据
       }  // end delete()
    //-------------------------------------------------------------
    public Link find(int key)         // 查找
       {
       int hashVal = hashFunc(key);   
       Link theLink = hashArray[hashVal].find(key);  
       return theLink;               
       }
    //-------------------------------------------------------------
    }  // end class HashTable

主函数

package hashChain;
    import java.io.*;
    
    class HashChainApp
    {
    public static void main(String[] args) throws IOException
       {
       int aKey;
       Link aDataItem;
       int size, n, keysPerCell = 100;
       System.out.print("Enter size of hash table: ");
       size = getInt();
       System.out.print("Enter initial number of items: ");
       n = getInt();
       HashTable theHashTable = new HashTable(size);
    
       for(int j=0; j<n; j++)        
          {
          aKey = (int)(java.lang.Math.random() *
                                           keysPerCell * size);
          aDataItem = new Link(aKey);
          theHashTable.insert(aDataItem);
          }
       while(true)                 
          {
          System.out.print("Enter first letter of ");
          System.out.print("show, insert, delete, or find: ");
          char choice = getChar();
          switch(choice)
             {
             case 's':
                theHashTable.displayTable();
                break;
             case 'i':
                System.out.print("Enter key value to insert: ");
                aKey = getInt();
                aDataItem = new Link(aKey);
                theHashTable.insert(aDataItem);
                break;
             case 'd':
                System.out.print("Enter key value to delete: ");
                aKey = getInt();
                theHashTable.delete(aKey);
                break;
             case 'f':
                System.out.print("Enter key value to find: ");
                aKey = getInt();
                aDataItem = theHashTable.find(aKey);
                if(aDataItem != null)
                   System.out.println("Found " + aKey);
                else
                   System.out.println("Could not find " + aKey);
                break;
             default:
                System.out.print("Invalid entry\n");
             }  // end switch
          }  // end while
       }  // end main()
    //--------------------------------------------------------------
    public static String getString() throws IOException
       {
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       String s = br.readLine();
       return s;
       }
    //-------------------------------------------------------------
    public static char getChar() throws IOException
       {
       String s = getString();
       return s.charAt(0);
       }
    //-------------------------------------------------------------
    public static int getInt() throws IOException
       {
       String s = getString();
       return Integer.parseInt(s);
       }
    //--------------------------------------------------------------
    }  // end class HashChainApp

六、如何设计哈希函数

1、不使用无用数据项

关键字的选取时，要提出原始数据中的无用数据项，例如起始位、校验位、结束位等，因为这些数据位没有携带信息。

2、使用所有的有用数据位

所有的有用数据位在哈希函数中都应当有体现。不要使用前四位或者后五位等其他方法。

3、使用质数作为取模运算的基数。

若关键字完全随机分布，质数和非质数的表现差不多。但是当关键字不是随机分布时，就应该使用质数作为哈希表的大小。使用质数可以是关键字较为平均的映射到哈希表的各个位置。

七、开放地址法和链地址法的比较

开放地址法在表快满时，性能有明显下降，且对哈希表进行扩展时操作复杂。链地址法需要设计链表类，但是不会随着数据项的增多导致性能快速下降，而且可以动态扩展哈希表。

参考文献：  
java数据结构与算法（第二版）