Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

370
LINES

< > BotCompany Repo | #1031038 // CompactHashMap - version using only one array

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (3193L/19K).

1  
/*
2  
 * #!
3  
 * Ontopia Engine
4  
 * #-
5  
 * Copyright (C) 2001 - 2013 The Ontopia Project
6  
 * #-
7  
 * Licensed under the Apache License, Version 2.0 (the "License");
8  
 * you may not use this file except in compliance with the License.
9  
 * You may obtain a copy of the License at
10  
 * 
11  
 *      http://www.apache.org/licenses/LICENSE-2.0
12  
 * 
13  
 * Unless required by applicable law or agreed to in writing, software
14  
 * distributed under the License is distributed on an "AS IS" BASIS,
15  
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16  
 * See the License for the specific language governing permissions and
17  
 * limitations under the License.
18  
 * !#
19  
 */
20  
21  
sclass CompactHashMap<K, V> extends AbstractMap<K, V> {
22  
  final static int INITIAL_SIZE = 3;
23  
  final static double LOAD_FACTOR = 0.6;
24  
25  
  // This object is used to represent null, should clients use that as
26  
  final static Object nullObject = new Object();
27  
  
28  
  /**
29  
   * When a key is deleted this object is put into the hashtable in
30  
   * its place, so that other entries with the same key (collisions)
31  
   * further down the hashtable are not lost after we delete an object
32  
   * in the collision chain.
33  
   */
34  
  final static Object deletedObject = new Object();
35  
  int elements;
36  
  int freecells;
37  
  O[] table; // key, value, key, value, ...
38  
  int modCount;
39  
40  
  *() {
41  
    this(INITIAL_SIZE);
42  
  }
43  
44  
  *(int size) {
45  
    table = new Object[(size==0 ? 1 : size)*2];
46  
    elements = 0;
47  
    freecells = tableSize();
48  
    modCount = 0;
49  
  }
50  
51  
  // ===== MAP IMPLEMENTATION =============================================
52  
53  
  /**
54  
   * Returns the number of key/value mappings in this map.
55  
   */
56  
  public synchronized int size() {
57  
    return elements;
58  
  }
59  
  
60  
  /**
61  
   * Returns <tt>true</tt> if this map contains no mappings.
62  
   */
63  
  public synchronized boolean isEmpty() {
64  
    return elements == 0;
65  
  }
66  
67  
  /**
68  
   * Removes all key/value mappings in the map.
69  
   */
70  
  public synchronized void clear() {
71  
    elements = 0;
72  
    for (int ix = 0; ix < tableSize(); ix++) {
73  
      key(ix, null);
74  
      value(ix, null);
75  
    }
76  
    freecells = tableSize();
77  
    modCount++;
78  
  }
79  
  
80  
  /**
81  
   * Returns <tt>true</tt> if this map contains the specified key.
82  
   */
83  
  public synchronized boolean containsKey(Object k) {
84  
    return key(findKeyIndex(k)) != null;
85  
  }
86  
  
87  
  /**
88  
   * Returns <tt>true</tt> if this map contains the specified value.
89  
   */
90  
  public synchronized boolean containsValue(Object v) {
91  
    if (v == null)
92  
      v = (V)nullObject;
93  
94  
    for (int ix = 0; ix < tableSize(); ix++)
95  
      if (value(ix) != null && value(ix).equals(v))
96  
        return true;
97  
98  
    return false;
99  
  }
100  
101  
  /**
102  
   * Returns a read-only set view of the map's keys.
103  
   */
104  
  public synchronized Set<Entry<K, V>> entrySet() {
105  
    throw new UnsupportedOperationException();
106  
  }
107  
108  
  /**
109  
   * Removes the mapping with key k, if there is one, and returns its
110  
   * value, if there is one, and null if there is none.
111  
   */
112  
  public synchronized V remove(Object k) {
113  
    int index = findKeyIndex(k);
114  
115  
    // we found the right position, now do the removal
116  
    if (key(index) != null) {
117  
      // we found the object
118  
119  
      // same problem here as with put
120  
      V v = value(index);
121  
      key(index, deletedObject);
122  
      value(index, deletedObject);
123  
      modCount++;
124  
      elements--;
125  
      return v;
126  
    } else
127  
      // we did not find the key
128  
      return null;
129  
  }
130  
131  
  /**
132  
   * Adds the specified mapping to this map, returning the old value for
133  
   * the mapping, if there was one.
134  
   */
135  
  public synchronized V put(K k, V v) {
136  
    if (k == null)
137  
      k = (K)nullObject;
138  
139  
    int hash = k.hashCode();
140  
    int index = (hash & 0x7FFFFFFF) % tableSize();
141  
    int offset = 1;
142  
    int deletedix = -1;
143  
    
144  
    // search for the key (continue while !null and !this key)
145  
    while(key(index) != null &&
146  
          !(key(index).hashCode() == hash &&
147  
            key(index).equals(k))) {
148  
149  
      // if there's a deleted mapping here we can put this mapping here,
150  
      // provided it's not in here somewhere else already
151  
      if (key(index) == deletedObject)
152  
        deletedix = index;
153  
      
154  
      index = ((index + offset) & 0x7FFFFFFF) % tableSize();
155  
      offset = offset*2 + 1;
156  
157  
      if (offset == -1)
158  
        offset = 2;
159  
    }
160  
    
161  
    if (key(index) == null) { // wasn't present already
162  
      if (deletedix != -1) // reusing a deleted cell
163  
        index = deletedix;
164  
      else
165  
        freecells--;
166  
167  
      modCount++;
168  
      elements++;
169  
170  
      key(index, k);
171  
      value(index, v);
172  
      
173  
      // rehash with increased capacity
174  
      if (1 - (freecells / (double) tableSize()) > LOAD_FACTOR)
175  
        rehash(tableSize()*2 + 1);
176  
      return null;
177  
    } else { // was there already
178  
      modCount++;
179  
      V oldv = value(index);
180  
      value(index, v);
181  
      return oldv;
182  
    }
183  
  }
184  
185  
  /**
186  
   * INTERNAL: Rehashes the hashmap to a bigger size.
187  
   */
188  
  void rehash(int newCapacity) {
189  
    int oldCapacity = tableSize();
190  
    O[] newTable = new Object[newCapacity*2];
191  
192  
    for (int ix = 0; ix < oldCapacity; ix++) {
193  
      Object k = key(ix);
194  
      if (k == null || k == deletedObject)
195  
        continue;
196  
      
197  
      int hash = k.hashCode();
198  
      int index = (hash & 0x7FFFFFFF) % newCapacity;
199  
      int offset = 1;
200  
201  
      // search for the key
202  
      while(newTable[index*2] != null) { // no need to test for duplicates
203  
        index = ((index + offset) & 0x7FFFFFFF) % newCapacity;
204  
        offset = offset*2 + 1;
205  
206  
        if (offset == -1)
207  
          offset = 2;
208  
      }
209  
210  
      newTable[index*2] = k;
211  
      newTable[index*2+1] = value(ix);
212  
    }
213  
214  
    table = newTable;
215  
    freecells = tableSize() - elements;
216  
  }
217  
218  
  /**
219  
   * Returns the value for the key k, if there is one, and null if
220  
   * there is none.
221  
   */
222  
  public synchronized V get(Object k) {
223  
    return value(findKeyIndex(k));
224  
  }
225  
226  
  /**
227  
   * Returns a virtual read-only collection containing all the values
228  
   * in the map.
229  
   */
230  
  public synchronized Collection<V> values() {
231  
    return new ValueCollection();
232  
  }
233  
234  
  /**
235  
   * Returns a virtual read-only set of all the keys in the map.
236  
   */
237  
  public synchronized Set<K> keySet() {
238  
    return new KeySet();
239  
  }
240  
241  
  // --- Internal utilities
242  
243  
  final int findKeyIndex(Object k) {
244  
    if (k == null)
245  
      k = nullObject;
246  
247  
    int hash = k.hashCode();
248  
    int index = (hash & 0x7FFFFFFF) % tableSize();
249  
    int offset = 1;
250  
251  
    // search for the key (continue while !null and !this key)
252  
    while(key(index) != null &&
253  
          !(key(index).hashCode() == hash &&
254  
            key(index).equals(k))) {
255  
      index = ((index + offset) & 0x7FFFFFFF) % tableSize();
256  
      offset = offset*2 + 1;
257  
258  
      if (offset == -1)
259  
        offset = 2;
260  
    }
261  
    return index;
262  
  }
263  
  
264  
  // --- Key set
265  
266  
  class KeySet<K> extends AbstractSet<K> {
267  
    public synchronized int size() {
268  
      return elements;
269  
    }
270  
271  
    public synchronized boolean contains(Object k) {
272  
      return containsKey(k);
273  
    }
274  
275  
    public synchronized Iterator<K> iterator() {
276  
      return new KeyIterator();
277  
    }
278  
  }
279  
280  
  class KeyIterator<K> implements Iterator<K> {
281  
    private int ix;
282  
    
283  
    private KeyIterator() {
284  
      // walk up to first value, so that hasNext() and next() return
285  
      // correct results
286  
      for (; ix < tableSize(); ix++)
287  
        if (value(ix) != null && key(ix) != deletedObject)
288  
          break;
289  
    }
290  
291  
    public synchronized boolean hasNext() {
292  
      return ix < tableSize();
293  
    }
294  
295  
    public synchronized void remove() {
296  
      throw new UnsupportedOperationException("Collection is read-only");
297  
    }
298  
299  
    public synchronized K next() {
300  
      if (ix >= tableSize())
301  
        throw new NoSuchElementException();
302  
      K key = (K) key(ix++);
303  
      
304  
      // walk up to next value
305  
      for (; ix < tableSize(); ix++)
306  
        if (key(ix) != null && key(ix) != deletedObject)
307  
          break;
308  
      
309  
      // ix now either points to next key, or outside array (if no next)
310  
      return key;
311  
    }
312  
  }
313  
  
314  
  // --- Value collection
315  
316  
  class ValueCollection<V> extends AbstractCollection<V> {
317  
    public synchronized int size() {
318  
      return elements;
319  
    }
320  
321  
    public synchronized Iterator<V> iterator() {
322  
      return new ValueIterator();
323  
    }
324  
325  
    public synchronized boolean contains(Object v) {
326  
      return containsValue(v);
327  
    }
328  
  }
329  
330  
  class ValueIterator<V> implements Iterator<V> {
331  
    private int ix;
332  
    
333  
    private ValueIterator() {
334  
      // walk up to first value, so that hasNext() and next() return
335  
      // correct results
336  
      for (; ix < table.length/2; ix++)
337  
        if (value(ix) != null && value(ix) != deletedObject)
338  
          break;
339  
    }
340  
341  
    public synchronized boolean hasNext() {
342  
      return ix < tableSize();
343  
    }
344  
345  
    public synchronized void remove() {
346  
      throw new UnsupportedOperationException("Collection is read-only");
347  
    }
348  
349  
    public synchronized V next() {
350  
      if (ix >= tableSize())
351  
        throw new NoSuchElementException();
352  
      V value = (V) value(ix++);
353  
      
354  
      // walk up to next value
355  
      for (; ix < tableSize(); ix++)
356  
        if (value(ix) != null && value(ix) != deletedObject)
357  
          break;
358  
      
359  
      // ix now either points to next value, or outside array (if no next)
360  
      return value;
361  
    }
362  
  }
363  
  
364  
  K key(int i) { ret (K) table[i*2]; }
365  
  void key(int i, O key) { table[i*2] = key; }
366  
  V value(int i) { ret (V) table[i*2+1]; }
367  
  void value(int i, O value) { table[i*2+1] = value; }
368  
  
369  
  int tableSize() { ret table.length/2; }
370  
}

Author comment

Began life as a copy of #1013303

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, vouqrxazstgt

No comments. add comment

Snippet ID: #1031038
Snippet name: CompactHashMap - version using only one array
Eternal ID of this version: #1031038/8
Text MD5: 5d4341d04c0a1b2b5ab7e1ce895548ae
Transpilation MD5: bae976d36e741ef3c53fbcf2a4815ebb
Author: stefan
Category: javax / collections
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2021-04-25 21:13:47
Source code size: 9757 bytes / 370 lines
Pitched / IR pitched: No / No
Views / Downloads: 165 / 239
Version history: 7 change(s)
Referenced in: [show references]