ArrayMap.java revision f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccda
1/* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package android.util; 18 19import java.util.Collection; 20import java.util.Map; 21import java.util.Set; 22 23/** 24 * ArrayMap is a generic key->value mapping data structure that is 25 * designed to be more memory efficient than a traditional {@link java.util.HashMap}. 26 * It keeps its mappings in an array data structure -- an integer array of hash 27 * codes for each item, and an Object array of the key/value pairs. This allows it to 28 * avoid having to create an extra object for every entry put in to the map, and it 29 * also tries to control the growth of the size of these arrays more aggressively 30 * (since growing them only requires copying the entries in the array, not rebuilding 31 * a hash map). 32 * 33 * <p>Note that this implementation is not intended to be appropriate for data structures 34 * that may contain large numbers of items. It is generally slower than a traditional 35 * HashMap, since lookups require a binary search and adds and removes require inserting 36 * and deleting entries in the array. For containers holding up to hundreds of items, 37 * the performance difference is not significant, less than 50%. For larger numbers of items 38 * this data structure should be avoided.</p> 39 * 40 * <p><b>Note:</b> unlike {@link java.util.HashMap}, this container does not support 41 * null keys.</p> 42 * 43 * <p>Because this container is intended to better balance memory use, unlike most other 44 * standard Java containers it will shrink its array as items are removed from it. Currently 45 * you have no control over this shrinking -- if you set a capacity and then remove an 46 * item, it may reduce the capacity to better match the current size. In the future an 47 * explicitly call to set the capacity should turn off this aggressive shrinking behavior.</p> 48 * 49 * @hide 50 */ 51public final class ArrayMap<K, V> implements Map<K, V> { 52 private static final boolean DEBUG = false; 53 private static final String TAG = "ArrayMap"; 54 55 /** 56 * The minimum amount by which the capacity of a ArrayMap will increase. 57 * This is tuned to be relatively space-efficient. 58 */ 59 private static final int BASE_SIZE = 4; 60 61 /** 62 * Maximum number of entries to have in array caches. 63 */ 64 private static final int CACHE_SIZE = 10; 65 66 /** 67 * Caches of small array objects to avoid spamming garbage. The cache 68 * Object[] variable is a pointer to a linked list of array objects. 69 * The first entry in the array is a pointer to the next array in the 70 * list; the second entry is a pointer to the int[] hash code array for it. 71 */ 72 static Object[] mBaseCache; 73 static int mBaseCacheSize; 74 static Object[] mTwiceBaseCache; 75 static int mTwiceBaseCacheSize; 76 77 int[] mHashes; 78 Object[] mArray; 79 int mSize; 80 MapCollections<K, V> mCollections; 81 82 private int indexOf(Object key, int hash) { 83 final int N = mSize; 84 85 // Important fast case: if nothing is in here, nothing to look for. 86 if (N == 0) { 87 return ~0; 88 } 89 90 int index = SparseArray.binarySearch(mHashes, N, hash); 91 92 // If the hash code wasn't found, then we have no entry for this key. 93 if (index < 0) { 94 return index; 95 } 96 97 // If the key at the returned index matches, that's what we want. 98 if (mArray[index<<1].equals(key)) { 99 return index; 100 } 101 102 // Search for a matching key after the index. 103 int end; 104 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 105 if (mArray[end << 1].equals(key)) return end; 106 } 107 108 // Search for a matching key before the index. 109 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 110 if (mArray[i << 1].equals(key)) return i; 111 } 112 113 // Key not found -- return negative value indicating where a 114 // new entry for this key should go. We use the end of the 115 // hash chain to reduce the number of array entries that will 116 // need to be copied when inserting. 117 return ~end; 118 } 119 120 private void allocArrays(final int size) { 121 if (size == (BASE_SIZE*2)) { 122 synchronized (ArrayMap.class) { 123 if (mTwiceBaseCache != null) { 124 final Object[] array = mTwiceBaseCache; 125 mArray = array; 126 mTwiceBaseCache = (Object[])array[0]; 127 mHashes = (int[])array[1]; 128 array[0] = array[1] = null; 129 mTwiceBaseCacheSize--; 130 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 131 + " now have " + mTwiceBaseCacheSize + " entries"); 132 return; 133 } 134 } 135 } else if (size == BASE_SIZE) { 136 synchronized (ArrayMap.class) { 137 if (mBaseCache != null) { 138 final Object[] array = mBaseCache; 139 mArray = array; 140 mBaseCache = (Object[])array[0]; 141 mHashes = (int[])array[1]; 142 array[0] = array[1] = null; 143 mBaseCacheSize--; 144 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 145 + " now have " + mBaseCacheSize + " entries"); 146 return; 147 } 148 } 149 } 150 151 mHashes = new int[size]; 152 mArray = new Object[size<<1]; 153 } 154 155 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 156 if (hashes.length == (BASE_SIZE*2)) { 157 synchronized (ArrayMap.class) { 158 if (mTwiceBaseCacheSize < CACHE_SIZE) { 159 array[0] = mTwiceBaseCache; 160 array[1] = hashes; 161 for (int i=(size<<1)-1; i>=2; i--) { 162 array[i] = null; 163 } 164 mTwiceBaseCache = array; 165 mTwiceBaseCacheSize++; 166 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 167 + " now have " + mTwiceBaseCacheSize + " entries"); 168 } 169 } 170 } else if (hashes.length == BASE_SIZE) { 171 synchronized (ArrayMap.class) { 172 if (mBaseCacheSize < CACHE_SIZE) { 173 array[0] = mBaseCache; 174 array[1] = hashes; 175 for (int i=(size<<1)-1; i>=2; i--) { 176 array[i] = null; 177 } 178 mBaseCache = array; 179 mBaseCacheSize++; 180 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 181 + " now have " + mBaseCacheSize + " entries"); 182 } 183 } 184 } 185 } 186 187 /** 188 * Create a new empty ArrayMap. The default capacity of an array map is 0, and 189 * will grow once items are added to it. 190 */ 191 public ArrayMap() { 192 mHashes = SparseArray.EMPTY_INTS; 193 mArray = SparseArray.EMPTY_OBJECTS; 194 mSize = 0; 195 } 196 197 /** 198 * Create a new ArrayMap with a given initial capacity. 199 */ 200 public ArrayMap(int capacity) { 201 if (capacity == 0) { 202 mHashes = SparseArray.EMPTY_INTS; 203 mArray = SparseArray.EMPTY_OBJECTS; 204 } else { 205 allocArrays(capacity); 206 } 207 mSize = 0; 208 } 209 210 /** 211 * Make the array map empty. All storage is released. 212 */ 213 @Override 214 public void clear() { 215 freeArrays(mHashes, mArray, mSize); 216 mHashes = SparseArray.EMPTY_INTS; 217 mArray = SparseArray.EMPTY_OBJECTS; 218 mSize = 0; 219 } 220 221 /** 222 * Ensure the array map can hold at least <var>minimumCapacity</var> 223 * items. 224 */ 225 public void ensureCapacity(int minimumCapacity) { 226 if (mHashes.length < minimumCapacity) { 227 int[] ohashes = mHashes; 228 Object[] oarray = mArray; 229 allocArrays(minimumCapacity); 230 if (mHashes.length > 0) { 231 System.arraycopy(ohashes, 0, mHashes, 0, mHashes.length); 232 System.arraycopy(oarray, 0, mArray, 0, mArray.length); 233 } 234 freeArrays(ohashes, oarray, mSize); 235 } 236 } 237 238 /** 239 * Check whether a key exists in the array. 240 * 241 * @param key The key to search for. 242 * @return Returns true if the key exists, else false. 243 */ 244 @Override 245 public boolean containsKey(Object key) { 246 return indexOf(key, key.hashCode()) >= 0; 247 } 248 249 private int indexOfValue(Object value) { 250 final int N = mSize*2; 251 final Object[] array = mArray; 252 if (value == null) { 253 for (int i=1; i<N; i+=2) { 254 if (array[i] == null) { 255 return i>>1; 256 } 257 } 258 } else { 259 for (int i=1; i<N; i+=2) { 260 if (value.equals(array[i])) { 261 return i>>1; 262 } 263 } 264 } 265 return -1; 266 } 267 268 /** 269 * Check whether a value exists in the array. This requires a linear search 270 * through the entire array. 271 * 272 * @param value The value to search for. 273 * @return Returns true if the value exists, else false. 274 */ 275 @Override 276 public boolean containsValue(Object value) { 277 return indexOfValue(value) >= 0; 278 } 279 280 /** 281 * Retrieve a value from the array. 282 * @param key The key of the value to retrieve. 283 * @return Returns the value associated with the given key, 284 * or null if there is no such key. 285 */ 286 @Override 287 public V get(Object key) { 288 final int index = indexOf(key, key.hashCode()); 289 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 290 } 291 292 /** 293 * Return the key at the given index in the array. 294 * @param index The desired index, must be between 0 and {@link #size()}-1. 295 * @return Returns the key stored at the given index. 296 */ 297 public K keyAt(int index) { 298 return (K)mArray[index << 1]; 299 } 300 301 /** 302 * Return the value at the given index in the array. 303 * @param index The desired index, must be between 0 and {@link #size()}-1. 304 * @return Returns the value stored at the given index. 305 */ 306 public V valueAt(int index) { 307 return (V)mArray[(index << 1) + 1]; 308 } 309 310 /** 311 * Set the value at a given index in the array. 312 * @param index The desired index, must be between 0 and {@link #size()}-1. 313 * @param value The new value to store at this index. 314 * @return Returns the previous value at the given index. 315 */ 316 public V setValueAt(int index, V value) { 317 index = (index << 1) + 1; 318 V old = (V)mArray[index]; 319 mArray[index] = value; 320 return old; 321 } 322 323 /** 324 * Return true if the array map contains no items. 325 */ 326 @Override 327 public boolean isEmpty() { 328 return mSize <= 0; 329 } 330 331 /** 332 * Add a new value to the array map. 333 * @param key The key under which to store the value. <b>Must not be null.</b> If 334 * this key already exists in the array, its value will be replaced. 335 * @param value The value to store for the given key. 336 * @return Returns the old value that was stored for the given key, or null if there 337 * was no such key. 338 */ 339 @Override 340 public V put(K key, V value) { 341 final int hash = key.hashCode(); 342 int index = indexOf(key, hash); 343 if (index >= 0) { 344 index = (index<<1) + 1; 345 final V old = (V)mArray[index]; 346 mArray[index] = value; 347 return old; 348 } 349 350 index = ~index; 351 if (mSize >= mHashes.length) { 352 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 353 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 354 355 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 356 357 final int[] ohashes = mHashes; 358 final Object[] oarray = mArray; 359 allocArrays(n); 360 361 if (mHashes.length > 0) { 362 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 363 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 364 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 365 } 366 367 freeArrays(ohashes, oarray, mSize); 368 } 369 370 if (index < mSize) { 371 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 372 + " to " + (index+1)); 373 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 374 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 375 } 376 377 mHashes[index] = hash; 378 mArray[index<<1] = key; 379 mArray[(index<<1)+1] = value; 380 mSize++; 381 return null; 382 } 383 384 /** 385 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 386 * @param array The array whose contents are to be retrieved. 387 */ 388 public void putAll(ArrayMap<? extends K, ? extends V> array) { 389 final int N = array.mSize; 390 ensureCapacity(mSize + N); 391 for (int i=0; i<N; i++) { 392 put(array.keyAt(i), array.valueAt(i)); 393 } 394 } 395 396 /** 397 * Remove an existing key from the array map. 398 * @param key The key of the mapping to remove. 399 * @return Returns the value that was stored under the key, or null if there 400 * was no such key. 401 */ 402 @Override 403 public V remove(Object key) { 404 int index = indexOf(key, key.hashCode()); 405 if (index >= 0) { 406 return removeAt(index); 407 } 408 409 return null; 410 } 411 412 /** 413 * Remove the key/value mapping at the given index. 414 * @param index The desired index, must be between 0 and {@link #size()}-1. 415 * @return Returns the value that was stored at this index. 416 */ 417 public V removeAt(int index) { 418 final V old = (V)mArray[(index << 1) + 1]; 419 if (mSize <= 1) { 420 // Now empty. 421 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 422 freeArrays(mHashes, mArray, mSize); 423 mHashes = SparseArray.EMPTY_INTS; 424 mArray = SparseArray.EMPTY_OBJECTS; 425 mSize = 0; 426 } else { 427 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 428 // Shrunk enough to reduce size of arrays. We don't allow it to 429 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 430 // that and BASE_SIZE. 431 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 432 433 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 434 435 final int[] ohashes = mHashes; 436 final Object[] oarray = mArray; 437 allocArrays(n); 438 439 mSize--; 440 if (index > 0) { 441 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 442 System.arraycopy(ohashes, 0, mHashes, 0, index); 443 System.arraycopy(oarray, 0, mArray, 0, index << 1); 444 } 445 if (index < mSize) { 446 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 447 + " to " + index); 448 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 449 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 450 (mSize - index) << 1); 451 } 452 } else { 453 mSize--; 454 if (index < mSize) { 455 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 456 + " to " + index); 457 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 458 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 459 (mSize - index) << 1); 460 } 461 mArray[mSize << 1] = null; 462 mArray[(mSize << 1) + 1] = null; 463 } 464 } 465 return old; 466 } 467 468 /** 469 * Return the number of items in this array map. 470 */ 471 @Override 472 public int size() { 473 return mSize; 474 } 475 476 // ------------------------------------------------------------------------ 477 // Interop with traditional Java containers. Not as efficient as using 478 // specialized collection APIs. 479 // ------------------------------------------------------------------------ 480 481 private MapCollections<K, V> getCollection() { 482 if (mCollections == null) { 483 mCollections = new MapCollections<K, V>() { 484 @Override 485 protected int colGetSize() { 486 return mSize; 487 } 488 489 @Override 490 protected Object colGetEntry(int index, int offset) { 491 return mArray[(index<<1) + offset]; 492 } 493 494 @Override 495 protected int colIndexOfKey(Object key) { 496 return indexOf(key, key.hashCode()); 497 } 498 499 @Override 500 protected int colIndexOfValue(Object value) { 501 return indexOfValue(value); 502 } 503 504 @Override 505 protected Map<K, V> colGetMap() { 506 return ArrayMap.this; 507 } 508 509 @Override 510 protected void colPut(K key, V value) { 511 put(key, value); 512 } 513 514 @Override 515 protected V colSetValue(int index, V value) { 516 return setValueAt(index, value); 517 } 518 519 @Override 520 protected void colRemoveAt(int index) { 521 removeAt(index); 522 } 523 524 @Override 525 protected void colClear() { 526 clear(); 527 } 528 }; 529 } 530 return mCollections; 531 } 532 533 /** 534 * Determine if the array map contains all of the keys in the given collection. 535 * @param collection The collection whose contents are to be checked against. 536 * @return Returns true if this array map contains a key for every entry 537 * in <var>collection</var>, else returns false. 538 */ 539 public boolean containsAll(Collection<?> collection) { 540 return MapCollections.containsAllHelper(this, collection); 541 } 542 543 /** 544 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 545 * @param map The map whose contents are to be retrieved. 546 */ 547 @Override 548 public void putAll(Map<? extends K, ? extends V> map) { 549 ensureCapacity(mSize + map.size()); 550 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 551 put(entry.getKey(), entry.getValue()); 552 } 553 } 554 555 /** 556 * Remove all keys in the array map that exist in the given collection. 557 * @param collection The collection whose contents are to be used to remove keys. 558 * @return Returns true if any keys were removed from the array map, else false. 559 */ 560 public boolean removeAll(Collection<?> collection) { 561 return MapCollections.removeAllHelper(this, collection); 562 } 563 564 /** 565 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 566 * @param collection The collection whose contents are to be used to determine which 567 * keys to keep. 568 * @return Returns true if any keys were removed from the array map, else false. 569 */ 570 public boolean retainAll(Collection<?> collection) { 571 return MapCollections.retainAllHelper(this, collection); 572 } 573 574 /** 575 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 576 * in the array map. 577 * 578 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 579 * requires generating a number of temporary objects.</p> 580 * 581 * <p><b>Note:</b></p> the semantics of this 582 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 583 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 584 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 585 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 586 */ 587 @Override 588 public Set<Map.Entry<K, V>> entrySet() { 589 return getCollection().getEntrySet(); 590 } 591 592 /** 593 * Return a {@link java.util.Set} for iterating over and interacting with all keys 594 * in the array map. 595 * 596 * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it 597 * requires generating a number of temporary objects.</p> 598 */ 599 @Override 600 public Set<K> keySet() { 601 return getCollection().getKeySet(); 602 } 603 604 /** 605 * Return a {@link java.util.Collection} for iterating over and interacting with all values 606 * in the array map. 607 * 608 * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it 609 * requires generating a number of temporary objects.</p> 610 */ 611 @Override 612 public Collection<V> values() { 613 return getCollection().getValues(); 614 } 615} 616