· 5 years ago · Jun 10, 2020, 09:56 AM
1package at.fhj.hashing;
2
3/**
4 * Hash table for arbitrary objects using the double hashing algorithm with Brent.
5 * The standard hashCode() method is used to get the key value of the objects
6 *
7 */
8public class HashTable {
9 /**
10 * Objects to be stored are wrapped in a HashObject object before being put into
11 * the hash table:
12 * - If an entry in the hash table contains null, the entry is empty.
13 * - If the table entry contains a HashObject wrapper object with a null data object,
14 * it is free, meaning there was a data object that has been deleted.
15 * - If the wrapper object contains a valid data object, the hash table entry is in
16 * use.
17 */
18 private HashObject[] table;
19
20 /**
21 * Create a hash table of the specified size
22 * @param size ... size of the hash table
23 */
24 public HashTable(int size) {
25 this.table = new HashObject[size];
26 }
27
28 /**
29 * Create a hash table Object from a given HashObject array (for testing purposes)
30 * @param table ... HashObject array
31 */
32 public HashTable(HashObject[] table) {
33 this.table = table;
34 }
35
36 /**
37 * Return the array containing the HashObject wrapper objects
38 * @return ... Hash array
39 */
40 public HashObject[] getTable() {
41 return this.table;
42 }
43
44 /**
45 * Insert the given into the hash table using double hashing (without Brent)
46 * @param obj ... object to insert into the hash table
47 * @return table index where the object was successfully inserted, -1 if table
48 * is full or an object with the same key already exists within the table
49 */
50 public int insert(Object obj) {
51 int key = obj.hashCode();
52
53 // Begin implementation
54
55 return -1; // change it!
56 // End implementation
57 }
58
59 /**
60 * Insert the given into the hash table using double hashing with Brent
61 * @param obj ... object to insert into the hash table
62 * @return table index where the object was successfully inserted, -1 if table
63 * is full or an object with the same key already exists within the table
64 */
65 public int insertBrent(Object obj) {
66 int key = obj.hashCode();
67
68 // Begin implementation
69
70 return -1; // change it!
71 // End implementation
72 }
73
74 /**
75 * Get the object identified by it's key (hashCode()) value from the hash table
76 * @param key
77 * @return the object with the specified key value if it exists in the table, null otherwise
78 */
79 public Object retrieve(int key) {
80 // Begin implementation
81
82 return null; // change it!
83 // End implementation
84 }
85
86 /**
87 * Delete the object identified by a key (hashCode()) value from the hash table
88 * @param key
89 * @return true if the object with the specified key has been found and deleted, false otherwise
90 */
91 public boolean delete(int key) {
92 // Begin implementation
93
94 return false; // change it!
95 // End implementation
96 }
97
98 /**
99 * Check if a given position in the hash table is empty, i.e. free and no deleted object either
100 * @param pos ... position in hash table
101 * @return true, if the position is empty, false otherwise
102 */
103 private boolean isEmpty(int pos) {
104 if (table[pos] == null)
105 return true;
106 else
107 return false;
108 }
109
110 /**
111 * Check if a given position in the hash table is free, i.e. either free or it contains a deleted
112 * object
113 * @param pos ... position in hash table
114 * @return true, if the position is free, false otherwise
115 */
116 private boolean isFree(int pos) {
117 if (table[pos] == null) // empty
118 return true;
119 if (table[pos].getData() == null) // free
120 return true;
121 return false; // occupied
122 }
123
124 /**
125 * Set an entry in the hash table at a given position
126 * @param pos ... position for inserting
127 * @param obj ... object to insert
128 */
129 private void setEntry(int pos, Object obj) {
130 if (isEmpty(pos))
131 table[pos] = new HashObject(obj);
132 else
133 table[pos].setData(obj);
134 }
135
136 /**
137 * Get the entry in the hash table at a given position
138 * @param pos ... position in the hash table
139 * @return object stored in this Position if the position is not free, null otherwise
140 */
141 private Object getEntry(int pos) {
142 if (!isFree(pos))
143 return table[pos].getData();
144 else
145 return null;
146 }
147
148 /**
149 * Delete an entry in the hash table at a give position
150 * @param pos ... position of the entry to be deleted
151 */
152 private void deleteEntry(int pos) {
153 if (!isEmpty(pos))
154 setEntry(pos, null);
155 }
156
157 // Place your private methods here
158 // Begin implementation
159
160 // End implementation
161}