|
1 | | - |
2 | | - |
3 | | -import java.util.ArrayList; |
4 | | -import java.util.LinkedList; |
5 | | - |
6 | | -public class HashMap<K,V> { |
7 | | - public class hmnodes{ //HashMap nodes |
8 | | - K key; |
9 | | - V value; |
10 | | - } |
11 | | - |
12 | | - private int size=0; //size of hashmap |
13 | | - private LinkedList<hmnodes> buckets[]; //array of addresses of list |
14 | | - |
15 | | - public HashMap(){ |
16 | | - buckets=new LinkedList[4]; //initially create bucket of any size |
17 | | - for(int i=0;i<4;i++) |
18 | | - buckets[i]=new LinkedList<>(); |
19 | | - } |
20 | | - |
21 | | - public void put(K key,V value) throws Exception{ |
22 | | - int bi=bucketIndex(key); //find the index,the new key will be inserted in linklist at that index |
23 | | - int fountAt=find(bi,key); //check if key already exists or not |
24 | | - if(fountAt==-1){ |
25 | | - hmnodes temp=new hmnodes(); //if doesn't exist create new node and insert |
26 | | - temp.key=key; |
27 | | - temp.value=value; |
28 | | - buckets[bi].addLast(temp); |
29 | | - this.size++; |
30 | | - }else{ |
31 | | - buckets[bi].get(fountAt).value=value;//if already exist modify the value |
32 | | - } |
33 | | - |
34 | | - double lambda = (this.size*1.0)/this.buckets.length; |
35 | | - if(lambda>2.0){ |
36 | | - rehash(); //rehashing function which will increase the size of bucket as soon as lambda exceeds 2.0 |
37 | | - } |
38 | | - |
39 | | - return; |
40 | | - } |
41 | | - |
42 | | - |
43 | | - public V get(K key) throws Exception{ |
44 | | - int bi=bucketIndex(key); |
45 | | - int fountAt=find(bi,key); |
46 | | - if(fountAt==-1){ |
47 | | - return null; |
48 | | - }else{ |
49 | | - return buckets[bi].get(fountAt).value; |
50 | | - } |
51 | | - } |
52 | | - |
53 | | - public V remove(K key) throws Exception{ |
54 | | - int bi=bucketIndex(key); |
55 | | - int fountAt=find(bi,key); |
56 | | - if(fountAt==-1){ |
57 | | - return null; |
58 | | - }else{ |
59 | | - this.size--; |
60 | | - return buckets[bi].remove(fountAt).value; |
61 | | - } |
62 | | - } |
63 | | - |
64 | | - public boolean containskey(K key) throws Exception{ |
65 | | - int bi=bucketIndex(key); |
66 | | - int fountAt=find(bi,key); |
67 | | - if(fountAt==-1){ |
68 | | - return false; |
69 | | - }else{ |
70 | | - return true; |
71 | | - } |
72 | | - } |
73 | | - |
74 | | - public int size(){ |
75 | | - return this.size; |
76 | | - } |
77 | | - |
78 | | - |
79 | | - public boolean isempty(){ |
80 | | - return this.size==0; |
81 | | - } |
82 | | - |
83 | | - public ArrayList<K> keyset() throws Exception{ |
84 | | - ArrayList<K> arr=new ArrayList<>(); |
85 | | - for(int i=0;i<buckets.length;i++){ |
86 | | - for(int j=0;j<buckets[i].size();j++){ |
87 | | - arr.add(buckets[i].get(j).key); |
88 | | - } |
89 | | - } |
90 | | - return arr; |
91 | | - } |
92 | | - |
93 | | - public ArrayList<V> valueset() throws Exception{ |
94 | | - ArrayList<V> arr=new ArrayList<>(); |
95 | | - for(int i=0;i<buckets.length;i++){ |
96 | | - for(int j=0;j<buckets[i].size();j++){ |
97 | | - arr.add(buckets[i].get(j).value); |
98 | | - } |
99 | | - } |
100 | | - return arr; |
101 | | - } |
102 | | - |
103 | | - public void display() throws Exception{ |
104 | | - for(int i=0;i<buckets.length;i++){ |
105 | | - System.out.print("Bucket: "+i+" "); |
106 | | - for(int j=0;j<buckets[i].size();j++){ |
107 | | - hmnodes temp=buckets[i].get(j); |
108 | | - System.out.print("["+temp.key+"->"+temp.value+"]"); |
109 | | - } |
110 | | - System.out.println(); |
111 | | - } |
112 | | - } |
113 | | - |
114 | | - public int find(int bi,K key) throws Exception{ |
115 | | - for(int i=0;i<buckets[bi].size();i++){ |
116 | | - if(key.equals(buckets[bi].get(i).key)) |
117 | | - return i; |
118 | | - } |
119 | | - return -1; |
120 | | - } |
121 | | - |
122 | | - public int bucketIndex(K key) throws Exception{ |
123 | | - int bi=key.hashCode(); |
124 | | - return Math.abs(bi%buckets.length); |
125 | | - } |
126 | | - |
127 | | - private void rehash() throws Exception{ |
128 | | - LinkedList<hmnodes> ob[]= buckets; |
129 | | - buckets=new LinkedList[ob.length*2]; |
130 | | - for(int i=0;i<ob.length*2;i++) |
131 | | - buckets[i]=new LinkedList<>(); |
132 | | - |
133 | | - size = 0; |
134 | | - for(int i=0;i<ob.length;i++){ |
135 | | - for(int j=0;j<ob[i].size();j++){ |
136 | | - put(ob[i].get(j).key,ob[i].get(j).value); |
137 | | - } |
138 | | - } |
139 | | - |
140 | | - } |
141 | | -} |
| 1 | + |
| 2 | + |
| 3 | +import java.util.ArrayList; |
| 4 | +import java.util.LinkedList; |
| 5 | + |
| 6 | +public class HashMap<K,V> { |
| 7 | + public class hmnodes{ //HashMap nodes |
| 8 | + K key; |
| 9 | + V value; |
| 10 | + } |
| 11 | + |
| 12 | + private int size=0; //size of hashmap |
| 13 | + private LinkedList<hmnodes> buckets[]; //array of addresses of list |
| 14 | + |
| 15 | + public HashMap(){ |
| 16 | + buckets=new LinkedList[4]; //initially create bucket of any size |
| 17 | + for(int i=0;i<4;i++) |
| 18 | + buckets[i]=new LinkedList<>(); |
| 19 | + } |
| 20 | + |
| 21 | + public void put(K key,V value) throws Exception{ |
| 22 | + int bi=bucketIndex(key); //find the index,the new key will be inserted in linklist at that index |
| 23 | + int fountAt=find(bi,key); //check if key already exists or not |
| 24 | + if(fountAt==-1){ |
| 25 | + hmnodes temp=new hmnodes(); //if doesn't exist create new node and insert |
| 26 | + temp.key=key; |
| 27 | + temp.value=value; |
| 28 | + buckets[bi].addLast(temp); |
| 29 | + this.size++; |
| 30 | + }else{ |
| 31 | + buckets[bi].get(fountAt).value=value;//if already exist modify the value |
| 32 | + } |
| 33 | + |
| 34 | + double lambda = (this.size*1.0)/this.buckets.length; |
| 35 | + if(lambda>2.0){ |
| 36 | + rehash(); //rehashing function which will increase the size of bucket as soon as lambda exceeds 2.0 |
| 37 | + } |
| 38 | + |
| 39 | + return; |
| 40 | + } |
| 41 | + |
| 42 | + |
| 43 | + public V get(K key) throws Exception{ |
| 44 | + int bi=bucketIndex(key); |
| 45 | + int fountAt=find(bi,key); |
| 46 | + if(fountAt==-1){ |
| 47 | + return null; |
| 48 | + }else{ |
| 49 | + return buckets[bi].get(fountAt).value; |
| 50 | + } |
| 51 | + } |
| 52 | + |
| 53 | + public V remove(K key) throws Exception{ |
| 54 | + int bi=bucketIndex(key); |
| 55 | + int fountAt=find(bi,key); |
| 56 | + if(fountAt==-1){ |
| 57 | + return null; |
| 58 | + }else{ |
| 59 | + this.size--; |
| 60 | + return buckets[bi].remove(fountAt).value; |
| 61 | + } |
| 62 | + } |
| 63 | + |
| 64 | + public boolean containskey(K key) throws Exception{ |
| 65 | + int bi=bucketIndex(key); |
| 66 | + int fountAt=find(bi,key); |
| 67 | + if(fountAt==-1){ |
| 68 | + return false; |
| 69 | + }else{ |
| 70 | + return true; |
| 71 | + } |
| 72 | + } |
| 73 | + |
| 74 | + public int size(){ |
| 75 | + return this.size; |
| 76 | + } |
| 77 | + |
| 78 | + |
| 79 | + public boolean isempty(){ |
| 80 | + return this.size==0; |
| 81 | + } |
| 82 | + |
| 83 | + public ArrayList<K> keyset() throws Exception{ |
| 84 | + ArrayList<K> arr=new ArrayList<>(); |
| 85 | + for(int i=0;i<buckets.length;i++){ |
| 86 | + for(int j=0;j<buckets[i].size();j++){ |
| 87 | + arr.add(buckets[i].get(j).key); |
| 88 | + } |
| 89 | + } |
| 90 | + return arr; |
| 91 | + } |
| 92 | + |
| 93 | + public ArrayList<V> valueset() throws Exception{ |
| 94 | + ArrayList<V> arr=new ArrayList<>(); |
| 95 | + for(int i=0;i<buckets.length;i++){ |
| 96 | + for(int j=0;j<buckets[i].size();j++){ |
| 97 | + arr.add(buckets[i].get(j).value); |
| 98 | + } |
| 99 | + } |
| 100 | + return arr; |
| 101 | + } |
| 102 | + |
| 103 | + public void display() throws Exception{ |
| 104 | + for(int i=0;i<buckets.length;i++){ |
| 105 | + System.out.print("Bucket: "+i+" "); |
| 106 | + for(int j=0;j<buckets[i].size();j++){ |
| 107 | + hmnodes temp=buckets[i].get(j); |
| 108 | + System.out.print("["+temp.key+"->"+temp.value+"]"); |
| 109 | + } |
| 110 | + System.out.println(); |
| 111 | + } |
| 112 | + } |
| 113 | + |
| 114 | + public int find(int bi,K key) throws Exception{ |
| 115 | + for(int i=0;i<buckets[bi].size();i++){ |
| 116 | + if(key.equals(buckets[bi].get(i).key)) |
| 117 | + return i; |
| 118 | + } |
| 119 | + return -1; |
| 120 | + } |
| 121 | + |
| 122 | + public int bucketIndex(K key) throws Exception{ |
| 123 | + int bi=key.hashCode(); |
| 124 | + return Math.abs(bi%buckets.length); |
| 125 | + } |
| 126 | + |
| 127 | + private void rehash() throws Exception{ |
| 128 | + LinkedList<hmnodes> ob[]= buckets; |
| 129 | + buckets=new LinkedList[ob.length*2]; |
| 130 | + for(int i=0;i<ob.length*2;i++) |
| 131 | + buckets[i]=new LinkedList<>(); |
| 132 | + |
| 133 | + size = 0; |
| 134 | + for(int i=0;i<ob.length;i++){ |
| 135 | + for(int j=0;j<ob[i].size();j++){ |
| 136 | + put(ob[i].get(j).key,ob[i].get(j).value); |
| 137 | + } |
| 138 | + } |
| 139 | + |
| 140 | + } |
| 141 | +} |
0 commit comments