ArrayMap.java revision 1938e34e42969053f1b553779fa21257a28d708d
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 libcore.util.EmptyArray; 20 21import java.util.Collection; 22import java.util.ConcurrentModificationException; 23import java.util.Map; 24import java.util.Set; 25 26/** 27 * ArrayMap is a generic key->value mapping data structure that is 28 * designed to be more memory efficient than a traditional {@link java.util.HashMap}. 29 * It keeps its mappings in an array data structure -- an integer array of hash 30 * codes for each item, and an Object array of the key/value pairs. This allows it to 31 * avoid having to create an extra object for every entry put in to the map, and it 32 * also tries to control the growth of the size of these arrays more aggressively 33 * (since growing them only requires copying the entries in the array, not rebuilding 34 * a hash map). 35 * 36 * <p>Note that this implementation is not intended to be appropriate for data structures 37 * that may contain large numbers of items. It is generally slower than a traditional 38 * HashMap, since lookups require a binary search and adds and removes require inserting 39 * and deleting entries in the array. For containers holding up to hundreds of items, 40 * the performance difference is not significant, less than 50%.</p> 41 * 42 * <p>Because this container is intended to better balance memory use, unlike most other 43 * standard Java containers it will shrink its array as items are removed from it. Currently 44 * you have no control over this shrinking -- if you set a capacity and then remove an 45 * item, it may reduce the capacity to better match the current size. In the future an 46 * explicit call to set the capacity should turn off this aggressive shrinking behavior.</p> 47 */ 48public final class ArrayMap<K, V> implements Map<K, V> { 49 private static final boolean DEBUG = false; 50 private static final String TAG = "ArrayMap"; 51 52 /** 53 * Attempt to spot concurrent modifications to this data structure. 54 * 55 * It's best-effort, but any time we can throw something more diagnostic than an 56 * ArrayIndexOutOfBoundsException deep in the ArrayMap internals it's going to 57 * save a lot of development time. 58 * 59 * Good times to look for CME include after any allocArrays() call and at the end of 60 * functions that change mSize (put/remove/clear). 61 */ 62 private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true; 63 64 /** 65 * The minimum amount by which the capacity of a ArrayMap will increase. 66 * This is tuned to be relatively space-efficient. 67 */ 68 private static final int BASE_SIZE = 4; 69 70 /** 71 * Maximum number of entries to have in array caches. 72 */ 73 private static final int CACHE_SIZE = 10; 74 75 /** 76 * Special hash array value that indicates the container is immutable. 77 */ 78 static final int[] EMPTY_IMMUTABLE_INTS = new int[0]; 79 80 /** 81 * @hide Special immutable empty ArrayMap. 82 */ 83 public static final ArrayMap EMPTY = new ArrayMap<>(-1); 84 85 /** 86 * Caches of small array objects to avoid spamming garbage. The cache 87 * Object[] variable is a pointer to a linked list of array objects. 88 * The first entry in the array is a pointer to the next array in the 89 * list; the second entry is a pointer to the int[] hash code array for it. 90 */ 91 static Object[] mBaseCache; 92 static int mBaseCacheSize; 93 static Object[] mTwiceBaseCache; 94 static int mTwiceBaseCacheSize; 95 96 final boolean mIdentityHashCode; 97 int[] mHashes; 98 Object[] mArray; 99 int mSize; 100 MapCollections<K, V> mCollections; 101 102 private static int binarySearchHashes(int[] hashes, int N, int hash) { 103 try { 104 return ContainerHelpers.binarySearch(hashes, N, hash); 105 } catch (ArrayIndexOutOfBoundsException e) { 106 if (CONCURRENT_MODIFICATION_EXCEPTIONS) { 107 throw new ConcurrentModificationException(); 108 } else { 109 throw e; // the cache is poisoned at this point, there's not much we can do 110 } 111 } 112 } 113 114 int indexOf(Object key, int hash) { 115 final int N = mSize; 116 117 // Important fast case: if nothing is in here, nothing to look for. 118 if (N == 0) { 119 return ~0; 120 } 121 122 int index = binarySearchHashes(mHashes, N, hash); 123 124 // If the hash code wasn't found, then we have no entry for this key. 125 if (index < 0) { 126 return index; 127 } 128 129 // If the key at the returned index matches, that's what we want. 130 if (key.equals(mArray[index<<1])) { 131 return index; 132 } 133 134 // Search for a matching key after the index. 135 int end; 136 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 137 if (key.equals(mArray[end << 1])) return end; 138 } 139 140 // Search for a matching key before the index. 141 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 142 if (key.equals(mArray[i << 1])) return i; 143 } 144 145 // Key not found -- return negative value indicating where a 146 // new entry for this key should go. We use the end of the 147 // hash chain to reduce the number of array entries that will 148 // need to be copied when inserting. 149 return ~end; 150 } 151 152 int indexOfNull() { 153 final int N = mSize; 154 155 // Important fast case: if nothing is in here, nothing to look for. 156 if (N == 0) { 157 return ~0; 158 } 159 160 int index = binarySearchHashes(mHashes, N, 0); 161 162 // If the hash code wasn't found, then we have no entry for this key. 163 if (index < 0) { 164 return index; 165 } 166 167 // If the key at the returned index matches, that's what we want. 168 if (null == mArray[index<<1]) { 169 return index; 170 } 171 172 // Search for a matching key after the index. 173 int end; 174 for (end = index + 1; end < N && mHashes[end] == 0; end++) { 175 if (null == mArray[end << 1]) return end; 176 } 177 178 // Search for a matching key before the index. 179 for (int i = index - 1; i >= 0 && mHashes[i] == 0; i--) { 180 if (null == mArray[i << 1]) return i; 181 } 182 183 // Key not found -- return negative value indicating where a 184 // new entry for this key should go. We use the end of the 185 // hash chain to reduce the number of array entries that will 186 // need to be copied when inserting. 187 return ~end; 188 } 189 190 private void allocArrays(final int size) { 191 if (mHashes == EMPTY_IMMUTABLE_INTS) { 192 throw new UnsupportedOperationException("ArrayMap is immutable"); 193 } 194 if (size == (BASE_SIZE*2)) { 195 synchronized (ArrayMap.class) { 196 if (mTwiceBaseCache != null) { 197 final Object[] array = mTwiceBaseCache; 198 mArray = array; 199 mTwiceBaseCache = (Object[])array[0]; 200 mHashes = (int[])array[1]; 201 array[0] = array[1] = null; 202 mTwiceBaseCacheSize--; 203 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 204 + " now have " + mTwiceBaseCacheSize + " entries"); 205 return; 206 } 207 } 208 } else if (size == BASE_SIZE) { 209 synchronized (ArrayMap.class) { 210 if (mBaseCache != null) { 211 final Object[] array = mBaseCache; 212 mArray = array; 213 mBaseCache = (Object[])array[0]; 214 mHashes = (int[])array[1]; 215 array[0] = array[1] = null; 216 mBaseCacheSize--; 217 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 218 + " now have " + mBaseCacheSize + " entries"); 219 return; 220 } 221 } 222 } 223 224 mHashes = new int[size]; 225 mArray = new Object[size<<1]; 226 } 227 228 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 229 if (hashes.length == (BASE_SIZE*2)) { 230 synchronized (ArrayMap.class) { 231 if (mTwiceBaseCacheSize < CACHE_SIZE) { 232 array[0] = mTwiceBaseCache; 233 array[1] = hashes; 234 for (int i=(size<<1)-1; i>=2; i--) { 235 array[i] = null; 236 } 237 mTwiceBaseCache = array; 238 mTwiceBaseCacheSize++; 239 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 240 + " now have " + mTwiceBaseCacheSize + " entries"); 241 } 242 } 243 } else if (hashes.length == BASE_SIZE) { 244 synchronized (ArrayMap.class) { 245 if (mBaseCacheSize < CACHE_SIZE) { 246 array[0] = mBaseCache; 247 array[1] = hashes; 248 for (int i=(size<<1)-1; i>=2; i--) { 249 array[i] = null; 250 } 251 mBaseCache = array; 252 mBaseCacheSize++; 253 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 254 + " now have " + mBaseCacheSize + " entries"); 255 } 256 } 257 } 258 } 259 260 /** 261 * Create a new empty ArrayMap. The default capacity of an array map is 0, and 262 * will grow once items are added to it. 263 */ 264 public ArrayMap() { 265 this(0, false); 266 } 267 268 /** 269 * Create a new ArrayMap with a given initial capacity. 270 */ 271 public ArrayMap(int capacity) { 272 this(capacity, false); 273 } 274 275 /** {@hide} */ 276 public ArrayMap(int capacity, boolean identityHashCode) { 277 mIdentityHashCode = identityHashCode; 278 279 // If this is immutable, use the sentinal EMPTY_IMMUTABLE_INTS 280 // instance instead of the usual EmptyArray.INT. The reference 281 // is checked later to see if the array is allowed to grow. 282 if (capacity < 0) { 283 mHashes = EMPTY_IMMUTABLE_INTS; 284 mArray = EmptyArray.OBJECT; 285 } else if (capacity == 0) { 286 mHashes = EmptyArray.INT; 287 mArray = EmptyArray.OBJECT; 288 } else { 289 allocArrays(capacity); 290 } 291 mSize = 0; 292 } 293 294 /** 295 * Create a new ArrayMap with the mappings from the given ArrayMap. 296 */ 297 public ArrayMap(ArrayMap<K, V> map) { 298 this(); 299 if (map != null) { 300 putAll(map); 301 } 302 } 303 304 /** 305 * Make the array map empty. All storage is released. 306 */ 307 @Override 308 public void clear() { 309 if (mSize > 0) { 310 final int[] ohashes = mHashes; 311 final Object[] oarray = mArray; 312 final int osize = mSize; 313 mHashes = EmptyArray.INT; 314 mArray = EmptyArray.OBJECT; 315 mSize = 0; 316 freeArrays(ohashes, oarray, osize); 317 } 318 if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) { 319 throw new ConcurrentModificationException(); 320 } 321 } 322 323 /** 324 * @hide 325 * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 326 */ 327 public void erase() { 328 if (mSize > 0) { 329 final int N = mSize<<1; 330 final Object[] array = mArray; 331 for (int i=0; i<N; i++) { 332 array[i] = null; 333 } 334 mSize = 0; 335 } 336 } 337 338 /** 339 * Ensure the array map can hold at least <var>minimumCapacity</var> 340 * items. 341 */ 342 public void ensureCapacity(int minimumCapacity) { 343 final int osize = mSize; 344 if (mHashes.length < minimumCapacity) { 345 final int[] ohashes = mHashes; 346 final Object[] oarray = mArray; 347 allocArrays(minimumCapacity); 348 if (mSize > 0) { 349 System.arraycopy(ohashes, 0, mHashes, 0, osize); 350 System.arraycopy(oarray, 0, mArray, 0, osize<<1); 351 } 352 freeArrays(ohashes, oarray, osize); 353 } 354 if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) { 355 throw new ConcurrentModificationException(); 356 } 357 } 358 359 /** 360 * Check whether a key exists in the array. 361 * 362 * @param key The key to search for. 363 * @return Returns true if the key exists, else false. 364 */ 365 @Override 366 public boolean containsKey(Object key) { 367 return indexOfKey(key) >= 0; 368 } 369 370 /** 371 * Returns the index of a key in the set. 372 * 373 * @param key The key to search for. 374 * @return Returns the index of the key if it exists, else a negative integer. 375 */ 376 public int indexOfKey(Object key) { 377 return key == null ? indexOfNull() 378 : indexOf(key, mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()); 379 } 380 381 int indexOfValue(Object value) { 382 final int N = mSize*2; 383 final Object[] array = mArray; 384 if (value == null) { 385 for (int i=1; i<N; i+=2) { 386 if (array[i] == null) { 387 return i>>1; 388 } 389 } 390 } else { 391 for (int i=1; i<N; i+=2) { 392 if (value.equals(array[i])) { 393 return i>>1; 394 } 395 } 396 } 397 return -1; 398 } 399 400 /** 401 * Check whether a value exists in the array. This requires a linear search 402 * through the entire array. 403 * 404 * @param value The value to search for. 405 * @return Returns true if the value exists, else false. 406 */ 407 @Override 408 public boolean containsValue(Object value) { 409 return indexOfValue(value) >= 0; 410 } 411 412 /** 413 * Retrieve a value from the array. 414 * @param key The key of the value to retrieve. 415 * @return Returns the value associated with the given key, 416 * or null if there is no such key. 417 */ 418 @Override 419 public V get(Object key) { 420 final int index = indexOfKey(key); 421 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 422 } 423 424 /** 425 * Return the key at the given index in the array. 426 * @param index The desired index, must be between 0 and {@link #size()}-1. 427 * @return Returns the key stored at the given index. 428 */ 429 public K keyAt(int index) { 430 return (K)mArray[index << 1]; 431 } 432 433 /** 434 * Return the value at the given index in the array. 435 * @param index The desired index, must be between 0 and {@link #size()}-1. 436 * @return Returns the value stored at the given index. 437 */ 438 public V valueAt(int index) { 439 return (V)mArray[(index << 1) + 1]; 440 } 441 442 /** 443 * Set the value at a given index in the array. 444 * @param index The desired index, must be between 0 and {@link #size()}-1. 445 * @param value The new value to store at this index. 446 * @return Returns the previous value at the given index. 447 */ 448 public V setValueAt(int index, V value) { 449 index = (index << 1) + 1; 450 V old = (V)mArray[index]; 451 mArray[index] = value; 452 return old; 453 } 454 455 /** 456 * Return true if the array map contains no items. 457 */ 458 @Override 459 public boolean isEmpty() { 460 return mSize <= 0; 461 } 462 463 /** 464 * Add a new value to the array map. 465 * @param key The key under which to store the value. If 466 * this key already exists in the array, its value will be replaced. 467 * @param value The value to store for the given key. 468 * @return Returns the old value that was stored for the given key, or null if there 469 * was no such key. 470 */ 471 @Override 472 public V put(K key, V value) { 473 final int osize = mSize; 474 final int hash; 475 int index; 476 if (key == null) { 477 hash = 0; 478 index = indexOfNull(); 479 } else { 480 hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode(); 481 index = indexOf(key, hash); 482 } 483 if (index >= 0) { 484 index = (index<<1) + 1; 485 final V old = (V)mArray[index]; 486 mArray[index] = value; 487 return old; 488 } 489 490 index = ~index; 491 if (osize >= mHashes.length) { 492 final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) 493 : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 494 495 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 496 497 final int[] ohashes = mHashes; 498 final Object[] oarray = mArray; 499 allocArrays(n); 500 501 if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 502 throw new ConcurrentModificationException(); 503 } 504 505 if (mHashes.length > 0) { 506 if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0"); 507 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 508 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 509 } 510 511 freeArrays(ohashes, oarray, osize); 512 } 513 514 if (index < osize) { 515 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index) 516 + " to " + (index+1)); 517 System.arraycopy(mHashes, index, mHashes, index + 1, osize - index); 518 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 519 } 520 521 if (CONCURRENT_MODIFICATION_EXCEPTIONS) { 522 if (osize != mSize || index >= mHashes.length) { 523 throw new ConcurrentModificationException(); 524 } 525 } 526 mHashes[index] = hash; 527 mArray[index<<1] = key; 528 mArray[(index<<1)+1] = value; 529 mSize++; 530 return null; 531 } 532 533 /** 534 * Special fast path for appending items to the end of the array without validation. 535 * The array must already be large enough to contain the item. 536 * @hide 537 */ 538 public void append(K key, V value) { 539 int index = mSize; 540 final int hash = key == null ? 0 541 : (mIdentityHashCode ? System.identityHashCode(key) : key.hashCode()); 542 if (index >= mHashes.length) { 543 throw new IllegalStateException("Array is full"); 544 } 545 if (index > 0 && mHashes[index-1] > hash) { 546 RuntimeException e = new RuntimeException("here"); 547 e.fillInStackTrace(); 548 Log.w(TAG, "New hash " + hash 549 + " is before end of array hash " + mHashes[index-1] 550 + " at index " + index + " key " + key, e); 551 put(key, value); 552 return; 553 } 554 mSize = index+1; 555 mHashes[index] = hash; 556 index <<= 1; 557 mArray[index] = key; 558 mArray[index+1] = value; 559 } 560 561 /** 562 * The use of the {@link #append} function can result in invalid array maps, in particular 563 * an array map where the same key appears multiple times. This function verifies that 564 * the array map is valid, throwing IllegalArgumentException if a problem is found. The 565 * main use for this method is validating an array map after unpacking from an IPC, to 566 * protect against malicious callers. 567 * @hide 568 */ 569 public void validate() { 570 final int N = mSize; 571 if (N <= 1) { 572 // There can't be dups. 573 return; 574 } 575 int basehash = mHashes[0]; 576 int basei = 0; 577 for (int i=1; i<N; i++) { 578 int hash = mHashes[i]; 579 if (hash != basehash) { 580 basehash = hash; 581 basei = i; 582 continue; 583 } 584 // We are in a run of entries with the same hash code. Go backwards through 585 // the array to see if any keys are the same. 586 final Object cur = mArray[i<<1]; 587 for (int j=i-1; j>=basei; j--) { 588 final Object prev = mArray[j<<1]; 589 if (cur == prev) { 590 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 591 } 592 if (cur != null && prev != null && cur.equals(prev)) { 593 throw new IllegalArgumentException("Duplicate key in ArrayMap: " + cur); 594 } 595 } 596 } 597 } 598 599 /** 600 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 601 * @param array The array whose contents are to be retrieved. 602 */ 603 public void putAll(ArrayMap<? extends K, ? extends V> array) { 604 final int N = array.mSize; 605 ensureCapacity(mSize + N); 606 if (mSize == 0) { 607 if (N > 0) { 608 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 609 System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 610 mSize = N; 611 } 612 } else { 613 for (int i=0; i<N; i++) { 614 put(array.keyAt(i), array.valueAt(i)); 615 } 616 } 617 } 618 619 /** 620 * Remove an existing key from the array map. 621 * @param key The key of the mapping to remove. 622 * @return Returns the value that was stored under the key, or null if there 623 * was no such key. 624 */ 625 @Override 626 public V remove(Object key) { 627 final int index = indexOfKey(key); 628 if (index >= 0) { 629 return removeAt(index); 630 } 631 632 return null; 633 } 634 635 /** 636 * Remove the key/value mapping at the given index. 637 * @param index The desired index, must be between 0 and {@link #size()}-1. 638 * @return Returns the value that was stored at this index. 639 */ 640 public V removeAt(int index) { 641 final Object old = mArray[(index << 1) + 1]; 642 final int osize = mSize; 643 final int nsize; 644 if (osize <= 1) { 645 // Now empty. 646 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 647 final int[] ohashes = mHashes; 648 final Object[] oarray = mArray; 649 mHashes = EmptyArray.INT; 650 mArray = EmptyArray.OBJECT; 651 freeArrays(ohashes, oarray, osize); 652 nsize = 0; 653 } else { 654 nsize = osize - 1; 655 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 656 // Shrunk enough to reduce size of arrays. We don't allow it to 657 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 658 // that and BASE_SIZE. 659 final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2); 660 661 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 662 663 final int[] ohashes = mHashes; 664 final Object[] oarray = mArray; 665 allocArrays(n); 666 667 if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 668 throw new ConcurrentModificationException(); 669 } 670 671 if (index > 0) { 672 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 673 System.arraycopy(ohashes, 0, mHashes, 0, index); 674 System.arraycopy(oarray, 0, mArray, 0, index << 1); 675 } 676 if (index < nsize) { 677 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize 678 + " to " + index); 679 System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index); 680 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 681 (nsize - index) << 1); 682 } 683 } else { 684 if (index < nsize) { 685 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize 686 + " to " + index); 687 System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index); 688 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 689 (nsize - index) << 1); 690 } 691 mArray[nsize << 1] = null; 692 mArray[(nsize << 1) + 1] = null; 693 } 694 } 695 if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { 696 throw new ConcurrentModificationException(); 697 } 698 mSize = nsize; 699 return (V)old; 700 } 701 702 /** 703 * Return the number of items in this array map. 704 */ 705 @Override 706 public int size() { 707 return mSize; 708 } 709 710 /** 711 * {@inheritDoc} 712 * 713 * <p>This implementation returns false if the object is not a map, or 714 * if the maps have different sizes. Otherwise, for each key in this map, 715 * values of both maps are compared. If the values for any key are not 716 * equal, the method returns false, otherwise it returns true. 717 */ 718 @Override 719 public boolean equals(Object object) { 720 if (this == object) { 721 return true; 722 } 723 if (object instanceof Map) { 724 Map<?, ?> map = (Map<?, ?>) object; 725 if (size() != map.size()) { 726 return false; 727 } 728 729 try { 730 for (int i=0; i<mSize; i++) { 731 K key = keyAt(i); 732 V mine = valueAt(i); 733 Object theirs = map.get(key); 734 if (mine == null) { 735 if (theirs != null || !map.containsKey(key)) { 736 return false; 737 } 738 } else if (!mine.equals(theirs)) { 739 return false; 740 } 741 } 742 } catch (NullPointerException ignored) { 743 return false; 744 } catch (ClassCastException ignored) { 745 return false; 746 } 747 return true; 748 } 749 return false; 750 } 751 752 /** 753 * {@inheritDoc} 754 */ 755 @Override 756 public int hashCode() { 757 final int[] hashes = mHashes; 758 final Object[] array = mArray; 759 int result = 0; 760 for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 761 Object value = array[v]; 762 result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 763 } 764 return result; 765 } 766 767 /** 768 * {@inheritDoc} 769 * 770 * <p>This implementation composes a string by iterating over its mappings. If 771 * this map contains itself as a key or a value, the string "(this Map)" 772 * will appear in its place. 773 */ 774 @Override 775 public String toString() { 776 if (isEmpty()) { 777 return "{}"; 778 } 779 780 StringBuilder buffer = new StringBuilder(mSize * 28); 781 buffer.append('{'); 782 for (int i=0; i<mSize; i++) { 783 if (i > 0) { 784 buffer.append(", "); 785 } 786 Object key = keyAt(i); 787 if (key != this) { 788 buffer.append(key); 789 } else { 790 buffer.append("(this Map)"); 791 } 792 buffer.append('='); 793 Object value = valueAt(i); 794 if (value != this) { 795 buffer.append(value); 796 } else { 797 buffer.append("(this Map)"); 798 } 799 } 800 buffer.append('}'); 801 return buffer.toString(); 802 } 803 804 // ------------------------------------------------------------------------ 805 // Interop with traditional Java containers. Not as efficient as using 806 // specialized collection APIs. 807 // ------------------------------------------------------------------------ 808 809 private MapCollections<K, V> getCollection() { 810 if (mCollections == null) { 811 mCollections = new MapCollections<K, V>() { 812 @Override 813 protected int colGetSize() { 814 return mSize; 815 } 816 817 @Override 818 protected Object colGetEntry(int index, int offset) { 819 return mArray[(index<<1) + offset]; 820 } 821 822 @Override 823 protected int colIndexOfKey(Object key) { 824 return indexOfKey(key); 825 } 826 827 @Override 828 protected int colIndexOfValue(Object value) { 829 return indexOfValue(value); 830 } 831 832 @Override 833 protected Map<K, V> colGetMap() { 834 return ArrayMap.this; 835 } 836 837 @Override 838 protected void colPut(K key, V value) { 839 put(key, value); 840 } 841 842 @Override 843 protected V colSetValue(int index, V value) { 844 return setValueAt(index, value); 845 } 846 847 @Override 848 protected void colRemoveAt(int index) { 849 removeAt(index); 850 } 851 852 @Override 853 protected void colClear() { 854 clear(); 855 } 856 }; 857 } 858 return mCollections; 859 } 860 861 /** 862 * Determine if the array map contains all of the keys in the given collection. 863 * @param collection The collection whose contents are to be checked against. 864 * @return Returns true if this array map contains a key for every entry 865 * in <var>collection</var>, else returns false. 866 */ 867 public boolean containsAll(Collection<?> collection) { 868 return MapCollections.containsAllHelper(this, collection); 869 } 870 871 /** 872 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 873 * @param map The map whose contents are to be retrieved. 874 */ 875 @Override 876 public void putAll(Map<? extends K, ? extends V> map) { 877 ensureCapacity(mSize + map.size()); 878 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 879 put(entry.getKey(), entry.getValue()); 880 } 881 } 882 883 /** 884 * Remove all keys in the array map that exist in the given collection. 885 * @param collection The collection whose contents are to be used to remove keys. 886 * @return Returns true if any keys were removed from the array map, else false. 887 */ 888 public boolean removeAll(Collection<?> collection) { 889 return MapCollections.removeAllHelper(this, collection); 890 } 891 892 /** 893 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 894 * @param collection The collection whose contents are to be used to determine which 895 * keys to keep. 896 * @return Returns true if any keys were removed from the array map, else false. 897 */ 898 public boolean retainAll(Collection<?> collection) { 899 return MapCollections.retainAllHelper(this, collection); 900 } 901 902 /** 903 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 904 * in the array map. 905 * 906 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 907 * requires generating a number of temporary objects and allocates additional state 908 * information associated with the container that will remain for the life of the container.</p> 909 * 910 * <p><b>Note:</b></p> the semantics of this 911 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 912 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 913 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 914 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 915 */ 916 @Override 917 public Set<Map.Entry<K, V>> entrySet() { 918 return getCollection().getEntrySet(); 919 } 920 921 /** 922 * Return a {@link java.util.Set} for iterating over and interacting with all keys 923 * in the array map. 924 * 925 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 926 * requires generating a number of temporary objects and allocates additional state 927 * information associated with the container that will remain for the life of the container.</p> 928 */ 929 @Override 930 public Set<K> keySet() { 931 return getCollection().getKeySet(); 932 } 933 934 /** 935 * Return a {@link java.util.Collection} for iterating over and interacting with all values 936 * in the array map. 937 * 938 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 939 * requires generating a number of temporary objects and allocates additional state 940 * information associated with the container that will remain for the life of the container.</p> 941 */ 942 @Override 943 public Collection<V> values() { 944 return getCollection().getValues(); 945 } 946} 947