ArrayMap.java revision 08735185f8105710e18ad02297461bec9268e514
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 * Create a new ArrayMap with the mappings from the given ArrayMap. 211 */ 212 public ArrayMap(ArrayMap map) { 213 this(); 214 if (map != null) { 215 putAll(map); 216 } 217 } 218 219 220 /** 221 * Make the array map empty. All storage is released. 222 */ 223 @Override 224 public void clear() { 225 if (mSize != 0) { 226 freeArrays(mHashes, mArray, mSize); 227 mHashes = SparseArray.EMPTY_INTS; 228 mArray = SparseArray.EMPTY_OBJECTS; 229 mSize = 0; 230 } 231 } 232 233 /** 234 * Ensure the array map can hold at least <var>minimumCapacity</var> 235 * items. 236 */ 237 public void ensureCapacity(int minimumCapacity) { 238 if (mHashes.length < minimumCapacity) { 239 int[] ohashes = mHashes; 240 Object[] oarray = mArray; 241 allocArrays(minimumCapacity); 242 if (mSize > 0) { 243 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 244 System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 245 } 246 freeArrays(ohashes, oarray, mSize); 247 } 248 } 249 250 /** 251 * Check whether a key exists in the array. 252 * 253 * @param key The key to search for. 254 * @return Returns true if the key exists, else false. 255 */ 256 @Override 257 public boolean containsKey(Object key) { 258 return indexOf(key, key.hashCode()) >= 0; 259 } 260 261 private int indexOfValue(Object value) { 262 final int N = mSize*2; 263 final Object[] array = mArray; 264 if (value == null) { 265 for (int i=1; i<N; i+=2) { 266 if (array[i] == null) { 267 return i>>1; 268 } 269 } 270 } else { 271 for (int i=1; i<N; i+=2) { 272 if (value.equals(array[i])) { 273 return i>>1; 274 } 275 } 276 } 277 return -1; 278 } 279 280 /** 281 * Check whether a value exists in the array. This requires a linear search 282 * through the entire array. 283 * 284 * @param value The value to search for. 285 * @return Returns true if the value exists, else false. 286 */ 287 @Override 288 public boolean containsValue(Object value) { 289 return indexOfValue(value) >= 0; 290 } 291 292 /** 293 * Retrieve a value from the array. 294 * @param key The key of the value to retrieve. 295 * @return Returns the value associated with the given key, 296 * or null if there is no such key. 297 */ 298 @Override 299 public V get(Object key) { 300 final int index = indexOf(key, key.hashCode()); 301 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 302 } 303 304 /** 305 * Return the key at the given index in the array. 306 * @param index The desired index, must be between 0 and {@link #size()}-1. 307 * @return Returns the key stored at the given index. 308 */ 309 public K keyAt(int index) { 310 return (K)mArray[index << 1]; 311 } 312 313 /** 314 * Return the value at the given index in the array. 315 * @param index The desired index, must be between 0 and {@link #size()}-1. 316 * @return Returns the value stored at the given index. 317 */ 318 public V valueAt(int index) { 319 return (V)mArray[(index << 1) + 1]; 320 } 321 322 /** 323 * Set the value at a given index in the array. 324 * @param index The desired index, must be between 0 and {@link #size()}-1. 325 * @param value The new value to store at this index. 326 * @return Returns the previous value at the given index. 327 */ 328 public V setValueAt(int index, V value) { 329 index = (index << 1) + 1; 330 V old = (V)mArray[index]; 331 mArray[index] = value; 332 return old; 333 } 334 335 /** 336 * Return true if the array map contains no items. 337 */ 338 @Override 339 public boolean isEmpty() { 340 return mSize <= 0; 341 } 342 343 /** 344 * Add a new value to the array map. 345 * @param key The key under which to store the value. <b>Must not be null.</b> If 346 * this key already exists in the array, its value will be replaced. 347 * @param value The value to store for the given key. 348 * @return Returns the old value that was stored for the given key, or null if there 349 * was no such key. 350 */ 351 @Override 352 public V put(K key, V value) { 353 final int hash = key.hashCode(); 354 int index = indexOf(key, hash); 355 if (index >= 0) { 356 index = (index<<1) + 1; 357 final V old = (V)mArray[index]; 358 mArray[index] = value; 359 return old; 360 } 361 362 index = ~index; 363 if (mSize >= mHashes.length) { 364 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 365 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 366 367 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 368 369 final int[] ohashes = mHashes; 370 final Object[] oarray = mArray; 371 allocArrays(n); 372 373 if (mHashes.length > 0) { 374 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 375 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 376 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 377 } 378 379 freeArrays(ohashes, oarray, mSize); 380 } 381 382 if (index < mSize) { 383 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 384 + " to " + (index+1)); 385 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 386 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 387 } 388 389 mHashes[index] = hash; 390 mArray[index<<1] = key; 391 mArray[(index<<1)+1] = value; 392 mSize++; 393 return null; 394 } 395 396 /** 397 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 398 * @param array The array whose contents are to be retrieved. 399 */ 400 public void putAll(ArrayMap<? extends K, ? extends V> array) { 401 final int N = array.mSize; 402 ensureCapacity(mSize + N); 403 for (int i=0; i<N; i++) { 404 put(array.keyAt(i), array.valueAt(i)); 405 } 406 } 407 408 /** 409 * Remove an existing key from the array map. 410 * @param key The key of the mapping to remove. 411 * @return Returns the value that was stored under the key, or null if there 412 * was no such key. 413 */ 414 @Override 415 public V remove(Object key) { 416 int index = indexOf(key, key.hashCode()); 417 if (index >= 0) { 418 return removeAt(index); 419 } 420 421 return null; 422 } 423 424 /** 425 * Remove the key/value mapping at the given index. 426 * @param index The desired index, must be between 0 and {@link #size()}-1. 427 * @return Returns the value that was stored at this index. 428 */ 429 public V removeAt(int index) { 430 final V old = (V)mArray[(index << 1) + 1]; 431 if (mSize <= 1) { 432 // Now empty. 433 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 434 freeArrays(mHashes, mArray, mSize); 435 mHashes = SparseArray.EMPTY_INTS; 436 mArray = SparseArray.EMPTY_OBJECTS; 437 mSize = 0; 438 } else { 439 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 440 // Shrunk enough to reduce size of arrays. We don't allow it to 441 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 442 // that and BASE_SIZE. 443 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 444 445 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 446 447 final int[] ohashes = mHashes; 448 final Object[] oarray = mArray; 449 allocArrays(n); 450 451 mSize--; 452 if (index > 0) { 453 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 454 System.arraycopy(ohashes, 0, mHashes, 0, index); 455 System.arraycopy(oarray, 0, mArray, 0, index << 1); 456 } 457 if (index < mSize) { 458 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 459 + " to " + index); 460 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 461 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 462 (mSize - index) << 1); 463 } 464 } else { 465 mSize--; 466 if (index < mSize) { 467 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 468 + " to " + index); 469 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 470 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 471 (mSize - index) << 1); 472 } 473 mArray[mSize << 1] = null; 474 mArray[(mSize << 1) + 1] = null; 475 } 476 } 477 return old; 478 } 479 480 /** 481 * Return the number of items in this array map. 482 */ 483 @Override 484 public int size() { 485 return mSize; 486 } 487 488 // ------------------------------------------------------------------------ 489 // Interop with traditional Java containers. Not as efficient as using 490 // specialized collection APIs. 491 // ------------------------------------------------------------------------ 492 493 private MapCollections<K, V> getCollection() { 494 if (mCollections == null) { 495 mCollections = new MapCollections<K, V>() { 496 @Override 497 protected int colGetSize() { 498 return mSize; 499 } 500 501 @Override 502 protected Object colGetEntry(int index, int offset) { 503 return mArray[(index<<1) + offset]; 504 } 505 506 @Override 507 protected int colIndexOfKey(Object key) { 508 return indexOf(key, key.hashCode()); 509 } 510 511 @Override 512 protected int colIndexOfValue(Object value) { 513 return indexOfValue(value); 514 } 515 516 @Override 517 protected Map<K, V> colGetMap() { 518 return ArrayMap.this; 519 } 520 521 @Override 522 protected void colPut(K key, V value) { 523 put(key, value); 524 } 525 526 @Override 527 protected V colSetValue(int index, V value) { 528 return setValueAt(index, value); 529 } 530 531 @Override 532 protected void colRemoveAt(int index) { 533 removeAt(index); 534 } 535 536 @Override 537 protected void colClear() { 538 clear(); 539 } 540 }; 541 } 542 return mCollections; 543 } 544 545 /** 546 * Determine if the array map contains all of the keys in the given collection. 547 * @param collection The collection whose contents are to be checked against. 548 * @return Returns true if this array map contains a key for every entry 549 * in <var>collection</var>, else returns false. 550 */ 551 public boolean containsAll(Collection<?> collection) { 552 return MapCollections.containsAllHelper(this, collection); 553 } 554 555 /** 556 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 557 * @param map The map whose contents are to be retrieved. 558 */ 559 @Override 560 public void putAll(Map<? extends K, ? extends V> map) { 561 ensureCapacity(mSize + map.size()); 562 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 563 put(entry.getKey(), entry.getValue()); 564 } 565 } 566 567 /** 568 * Remove all keys in the array map that exist in the given collection. 569 * @param collection The collection whose contents are to be used to remove keys. 570 * @return Returns true if any keys were removed from the array map, else false. 571 */ 572 public boolean removeAll(Collection<?> collection) { 573 return MapCollections.removeAllHelper(this, collection); 574 } 575 576 /** 577 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 578 * @param collection The collection whose contents are to be used to determine which 579 * keys to keep. 580 * @return Returns true if any keys were removed from the array map, else false. 581 */ 582 public boolean retainAll(Collection<?> collection) { 583 return MapCollections.retainAllHelper(this, collection); 584 } 585 586 /** 587 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 588 * in the array map. 589 * 590 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 591 * requires generating a number of temporary objects.</p> 592 * 593 * <p><b>Note:</b></p> the semantics of this 594 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 595 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 596 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 597 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 598 */ 599 @Override 600 public Set<Map.Entry<K, V>> entrySet() { 601 return getCollection().getEntrySet(); 602 } 603 604 /** 605 * Return a {@link java.util.Set} for iterating over and interacting with all keys 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 Set<K> keySet() { 613 return getCollection().getKeySet(); 614 } 615 616 /** 617 * Return a {@link java.util.Collection} for iterating over and interacting with all values 618 * in the array map. 619 * 620 * <p><b>Note:</b> this is a fair inefficient way to access the array contents, it 621 * requires generating a number of temporary objects.</p> 622 */ 623 @Override 624 public Collection<V> values() { 625 return getCollection().getValues(); 626 } 627} 628