forked from Sachin-Mamoru/Java_Programs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhash_table_code.java
More file actions
129 lines (115 loc) · 2.78 KB
/
hash_table_code.java
File metadata and controls
129 lines (115 loc) · 2.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
public class HashTable<K, V> {
private class HTPair {
K key;
V value;
public HTPair(K key, V value) {
this.key = key;
this.value = value;
}
public boolean equals(Object other) {
HTPair op = (HTPair) other;
return this.key.equals(op.key);
}
public String toString() {
return "{" + this.key + "->" + this.value + "}";
}
}
private LinkedList<HTPair>[] bucketArray;
private int size;
public static final int DEFAULT_CAPACITY = 5;
public HashTable() {
this(DEFAULT_CAPACITY);
}
public HashTable(int capacity) {
this.bucketArray = (LinkedList<HTPair>[]) new LinkedList[capacity];
this.size = 0;
}
public int size() {
return this.size;
}
private int HashFunction(K key) {
int hc = key.hashCode();
hc = Math.abs(hc);
int bi = hc % this.bucketArray.length;
return bi;
}
public void put(K key, V value) throws Exception {
int bi = HashFunction(key);
HTPair data = new HTPair(key, value);
if (this.bucketArray[bi] == null) {
LinkedList<HTPair> bucket = new LinkedList<>();
bucket.addLast(data);
this.size++;
this.bucketArray[bi] = bucket;
} else {
int foundAt = this.bucketArray[bi].find(data);
if (foundAt == -1) {
this.bucketArray[bi].addLast(data);
this.size++;
} else {
HTPair obj = this.bucketArray[bi].getAt(foundAt);
obj.value = value;
this.size++;
}
}
double lambda = (this.size) * 1.0;
lambda = this.size / this.bucketArray.length;
if (lambda > 0.75) {
rehash();
}
}
public void display() {
for (LinkedList<HTPair> list : this.bucketArray) {
if (list != null && !list.isEmpty()) {
list.display();
} else {
System.out.println("NULL");
}
}
}
public V get(K key) throws Exception {
int index = this.HashFunction(key);
LinkedList<HTPair> list = this.bucketArray[index];
HTPair ptf = new HTPair(key, null);
if (list == null) {
return null;
} else {
int findAt = list.find(ptf);
if (findAt == -1) {
return null;
} else {
HTPair pair = list.getAt(findAt);
return pair.value;
}
}
}
public V remove(K key) throws Exception {
int index = this.HashFunction(key);
LinkedList<HTPair> list = this.bucketArray[index];
HTPair ptf = new HTPair(key, null);
if (list == null) {
return null;
} else {
int findAt = list.find(ptf);
if (findAt == -1) {
return null;
} else {
HTPair pair = list.getAt(findAt);
list.removeAt(findAt);
this.size--;
return pair.value;
}
}
}
public void rehash() throws Exception {
LinkedList<HTPair>[] oba = this.bucketArray;
this.bucketArray = (LinkedList<HTPair>[]) new LinkedList[2 * oba.length];
this.size = 0;
for (LinkedList<HTPair> ob : oba) {
while (ob != null && !ob.isEmpty()) {
HTPair pair = ob.removeFirst();
this.put(pair.key, pair.value);
}
}
}
}