当前位置:首页 > 开发 > 编程语言 > Java > 正文

哈希表,开放地址法之线性探测代码(JAVA)

发表于: 2012-12-10   作者:128kj   来源:转载   浏览:
摘要: import java.io.*; class DataItem { //数据 private int iData; // data item (key) public DataItem(int ii) { iData = ii; } public int getKey(){
import java.io.*;
class DataItem { //数据                           
   private int iData;    // data item (key)

   public DataItem(int ii) { 
    iData = ii; 
  }
      public int getKey(){
       return iData; 
   }

   }  

class HashTable{//数组实现的哈希表,开放地址法之线性探测
   private DataItem[] hashArray; //存放数据的数组
   private int arraySize;
   private DataItem nonItem; //用作删除标志

   public HashTable(int size) {//构造函数
      arraySize = size;
      hashArray = new DataItem[arraySize];
      nonItem = new DataItem(-1);   // deleted item key is -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;   // 不让超过数组的大小
     }
      hashArray[hashVal] = item;  // 找到空位后插入
   }  

   //在哈希表中删除
   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;    // 没有找到要删除的数据
      } 

   //在哈希表中查找
   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;  // 没有找到
  }

}  

public 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();
      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");
            }  
         }  
      }  

   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);
      }

   }  



运行:
C:\java>java   HashTableApp
Enter size of hash table: 20
Enter initial number of items: 10
Enter first letter of show, insert, delete, or find: s
Table: ** ** ** 143 24 85 166 ** ** 89 30 ** ** ** 34 15 ** 17 ** 59
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 89
Enter first letter of show, insert, delete, or find: s
Table: ** ** ** 143 24 85 166 ** ** -1 30 ** ** ** 34 15 ** 17 ** 59
Enter first letter of show, insert, delete, or find: f
Enter key value to find: 17
Found 17
Enter first letter of show, insert, delete, or find:

源码下载:

哈希表,开放地址法之线性探测代码(JAVA)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
哈希表中,一串连续的已填充单元叫做填充序列。增加越来越多的数据项时,填充序列变的越来越长,这
二、开地址法 基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个
二、开地址法 基本思想:当关键码key的哈希地址H0 = hash(key)出现冲突时,以H0为基础,产生另一个
在上一篇博文中,我们讲述了使用链地址法解决冲突的方法。这里我们介绍另一种方式:开地址法解决冲
/* 文件名称:main.cpp 作者 :王超 完成日期:2015年12月7日 问题描述:用哈希法组织关键字 线性探
哈希表的链地址法来解决冲突问题 将所有关键字为同义词的记录存储在同一个线性链表中,假设某哈希函
链地址法的基本思想是:将所有哈希地址为i 的元素构成一个称为同义词链的链表,并将链表的头指针存
上一节讲了利用链表来处理冲突的方法——分离链接法。本节讲另一种处理冲突的方法——开放定址法。
1、背景引入    (1)线性表和树等线性结构中,记录在结构中的相对位置是随机的,和记录的关键字
/* * Copyright (c)2015,烟台大学计算机与控制工程学院 * All rights reserved. * 文件名称:项目.c
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号