fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. class LinearProbing {
  4. 	int[] freq, status, hashTable;
  5. 	int capacity;
  6. 	int EMPTY = 0, DELETED = -1, OCCUPIED = 1;
  7.  
  8. 	LinearProbing(int capacity) {
  9. 		this.capacity = capacity;
  10. 		freq = new int[capacity];
  11. 		status = new int[capacity];
  12. 		hashTable = new int[capacity];
  13. 	}
  14.  
  15. 	public int hashFunction(int key) {
  16. 		return key % capacity;
  17. 	}
  18.  
  19. 	public boolean search(int key) {
  20. 		int index = hashFunction(key);
  21. 		int start = index;
  22. 		while (status[index] != EMPTY) {
  23. 			if (hashTable[index] == key && status[index] == OCCUPIED)
  24. 				return true;
  25. 			index = (index + 1) % capacity;
  26. 			if (index == start) break;
  27. 		}
  28. 		return false;
  29. 	}
  30.  
  31. 	public void insert(int key) {
  32. 		int index = hashFunction(key);
  33. 		int start = index;
  34. 		while (status[index] != EMPTY) {
  35. 			if (hashTable[index] == key) {
  36. 				freq[index]++;
  37. 				return;
  38. 			}
  39. 			index = (index + 1) % capacity;
  40. 			if (index == start) return;
  41. 		}
  42. 		hashTable[index] = key;
  43. 		status[index] = OCCUPIED;
  44. 		freq[index] = 1;
  45. 	}
  46.  
  47. 	public boolean delete(int key) {
  48. 		int index = hashFunction(key);
  49. 		int start = index;
  50. 		while (status[index] != EMPTY) {
  51. 			if (hashTable[index] == key && status[index] == OCCUPIED) {
  52. 				freq[index]--;
  53. 				if (freq[index] <= 0) status[index] = DELETED;
  54. 				return true;
  55. 			}
  56. 			index = (index + 1) % capacity;
  57. 			if (index == start) break;
  58. 		}
  59. 		return false;
  60. 	}
  61.  
  62. 	public void display() {
  63. 		for (int i = 0; i < capacity; i++) {
  64. 			if (status[i] == OCCUPIED)
  65. 				System.out.println(i + " -> " + hashTable[i] + " : " + freq[i]);
  66. 			else
  67. 				System.out.println(i + " -> - : -");
  68. 		}
  69. 	}
  70. }
  71.  
  72. public class Main {
  73. 	public static void main(String[] args) {
  74. 		LinearProbing map = new LinearProbing(10);
  75. 		map.insert(45);
  76. 		map.insert(22);
  77. 		map.insert(35);
  78. 		map.insert(67);
  79. 		map.insert(78);
  80. 		map.insert(15);
  81. 		map.insert(67);
  82. 		map.insert(67);
  83. 		map.insert(90);
  84. 		map.insert(90);
  85. 		System.out.println(map.delete(15)); 
  86. 		System.out.println(map.search(99));  
  87. 		map.display();
  88. 	}
  89. }
  90.  
Success #stdin #stdout 0.22s 57944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
false
0 -> 90 : 2
1 -> - : -
2 -> 22 : 1
3 -> - : -
4 -> - : -
5 -> 45 : 1
6 -> 35 : 1
7 -> 67 : 3
8 -> 78 : 1
9 -> - : -
https://ideone.com/gn91ci
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!