哈希表，开放地址法之线性探测代码（JAVA）

Java代码 复制代码 收藏代码
  1. import java.io.*;
  2. class DataItem { //数据
  3. private int iData; // data item (key)
  5. public DataItem(int ii) {
  6. iData = ii;
  7. }
  8. public int getKey(){
  9. return iData;
  10. }
  12. }
  14. class HashTable{//数组实现的哈希表，开放地址法之线性探测
  15. private DataItem[] hashArray; //存放数据的数组
  16. private int arraySize;
  17. private DataItem nonItem; //用作删除标志
  19. public HashTable(int size) {//构造函数
  20. arraySize = size;
  21. hashArray = new DataItem[arraySize];
  22. nonItem = new DataItem(-1); // deleted item key is -1
  23. }
  25. public void displayTable(){//显示哈希表
  26. System.out.print("Table: ");
  27. for(int j=0; j<arraySize; j++)
  28. {
  29. if(hashArray[j] != null)
  30. System.out.print(hashArray[j].getKey() + " ");
  31. else
  32. System.out.print("** ");
  33. }
  34. System.out.println("");
  35. }
  37. //哈希函数
  38. public int hashFunc(int key)
  39. {
  40. return key % arraySize;
  41. }
  44. //在哈希表中插入数据
  45. public void insert(DataItem item){
  46. int key = item.getKey(); // 获取数据的键值
  47. int hashVal = hashFunc(key); // 计算其哈希值
  49. while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1){
  50. ++hashVal; // 插入位置被占，线性探测下一位置
  51. hashVal %= arraySize; // 不让超过数组的大小
  52. }
  53. hashArray[hashVal] = item; // 找到空位后插入
  54. }
  56. //在哈希表中删除
  57. public DataItem delete(int key) {
  58. int hashVal = hashFunc(key); // 计算其哈希值
  60. while(hashArray[hashVal] != null){
  61. if(hashArray[hashVal].getKey() == key){
  62. DataItem temp = hashArray[hashVal]; // 记录已删除的数据
  63. hashArray[hashVal] = nonItem; // 删除它
  64. return temp;
  65. }
  66. ++hashVal; // 到下一单元找
  67. hashVal %= arraySize;
  68. }
  69. return null; // 没有找到要删除的数据
  70. }
  72. //在哈希表中查找
  73. public DataItem find(int key) {
  74. int hashVal = hashFunc(key); //哈希这个键
  76. while(hashArray[hashVal] != null) { // 直到空的单元
  77. if(hashArray[hashVal].getKey() == key)
  78. return hashArray[hashVal]; // 找到
  79. ++hashVal; // 去下一单元找
  80. hashVal %= arraySize; // 不让超过数组的大小
  81. }
  82. return null; // 没有找到
  83. }
  85. }
  87. public class HashTableApp{//测试
  88. public static void main(String[] args) throws IOException {
  89. DataItem aDataItem;
  90. int aKey, size, n, keysPerCell;
  91. System.out.print("Enter size of hash table: ");
  92. size = getInt();
  93. System.out.print("Enter initial number of items: ");
  94. n = getInt();
  95. keysPerCell = 10;
  97. HashTable theHashTable = new HashTable(size);
  99. for(int j=0; j<n; j++){
  100. aKey = (int)(java.lang.Math.random() * keysPerCell * size);
  101. aDataItem = new DataItem(aKey);
  102. theHashTable.insert(aDataItem);
  103. }
  105. while(true){
  106. System.out.print("Enter first letter of ");
  107. System.out.print("show, insert, delete, or find: ");
  108. char choice = getChar();
  109. switch(choice){
  110. case 's':
  111. theHashTable.displayTable();
  112. break;
  113. case 'i':
  114. System.out.print("Enter key value to insert: ");
  115. aKey = getInt();
  116. aDataItem = new DataItem(aKey);
  117. theHashTable.insert(aDataItem);
  118. break;
  119. case 'd':
  120. System.out.print("Enter key value to delete: ");
  121. aKey = getInt();
  122. theHashTable.delete(aKey);
  123. break;
  124. case 'f':
  125. System.out.print("Enter key value to find: ");
  126. aKey = getInt();
  127. aDataItem = theHashTable.find(aKey);
  128. if(aDataItem != null)
  129. {
  130. System.out.println("Found " + aKey);
  131. }
  132. else
  133. System.out.println("Could not find " + aKey);
  134. break;
  135. default:
  136. System.out.print("Invalid entry\n");
  137. }
  138. }
  139. }
  141. public static String getString() throws IOException{
  142. InputStreamReader isr = new InputStreamReader(System.in);
  143. BufferedReader br = new BufferedReader(isr);
  144. String s = br.readLine();
  145. return s;
  146. }
  148. public static char getChar() throws IOException
  149. {
  150. String s = getString();
  151. return s.charAt(0);
  152. }
  154. public static int getInt() throws IOException
  155. {
  156. String s = getString();
  157. return Integer.parseInt(s);
  158. }
  160. }

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bjanzhuo/p/3575920.html