Source code: com/memoire/fu/FuHashtableFast.java
1 /**
2 * @modification $Date: 2002/12/16 18:56:26 $
3 * @statut unstable
4 * @file FuHashtableFast.java
5 * @version 0.36
6 * @author Guillaume Desnoix
7 * @email guillaume@desnoix.com
8 * @license GNU General Public License 2 (GPL2)
9 * @copyright 1998-2001 Guillaume Desnoix
10 */
11
12 package com.memoire.fu;
13
14 import com.memoire.fu.*;
15 import java.io.*;
16 import java.util.*;
17
18 /**
19 * A fast hashtable not synchronized and using == as test.
20 */
21 public final class FuHashtableFast
22 // implements Serializable
23 {
24 private static final class Entry
25 // implements Serializable
26 {
27 public int hash;
28 public Object key;
29 public Object value;
30 public Entry next;
31 }
32
33 private Entry table[];
34 private int count;
35 private int threshold;
36 private float factor;
37
38 public FuHashtableFast(int _capacity, float _factor)
39 {
40 if((_capacity<=0)||(_factor<=0.0))
41 throw new IllegalArgumentException();
42
43 factor=_factor;
44 table =new Entry[_capacity];
45 threshold =(int)(_capacity*_factor);
46 }
47
48 public FuHashtableFast(int _capacity)
49 {
50 this(_capacity,0.75f);
51 }
52
53 public FuHashtableFast()
54 {
55 this(21,0.75f);
56 }
57
58 public final int size()
59 {
60 return count;
61 }
62
63 public final boolean isEmpty()
64 {
65 return (count==0);
66 }
67
68 public final Enumeration keys()
69 {
70 return new Enumerator(table,true);
71 }
72
73 public final Enumeration elements()
74 {
75 return new Enumerator(table,false);
76 }
77
78 public final boolean contains(Object _value)
79 {
80 if(_value==null) throw new NullPointerException();
81
82 Entry[] tab=table;
83 for(int i=tab.length; i-->0; )
84 {
85 for(Entry e=tab[i]; e!=null; e=e.next)
86 if(e.value==_value)
87 return true;
88 }
89 return false;
90 }
91
92 public final boolean containsKey(Object _key)
93 {
94 Entry[] tab =table;
95 int hash =_key.hashCode();
96 int index=(hash&0x7FFFFFFF)%tab.length;
97
98 for(Entry e=tab[index]; e!=null; e=e.next)
99 if((e.hash==hash)&&(e.key==_key))
100 return true;
101
102 return false;
103 }
104
105 public final Object get(Object _key)
106 {
107 Entry[] tab =table;
108 int hash =_key.hashCode();
109 int index=(hash&0x7FFFFFFF)%tab.length;
110
111 for(Entry e=tab[index]; e!=null; e=e.next)
112 if((e.hash==hash)&&(e.key==_key))
113 return e.value;
114
115 return null;
116 }
117
118 private final void rehash()
119 {
120 int oldCapacity=table.length;
121 Entry[] oldTable =table;
122
123 int newCapacity=oldCapacity*3+1;
124 Entry newTable[] =new Entry[newCapacity];
125
126 threshold=(int)(newCapacity*factor);
127 table =newTable;
128
129 for(int i=oldCapacity; i-->0; )
130 {
131 for(Entry old=oldTable[i]; old!=null; )
132 {
133 Entry e=old;
134 old=old.next;
135
136 int index=(e.hash&0x7FFFFFFF)%newCapacity;
137 e.next=newTable[index];
138 newTable[index]=e;
139 }
140 }
141 }
142
143 public final Object put(Object _key, Object _value)
144 {
145 if(_value==null) throw new NullPointerException();
146
147 Entry[] tab =table;
148 int hash =_key.hashCode();
149 int index=(hash&0x7FFFFFFF)%tab.length;
150
151 for(Entry e=tab[index]; e!=null; e=e.next)
152 {
153 if((e.hash==hash)&&(e.key==_key))
154 {
155 Object old=e.value;
156 e.value=_value;
157 return old;
158 }
159 }
160
161 if(count>=threshold)
162 {
163 rehash();
164 return put(_key,_value);
165 }
166
167 Entry e =new Entry();
168 e.hash =hash;
169 e.key =_key;
170 e.value =_value;
171 e.next =tab[index];
172 tab[index]=e;
173 count++;
174 return null;
175 }
176
177 public final Object remove(Object key)
178 {
179 Entry[] tab=table;
180 int hash =key.hashCode();
181 int index=(hash & 0x7FFFFFFF) % tab.length;
182
183 for(Entry e=tab[index], prev=null; e!=null; prev=e, e=e.next)
184 {
185 if((e.hash==hash)&&(e.key==key))
186 {
187 if(prev!=null)
188 prev.next =e.next;
189 else
190 tab[index]=e.next;
191
192 count--;
193 return e.value;
194 }
195 }
196
197 return null;
198 }
199
200 public final void clear()
201 {
202 Entry[] tab=table;
203 for(int index=tab.length; --index>= 0; )
204 tab[index]=null;
205 count=0;
206 }
207
208 public final String toString()
209 {
210 return "FuHashtableFast("+count+")";
211 }
212
213 private static final class Enumerator
214 implements Enumeration
215 {
216 private boolean keys;
217 private int index;
218 private Entry[] table;
219 private Entry entry;
220
221 Enumerator(Entry[] _table, boolean _keys)
222 {
223 table=_table;
224 keys =_keys;
225 index=_table.length;
226 }
227
228 public final boolean hasMoreElements()
229 {
230 if(entry!=null) return true;
231
232 while(index-->0)
233 if((entry=table[index])!=null)
234 return true;
235
236 return false;
237 }
238
239 public final Object nextElement()
240 {
241 if(entry==null)
242 while((index>=0)&&((entry=table[index])==null))
243 index--;
244
245 if(entry!=null)
246 {
247 Entry e=entry;
248 entry=e.next;
249 return (keys ? e.key : e.value);
250 }
251 throw new NoSuchElementException("FuHashtableFast.Enumerator");
252 }
253 }
254
255 public static void main(String[] args)
256 {
257 final int NB=200000;
258
259 Hashtable nv=new Hashtable();
260 FuHashtableFast fv=new FuHashtableFast();
261 long debut,fin;
262
263 Integer[] te=new Integer[NB];
264 for(int i=0;i<NB;i++)
265 te[i]=new Integer(i);
266
267 debut=System.currentTimeMillis();
268 for(int i=0;i<NB;i++)
269 nv.put(te[i],te[i]);
270 fin=System.currentTimeMillis();
271 System.out.println("duree Stnd Hashtable: "+(fin-debut)+" ms");
272
273 debut=System.currentTimeMillis();
274 for(int i=0;i<NB;i++)
275 fv.put(te[i],te[i]);
276 fin=System.currentTimeMillis();
277 System.out.println("duree Fast Hashtable: "+(fin-debut)+" ms");
278
279 debut=System.currentTimeMillis();
280 for(int i=0;i<NB/100;i++)
281 nv.get(te[i]);
282 fin=System.currentTimeMillis();
283 System.out.println("duree Stnd Hashtable: "+(fin-debut)+" ms");
284
285 debut=System.currentTimeMillis();
286 for(int i=0;i<NB/100;i++)
287 fv.get(te[i]);
288 fin=System.currentTimeMillis();
289 System.out.println("duree Fast Hashtable: "+(fin-debut)+" ms");
290 }
291 }