forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHashMap.java
More file actions
141 lines (118 loc) · 3.21 KB
/
HashMap.java
File metadata and controls
141 lines (118 loc) · 3.21 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
130
131
132
133
134
135
136
137
138
139
140
141
import java.util.ArrayList;
import java.util.LinkedList;
public class HashMap<K,V> {
public class hmnodes{ //HashMap nodes
K key;
V value;
}
private int size=0; //size of hashmap
private LinkedList<hmnodes> buckets[]; //array of addresses of list
public HashMap(){
buckets=new LinkedList[4]; //initially create bucket of any size
for(int i=0;i<4;i++)
buckets[i]=new LinkedList<>();
}
public void put(K key,V value) throws Exception{
int bi=bucketIndex(key); //find the index,the new key will be inserted in linklist at that index
int fountAt=find(bi,key); //check if key already exists or not
if(fountAt==-1){
hmnodes temp=new hmnodes(); //if doesn't exist create new node and insert
temp.key=key;
temp.value=value;
buckets[bi].addLast(temp);
this.size++;
}else{
buckets[bi].get(fountAt).value=value;//if already exist modify the value
}
double lambda = (this.size*1.0)/this.buckets.length;
if(lambda>2.0){
rehash(); //rehashing function which will increase the size of bucket as soon as lambda exceeds 2.0
}
return;
}
public V get(K key) throws Exception{
int bi=bucketIndex(key);
int fountAt=find(bi,key);
if(fountAt==-1){
return null;
}else{
return buckets[bi].get(fountAt).value;
}
}
public V remove(K key) throws Exception{
int bi=bucketIndex(key);
int fountAt=find(bi,key);
if(fountAt==-1){
return null;
}else{
this.size--;
return buckets[bi].remove(fountAt).value;
}
}
public boolean containskey(K key) throws Exception{
int bi=bucketIndex(key);
int fountAt=find(bi,key);
if(fountAt==-1){
return false;
}else{
return true;
}
}
public int size(){
return this.size;
}
public boolean isempty(){
return this.size==0;
}
public ArrayList<K> keyset() throws Exception{
ArrayList<K> arr=new ArrayList<>();
for(int i=0;i<buckets.length;i++){
for(int j=0;j<buckets[i].size();j++){
arr.add(buckets[i].get(j).key);
}
}
return arr;
}
public ArrayList<V> valueset() throws Exception{
ArrayList<V> arr=new ArrayList<>();
for(int i=0;i<buckets.length;i++){
for(int j=0;j<buckets[i].size();j++){
arr.add(buckets[i].get(j).value);
}
}
return arr;
}
public void display() throws Exception{
for(int i=0;i<buckets.length;i++){
System.out.print("Bucket: "+i+" ");
for(int j=0;j<buckets[i].size();j++){
hmnodes temp=buckets[i].get(j);
System.out.print("["+temp.key+"->"+temp.value+"]");
}
System.out.println();
}
}
public int find(int bi,K key) throws Exception{
for(int i=0;i<buckets[bi].size();i++){
if(key.equals(buckets[bi].get(i).key))
return i;
}
return -1;
}
public int bucketIndex(K key) throws Exception{
int bi=key.hashCode();
return Math.abs(bi%buckets.length);
}
private void rehash() throws Exception{
LinkedList<hmnodes> ob[]= buckets;
buckets=new LinkedList[ob.length*2];
for(int i=0;i<ob.length*2;i++)
buckets[i]=new LinkedList<>();
size = 0;
for(int i=0;i<ob.length;i++){
for(int j=0;j<ob[i].size();j++){
put(ob[i].get(j).key,ob[i].get(j).value);
}
}
}
}