Skip to content

Commit 84f5038

Browse files
author
Ray
committed
Add HashMapLinearProbing.java and MainLinearProbing.java
1 parent 0ce51e8 commit 84f5038

File tree

2 files changed

+217
-0
lines changed

2 files changed

+217
-0
lines changed

‎DataStructures/HashMap/Hashing/HashMapLinearProbing.java

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
package DataStructures.HashMap.Hashing;
2+
3+
/**
4+
* This class is an implementation of a hash table using linear probing
5+
*
6+
*/
7+
class HashMapLinearProbing {
8+
private int hsize;
9+
private Integer[] buckets;
10+
private Integer AVAILABLE;
11+
12+
/**
13+
* Constructor initializes buckets array, hsize, and creates dummy object for AVAILABLE
14+
* @param hsize the desired size of the hash map
15+
*/
16+
public HashMapLinearProbing(int hsize) {
17+
buckets = new Integer[hsize];
18+
this.hsize = hsize;
19+
AVAILABLE = new Integer(Integer.MIN_VALUE);
20+
}
21+
22+
/**
23+
* The Hash Function takes a given key and finds an index based on its data
24+
* @param key the desired key to be converted
25+
* @return int an index corresponding to the key
26+
*/
27+
public int hashing(int key) {
28+
int hash = key % hsize;
29+
if (hash < 0) {
30+
hash += hsize;
31+
}
32+
return hash;
33+
}
34+
35+
/**
36+
* inserts the key into the hash map by wrapping it as an Integer object
37+
* @param key the desired key to be inserted in the hash map
38+
*/
39+
public void insertHash(int key) {
40+
Integer wrappedInt = new Integer(key);
41+
int hash = hashing(key);
42+
43+
if(isFull()) {
44+
System.out.println("Hash table is full");
45+
return;
46+
}
47+
48+
for (int i = 0;i < hsize; i++) {
49+
if(buckets[hash] == null || buckets[hash] == AVAILABLE) {
50+
buckets[hash] = wrappedInt;
51+
return;
52+
}
53+
54+
if(hash + 1 < hsize) {
55+
hash++;
56+
} else {
57+
hash = 0;
58+
}
59+
}
60+
}
61+
62+
/**
63+
* deletes a key from the hash map and adds an available placeholder
64+
* @param key the desired key to be deleted
65+
*/
66+
public void deleteHash(int key) {
67+
Integer wrappedInt = new Integer(key);
68+
int hash = hashing(key);
69+
70+
if(isEmpty()) {
71+
System.out.println("Table is empty");
72+
return;
73+
}
74+
75+
for(int i = 0;i < hsize; i++) {
76+
if(buckets[hash] != null && buckets[hash].equals(wrappedInt)) {
77+
buckets[hash] = AVAILABLE;
78+
return;
79+
}
80+
81+
if(hash + 1 < hsize) {
82+
hash++;
83+
} else {
84+
hash = 0;
85+
}
86+
}
87+
System.out.println("Key " + key + " not found");
88+
}
89+
90+
/**
91+
* Displays the hash table line by line
92+
*/
93+
public void displayHashtable() {
94+
for (int i = 0; i < hsize; i++) {
95+
if(buckets[i] == null || buckets[i] == AVAILABLE) {
96+
System.out.println("Bucket " + i + ": Empty");
97+
} else {
98+
System.out.println("Bucket " + i + ": " + buckets[i].toString());
99+
}
100+
101+
}
102+
}
103+
104+
/**
105+
* Finds the index of location based on an inputed key
106+
* @param key the desired key to be found
107+
* @return int the index where the key is located
108+
*/
109+
public int findHash(int key) {
110+
Integer wrappedInt = new Integer(key);
111+
int hash = hashing(key);
112+
113+
if(isEmpty()) {
114+
System.out.println("Table is empty");
115+
return -1;
116+
}
117+
118+
for(int i = 0;i < hsize; i++) {
119+
if(buckets[hash].equals(wrappedInt)) {
120+
buckets[hash] = AVAILABLE;
121+
return hash;
122+
}
123+
124+
if(hash + 1 < hsize) {
125+
hash++;
126+
} else {
127+
hash = 0;
128+
}
129+
}
130+
System.out.println("Key " + key + " not found");
131+
return -1;
132+
}
133+
134+
/**
135+
* isFull returns true if the hash map is full and false if not full
136+
* @return boolean is Empty
137+
*/
138+
public boolean isFull() {
139+
boolean response = true;
140+
for(int i = 0; i< hsize;i++) {
141+
if(buckets[i] == null || buckets[i] == AVAILABLE) {
142+
response = false;
143+
break;
144+
}
145+
}
146+
return response;
147+
}
148+
149+
/**
150+
* isEmpty returns true if the hash map is empty and false if not empty
151+
* @return boolean is Empty
152+
*/
153+
public boolean isEmpty() {
154+
boolean response = true;
155+
for(int i = 0; i< hsize;i++) {
156+
if(buckets[i] != null) {
157+
response = false;
158+
break;
159+
}
160+
}
161+
return response;
162+
}
163+
}

‎DataStructures/HashMap/Hashing/MainLinearProbing.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package DataStructures.HashMap.Hashing;
2+
3+
import java.util.Scanner;
4+
5+
public class MainLinearProbing {
6+
public static void main(String[] args) {
7+
8+
int choice, key;
9+
10+
HashMapLinearProbing h = new HashMapLinearProbing(7);
11+
Scanner In = new Scanner(System.in);
12+
13+
while (true) {
14+
System.out.println("Enter your Choice :");
15+
System.out.println("1. Add Key");
16+
System.out.println("2. Delete Key");
17+
System.out.println("3. Print Table");
18+
System.out.println("4. Exit");
19+
System.out.println("5. Search and print key index");
20+
21+
choice = In.nextInt();
22+
23+
switch (choice) {
24+
case 1: {
25+
System.out.println("Enter the Key: ");
26+
key = In.nextInt();
27+
h.insertHash(key);
28+
break;
29+
}
30+
case 2: {
31+
System.out.println("Enter the Key delete: ");
32+
key = In.nextInt();
33+
h.deleteHash(key);
34+
break;
35+
}
36+
case 3: {
37+
System.out.println("Print table");
38+
h.displayHashtable();
39+
break;
40+
}
41+
case 4: {
42+
In.close();
43+
return;
44+
}
45+
case 5: {
46+
System.out.println("Enter the Key to find and print: ");
47+
key = In.nextInt();
48+
System.out.println("Key: "+ key + " is at index: "+ h.findHash(key));
49+
}
50+
}
51+
52+
}
53+
}
54+
}

0 commit comments

Comments
 (0)