HashTable


1   /*
2   
3      Copyright 2000-2001  The Apache Software Foundation 
4   
5      Licensed under the Apache License, Version 2.0 (the "License");
6      you may not use this file except in compliance with the License.
7      You may obtain a copy of the License at
8   
9          http://www.apache.org/licenses/LICENSE-2.0
10  
11     Unless required by applicable law or agreed to in writing, software
12     distributed under the License is distributed on an "AS IS" BASIS,
13     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14     See the License for the specific language governing permissions and
15     limitations under the License.
16  
17   */
18  package org.apache.batik.dom.util;
19  
20  import java.io.Serializable  ;
21  
22  /**
23   * A simple hashtable, not synchronized, with fixed load factor.
24   *
25   * @author <a HREF="mailto:stephane@hillion.org">Stephane Hillion</a>
26   * @version $Id: HashTable.java,v 1.7 2005/02/22 09:13:02 cam Exp $
27   */
28  
29  public class HashTable implements Serializable   {
30          
31      /**
32       * The initial capacity
33       */
34      protected final static int INITIAL_CAPACITY = 11;
35  
36      /**
37       * The underlying array
38       */
39      protected Entry[] table;
40          
41      /**
42       * The number of entries
43       */
44      protected int count;
45          
46      /**
47       * Creates a new table.
48       */
49      public HashTable() {
50      table = new Entry[INITIAL_CAPACITY];
51      }
52  
53      /**
54       * Creates a new table.
55       * @param c The initial capacity.
56       */
57      public HashTable(int c) {
58      table = new Entry[c];
59      }
60  
61      /**
62       * Creates a copy of the given HashTable object.
63       * @param t The table to copy.
64       */
65      public HashTable(HashTable t) {
66      count = t.count;
67      table = new Entry[t.table.length];
68      for (int i = 0; i < table.length; i++) {
69          Entry e = t.table[i];
70          Entry n = null;
71          if (e != null) {
72          n = new Entry(e.hash, e.key, e.value, null);
73          table[i] = n;
74          e = e.next;
75          while (e != null) {
76              n.next = new Entry(e.hash, e.key, e.value, null);
77              n = n.next;
78              e = e.next;
79          }
80          }
81      }
82      }
83  
84      /**
85       * Returns the size of this table.
86       */
87      public int size() {
88      return count;
89      }
90      
91      /**
92       * Gets the value of a variable
93       * @return the value or null
94       */
95      public Object   get(Object   key) {
96      int hash  = key.hashCode() & 0x7FFFFFFF;
97      int index = hash % table.length;
98      
99      for (Entry e = table[index]; e != null; e = e.next) {
100         if ((e.hash == hash) && e.key.equals(key)) {
101         return e.value;
102         }
103     }
104     return null;
105     }
106     
107     /**
108      * Sets a new value for the given variable
109      * @return the old value or null
110      */
111     public Object   put(Object   key, Object   value) {
112     int hash  = key.hashCode() & 0x7FFFFFFF;
113     int index = hash % table.length;
114     
115     for (Entry e = table[index]; e != null; e = e.next) {
116         if ((e.hash == hash) && e.key.equals(key)) {
117         Object   old = e.value;
118         e.value = value;
119         return old;
120         }
121     }
122     
123     // The key is not in the hash table
124         int len = table.length;
125     if (count++ >= (len * 3) >>> 2) {
126         rehash();
127         index = hash % table.length;
128     }
129     
130     Entry e = new Entry(hash, key, value, table[index]);
131     table[index] = e;
132     return null;
133     }
134 
135     /**
136      * Removes an entry from the table.
137      * @return the value or null.
138      */
139     public Object   remove(Object   key) {
140     int hash  = key.hashCode() & 0x7FFFFFFF;
141     int index = hash % table.length;
142     
143     Entry p = null;
144     for (Entry e = table[index]; e != null; e = e.next) {
145         if ((e.hash == hash) && e.key.equals(key)) {
146         Object   result = e.value;
147         if (p == null) {
148             table[index] = e.next;
149         } else {
150             p.next = e.next;
151         }
152         count--;
153         return result;
154         }
155         p = e;
156     }
157     return null;
158     }
159 
160     /**
161      * Returns the key at the given position or null.
162      */
163     public Object   key(int index) {
164     if (index < 0 || index >= count) {
165         return null;
166     }
167     int j = 0;
168     for (int i = 0; i < table.length; i++) {
169         Entry e = table[i];
170         if (e == null) {
171         continue;
172         }
173         do {
174         if (j++ == index) {
175             return e.key;
176         }
177         e = e.next;
178         } while (e != null);
179     }
180     return null;
181     }
182 
183     /**
184      * Returns the item at the given position.
185      */
186     public Object   item(int index) {
187     if (index < 0 || index >= count) {
188         return null;
189     }
190     int j = 0;
191     for (int i = 0; i < table.length; i++) {
192         Entry e = table[i];
193         if (e == null) {
194         continue;
195         }
196         do {
197         if (j++ == index) {
198             return e.value;
199         }
200         e = e.next;
201         } while (e != null);
202     }
203     return null;
204     }
205 
206     /**
207      * Clears the map.
208      */
209     public void clear() {
210         for (int i = 0; i < table.length; i++) {
211             table[i] = null;
212         }
213     count = 0;
214     }
215 
216     /**
217      * Rehash the table
218      */
219     protected void rehash () {
220     Entry[] oldTable = table;
221     
222     table = new Entry[oldTable.length * 2 + 1];
223     
224     for (int i = oldTable.length-1; i >= 0; i--) {
225         for (Entry old = oldTable[i]; old != null;) {
226         Entry e = old;
227         old = old.next;
228         
229         int index = e.hash % table.length;
230         e.next = table[index];
231         table[index] = e;
232         }
233     }
234     }
235 
236     /**
237      * To manage collisions
238      */
239     protected static class Entry implements Serializable   {
240     /**
241      * The hash code
242      */
243     public int hash;
244     
245     /**
246      * The key
247      */
248     public Object   key;
249     
250     /**
251      * The value
252      */
253     public Object   value;
254     
255     /**
256      * The next entry
257      */
258     public Entry next;
259     
260     /**
261      * Creates a new entry
262      */
263     public Entry(int hash, Object   key, Object   value, Entry next) {
264         this.hash  = hash;
265         this.key   = key;
266         this.value = value;
267         this.next  = next;
268     }
269     }
270 }
271
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags