ArrayMap.java revision 450d8c5b7c936b00fd0d40b5d68670df0fe56daa
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%.</p> 38 * 39 * <p><b>Note:</b> unlike {@link java.util.HashMap}, this container does not support 40 * null keys.</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 * The minimum amount by which the capacity of a ArrayMap will increase. 54 * This is tuned to be relatively space-efficient. 55 */ 56 private static final int BASE_SIZE = 4; 57 58 /** 59 * Maximum number of entries to have in array caches. 60 */ 61 private static final int CACHE_SIZE = 10; 62 63 /** 64 * @hide Special immutable empty ArrayMap. 65 */ 66 public static final ArrayMap EMPTY = new ArrayMap(true); 67 68 /** 69 * Caches of small array objects to avoid spamming garbage. The cache 70 * Object[] variable is a pointer to a linked list of array objects. 71 * The first entry in the array is a pointer to the next array in the 72 * list; the second entry is a pointer to the int[] hash code array for it. 73 */ 74 static Object[] mBaseCache; 75 static int mBaseCacheSize; 76 static Object[] mTwiceBaseCache; 77 static int mTwiceBaseCacheSize; 78 79 /** 80 * Special hash array value that indicates the container is immutable. 81 */ 82 static final int[] EMPTY_IMMUTABLE_INTS = new int[0]; 83 84 int[] mHashes; 85 Object[] mArray; 86 int mSize; 87 MapCollections<K, V> mCollections; 88 89 private int indexOf(Object key, int hash) { 90 final int N = mSize; 91 92 // Important fast case: if nothing is in here, nothing to look for. 93 if (N == 0) { 94 return ~0; 95 } 96 97 int index = ContainerHelpers.binarySearch(mHashes, N, hash); 98 99 // If the hash code wasn't found, then we have no entry for this key. 100 if (index < 0) { 101 return index; 102 } 103 104 // If the key at the returned index matches, that's what we want. 105 if (mArray[index<<1].equals(key)) { 106 return index; 107 } 108 109 // Search for a matching key after the index. 110 int end; 111 for (end = index + 1; end < N && mHashes[end] == hash; end++) { 112 if (mArray[end << 1].equals(key)) return end; 113 } 114 115 // Search for a matching key before the index. 116 for (int i = index - 1; i >= 0 && mHashes[i] == hash; i--) { 117 if (mArray[i << 1].equals(key)) return i; 118 } 119 120 // Key not found -- return negative value indicating where a 121 // new entry for this key should go. We use the end of the 122 // hash chain to reduce the number of array entries that will 123 // need to be copied when inserting. 124 return ~end; 125 } 126 127 private void allocArrays(final int size) { 128 if (mHashes == EMPTY_IMMUTABLE_INTS) { 129 throw new UnsupportedOperationException("ArrayMap is immutable"); 130 } 131 if (size == (BASE_SIZE*2)) { 132 synchronized (ArrayMap.class) { 133 if (mTwiceBaseCache != null) { 134 final Object[] array = mTwiceBaseCache; 135 mArray = array; 136 mTwiceBaseCache = (Object[])array[0]; 137 mHashes = (int[])array[1]; 138 array[0] = array[1] = null; 139 mTwiceBaseCacheSize--; 140 if (DEBUG) Log.d(TAG, "Retrieving 2x cache " + mHashes 141 + " now have " + mTwiceBaseCacheSize + " entries"); 142 return; 143 } 144 } 145 } else if (size == BASE_SIZE) { 146 synchronized (ArrayMap.class) { 147 if (mBaseCache != null) { 148 final Object[] array = mBaseCache; 149 mArray = array; 150 mBaseCache = (Object[])array[0]; 151 mHashes = (int[])array[1]; 152 array[0] = array[1] = null; 153 mBaseCacheSize--; 154 if (DEBUG) Log.d(TAG, "Retrieving 1x cache " + mHashes 155 + " now have " + mBaseCacheSize + " entries"); 156 return; 157 } 158 } 159 } 160 161 mHashes = new int[size]; 162 mArray = new Object[size<<1]; 163 } 164 165 private static void freeArrays(final int[] hashes, final Object[] array, final int size) { 166 if (hashes.length == (BASE_SIZE*2)) { 167 synchronized (ArrayMap.class) { 168 if (mTwiceBaseCacheSize < CACHE_SIZE) { 169 array[0] = mTwiceBaseCache; 170 array[1] = hashes; 171 for (int i=(size<<1)-1; i>=2; i--) { 172 array[i] = null; 173 } 174 mTwiceBaseCache = array; 175 mTwiceBaseCacheSize++; 176 if (DEBUG) Log.d(TAG, "Storing 2x cache " + array 177 + " now have " + mTwiceBaseCacheSize + " entries"); 178 } 179 } 180 } else if (hashes.length == BASE_SIZE) { 181 synchronized (ArrayMap.class) { 182 if (mBaseCacheSize < CACHE_SIZE) { 183 array[0] = mBaseCache; 184 array[1] = hashes; 185 for (int i=(size<<1)-1; i>=2; i--) { 186 array[i] = null; 187 } 188 mBaseCache = array; 189 mBaseCacheSize++; 190 if (DEBUG) Log.d(TAG, "Storing 1x cache " + array 191 + " now have " + mBaseCacheSize + " entries"); 192 } 193 } 194 } 195 } 196 197 /** 198 * Create a new empty ArrayMap. The default capacity of an array map is 0, and 199 * will grow once items are added to it. 200 */ 201 public ArrayMap() { 202 mHashes = ContainerHelpers.EMPTY_INTS; 203 mArray = ContainerHelpers.EMPTY_OBJECTS; 204 mSize = 0; 205 } 206 207 /** 208 * Create a new ArrayMap with a given initial capacity. 209 */ 210 public ArrayMap(int capacity) { 211 if (capacity == 0) { 212 mHashes = ContainerHelpers.EMPTY_INTS; 213 mArray = ContainerHelpers.EMPTY_OBJECTS; 214 } else { 215 allocArrays(capacity); 216 } 217 mSize = 0; 218 } 219 220 private ArrayMap(boolean immutable) { 221 mHashes = EMPTY_IMMUTABLE_INTS; 222 mArray = ContainerHelpers.EMPTY_OBJECTS; 223 mSize = 0; 224 } 225 226 /** 227 * Create a new ArrayMap with the mappings from the given ArrayMap. 228 */ 229 public ArrayMap(ArrayMap map) { 230 this(); 231 if (map != null) { 232 putAll(map); 233 } 234 } 235 236 /** 237 * Make the array map empty. All storage is released. 238 */ 239 @Override 240 public void clear() { 241 if (mSize > 0) { 242 freeArrays(mHashes, mArray, mSize); 243 mHashes = ContainerHelpers.EMPTY_INTS; 244 mArray = ContainerHelpers.EMPTY_OBJECTS; 245 mSize = 0; 246 } 247 } 248 249 /** 250 * @hide 251 * Like {@link #clear}, but doesn't reduce the capacity of the ArrayMap. 252 */ 253 public void erase() { 254 if (mSize > 0) { 255 final int N = mSize<<1; 256 final Object[] array = mArray; 257 for (int i=0; i<N; i++) { 258 array[i] = null; 259 } 260 } 261 } 262 263 /** 264 * Ensure the array map can hold at least <var>minimumCapacity</var> 265 * items. 266 */ 267 public void ensureCapacity(int minimumCapacity) { 268 if (mHashes.length < minimumCapacity) { 269 final int[] ohashes = mHashes; 270 final Object[] oarray = mArray; 271 allocArrays(minimumCapacity); 272 if (mSize > 0) { 273 System.arraycopy(ohashes, 0, mHashes, 0, mSize); 274 System.arraycopy(oarray, 0, mArray, 0, mSize<<1); 275 } 276 freeArrays(ohashes, oarray, mSize); 277 } 278 } 279 280 /** 281 * Check whether a key exists in the array. 282 * 283 * @param key The key to search for. 284 * @return Returns true if the key exists, else false. 285 */ 286 @Override 287 public boolean containsKey(Object key) { 288 return indexOf(key, key.hashCode()) >= 0; 289 } 290 291 private int indexOfValue(Object value) { 292 final int N = mSize*2; 293 final Object[] array = mArray; 294 if (value == null) { 295 for (int i=1; i<N; i+=2) { 296 if (array[i] == null) { 297 return i>>1; 298 } 299 } 300 } else { 301 for (int i=1; i<N; i+=2) { 302 if (value.equals(array[i])) { 303 return i>>1; 304 } 305 } 306 } 307 return -1; 308 } 309 310 /** 311 * Check whether a value exists in the array. This requires a linear search 312 * through the entire array. 313 * 314 * @param value The value to search for. 315 * @return Returns true if the value exists, else false. 316 */ 317 @Override 318 public boolean containsValue(Object value) { 319 return indexOfValue(value) >= 0; 320 } 321 322 /** 323 * Retrieve a value from the array. 324 * @param key The key of the value to retrieve. 325 * @return Returns the value associated with the given key, 326 * or null if there is no such key. 327 */ 328 @Override 329 public V get(Object key) { 330 final int index = indexOf(key, key.hashCode()); 331 return index >= 0 ? (V)mArray[(index<<1)+1] : null; 332 } 333 334 /** 335 * Return the key at the given index in the array. 336 * @param index The desired index, must be between 0 and {@link #size()}-1. 337 * @return Returns the key stored at the given index. 338 */ 339 public K keyAt(int index) { 340 return (K)mArray[index << 1]; 341 } 342 343 /** 344 * Return the value at the given index in the array. 345 * @param index The desired index, must be between 0 and {@link #size()}-1. 346 * @return Returns the value stored at the given index. 347 */ 348 public V valueAt(int index) { 349 return (V)mArray[(index << 1) + 1]; 350 } 351 352 /** 353 * Set the value at a given index in the array. 354 * @param index The desired index, must be between 0 and {@link #size()}-1. 355 * @param value The new value to store at this index. 356 * @return Returns the previous value at the given index. 357 */ 358 public V setValueAt(int index, V value) { 359 index = (index << 1) + 1; 360 V old = (V)mArray[index]; 361 mArray[index] = value; 362 return old; 363 } 364 365 /** 366 * Return true if the array map contains no items. 367 */ 368 @Override 369 public boolean isEmpty() { 370 return mSize <= 0; 371 } 372 373 /** 374 * Add a new value to the array map. 375 * @param key The key under which to store the value. <b>Must not be null.</b> If 376 * this key already exists in the array, its value will be replaced. 377 * @param value The value to store for the given key. 378 * @return Returns the old value that was stored for the given key, or null if there 379 * was no such key. 380 */ 381 @Override 382 public V put(K key, V value) { 383 final int hash = key.hashCode(); 384 int index = indexOf(key, hash); 385 if (index >= 0) { 386 index = (index<<1) + 1; 387 final V old = (V)mArray[index]; 388 mArray[index] = value; 389 return old; 390 } 391 392 index = ~index; 393 if (mSize >= mHashes.length) { 394 final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) 395 : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); 396 397 if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); 398 399 final int[] ohashes = mHashes; 400 final Object[] oarray = mArray; 401 allocArrays(n); 402 403 if (mHashes.length > 0) { 404 if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); 405 System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); 406 System.arraycopy(oarray, 0, mArray, 0, oarray.length); 407 } 408 409 freeArrays(ohashes, oarray, mSize); 410 } 411 412 if (index < mSize) { 413 if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) 414 + " to " + (index+1)); 415 System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); 416 System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); 417 } 418 419 mHashes[index] = hash; 420 mArray[index<<1] = key; 421 mArray[(index<<1)+1] = value; 422 mSize++; 423 return null; 424 } 425 426 /** 427 * Special fast path for appending items to the end of the array without validation. 428 * The array must already be large enough to contain the item. 429 * @hide 430 */ 431 public void append(K key, V value) { 432 int index = mSize; 433 final int hash = key.hashCode(); 434 if (index >= mHashes.length) { 435 throw new IllegalStateException("Array is full"); 436 } 437 if (index > 0 && mHashes[index-1] > hash) { 438 RuntimeException e = new RuntimeException("here"); 439 e.fillInStackTrace(); 440 Log.w(TAG, "New hash " + hash 441 + " is before end of array hash " + mHashes[index-1] 442 + " at index " + index + " key " + key, e); 443 put(key, value); 444 return; 445 } 446 mSize = index+1; 447 mHashes[index] = hash; 448 index <<= 1; 449 mArray[index] = key; 450 mArray[index+1] = value; 451 } 452 453 /** 454 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>array</var> 455 * @param array The array whose contents are to be retrieved. 456 */ 457 public void putAll(ArrayMap<? extends K, ? extends V> array) { 458 final int N = array.mSize; 459 ensureCapacity(mSize + N); 460 if (mSize == 0) { 461 if (N > 0) { 462 System.arraycopy(array.mHashes, 0, mHashes, 0, N); 463 System.arraycopy(array.mArray, 0, mArray, 0, N<<1); 464 mSize = N; 465 } 466 } else { 467 for (int i=0; i<N; i++) { 468 put(array.keyAt(i), array.valueAt(i)); 469 } 470 } 471 } 472 473 /** 474 * Remove an existing key from the array map. 475 * @param key The key of the mapping to remove. 476 * @return Returns the value that was stored under the key, or null if there 477 * was no such key. 478 */ 479 @Override 480 public V remove(Object key) { 481 int index = indexOf(key, key.hashCode()); 482 if (index >= 0) { 483 return removeAt(index); 484 } 485 486 return null; 487 } 488 489 /** 490 * Remove the key/value mapping at the given index. 491 * @param index The desired index, must be between 0 and {@link #size()}-1. 492 * @return Returns the value that was stored at this index. 493 */ 494 public V removeAt(int index) { 495 final V old = (V)mArray[(index << 1) + 1]; 496 if (mSize <= 1) { 497 // Now empty. 498 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); 499 freeArrays(mHashes, mArray, mSize); 500 mHashes = ContainerHelpers.EMPTY_INTS; 501 mArray = ContainerHelpers.EMPTY_OBJECTS; 502 mSize = 0; 503 } else { 504 if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { 505 // Shrunk enough to reduce size of arrays. We don't allow it to 506 // shrink smaller than (BASE_SIZE*2) to avoid flapping between 507 // that and BASE_SIZE. 508 final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); 509 510 if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); 511 512 final int[] ohashes = mHashes; 513 final Object[] oarray = mArray; 514 allocArrays(n); 515 516 mSize--; 517 if (index > 0) { 518 if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); 519 System.arraycopy(ohashes, 0, mHashes, 0, index); 520 System.arraycopy(oarray, 0, mArray, 0, index << 1); 521 } 522 if (index < mSize) { 523 if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize 524 + " to " + index); 525 System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); 526 System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, 527 (mSize - index) << 1); 528 } 529 } else { 530 mSize--; 531 if (index < mSize) { 532 if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize 533 + " to " + index); 534 System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); 535 System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, 536 (mSize - index) << 1); 537 } 538 mArray[mSize << 1] = null; 539 mArray[(mSize << 1) + 1] = null; 540 } 541 } 542 return old; 543 } 544 545 /** 546 * Return the number of items in this array map. 547 */ 548 @Override 549 public int size() { 550 return mSize; 551 } 552 553 /** 554 * {@inheritDoc} 555 * 556 * <p>This implementation returns false if the object is not a map, or 557 * if the maps have different sizes. Otherwise, for each key in this map, 558 * values of both maps are compared. If the values for any key are not 559 * equal, the method returns false, otherwise it returns true. 560 */ 561 @Override 562 public boolean equals(Object object) { 563 if (this == object) { 564 return true; 565 } 566 if (object instanceof Map) { 567 Map<?, ?> map = (Map<?, ?>) object; 568 if (size() != map.size()) { 569 return false; 570 } 571 572 try { 573 for (int i=0; i<mSize; i++) { 574 K key = keyAt(i); 575 V mine = valueAt(i); 576 Object theirs = map.get(key); 577 if (mine == null) { 578 if (theirs != null || !map.containsKey(key)) { 579 return false; 580 } 581 } else if (!mine.equals(theirs)) { 582 return false; 583 } 584 } 585 } catch (NullPointerException ignored) { 586 return false; 587 } catch (ClassCastException ignored) { 588 return false; 589 } 590 return true; 591 } 592 return false; 593 } 594 595 /** 596 * {@inheritDoc} 597 */ 598 @Override 599 public int hashCode() { 600 final int[] hashes = mHashes; 601 final Object[] array = mArray; 602 int result = 0; 603 for (int i = 0, v = 1, s = mSize; i < s; i++, v+=2) { 604 Object value = array[v]; 605 result += hashes[i] ^ (value == null ? 0 : value.hashCode()); 606 } 607 return result; 608 } 609 610 /** 611 * {@inheritDoc} 612 * 613 * <p>This implementation composes a string by iterating over its mappings. If 614 * this map contains itself as a key or a value, the string "(this Map)" 615 * will appear in its place. 616 */ 617 @Override 618 public String toString() { 619 if (isEmpty()) { 620 return "{}"; 621 } 622 623 StringBuilder buffer = new StringBuilder(mSize * 28); 624 buffer.append('{'); 625 for (int i=0; i<mSize; i++) { 626 if (i > 0) { 627 buffer.append(", "); 628 } 629 Object key = keyAt(i); 630 if (key != this) { 631 buffer.append(key); 632 } else { 633 buffer.append("(this Map)"); 634 } 635 buffer.append('='); 636 Object value = valueAt(i); 637 if (value != this) { 638 buffer.append(value); 639 } else { 640 buffer.append("(this Map)"); 641 } 642 } 643 buffer.append('}'); 644 return buffer.toString(); 645 } 646 647 // ------------------------------------------------------------------------ 648 // Interop with traditional Java containers. Not as efficient as using 649 // specialized collection APIs. 650 // ------------------------------------------------------------------------ 651 652 private MapCollections<K, V> getCollection() { 653 if (mCollections == null) { 654 mCollections = new MapCollections<K, V>() { 655 @Override 656 protected int colGetSize() { 657 return mSize; 658 } 659 660 @Override 661 protected Object colGetEntry(int index, int offset) { 662 return mArray[(index<<1) + offset]; 663 } 664 665 @Override 666 protected int colIndexOfKey(Object key) { 667 return indexOf(key, key.hashCode()); 668 } 669 670 @Override 671 protected int colIndexOfValue(Object value) { 672 return indexOfValue(value); 673 } 674 675 @Override 676 protected Map<K, V> colGetMap() { 677 return ArrayMap.this; 678 } 679 680 @Override 681 protected void colPut(K key, V value) { 682 put(key, value); 683 } 684 685 @Override 686 protected V colSetValue(int index, V value) { 687 return setValueAt(index, value); 688 } 689 690 @Override 691 protected void colRemoveAt(int index) { 692 removeAt(index); 693 } 694 695 @Override 696 protected void colClear() { 697 clear(); 698 } 699 }; 700 } 701 return mCollections; 702 } 703 704 /** 705 * Determine if the array map contains all of the keys in the given collection. 706 * @param collection The collection whose contents are to be checked against. 707 * @return Returns true if this array map contains a key for every entry 708 * in <var>collection</var>, else returns false. 709 */ 710 public boolean containsAll(Collection<?> collection) { 711 return MapCollections.containsAllHelper(this, collection); 712 } 713 714 /** 715 * Perform a {@link #put(Object, Object)} of all key/value pairs in <var>map</var> 716 * @param map The map whose contents are to be retrieved. 717 */ 718 @Override 719 public void putAll(Map<? extends K, ? extends V> map) { 720 ensureCapacity(mSize + map.size()); 721 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 722 put(entry.getKey(), entry.getValue()); 723 } 724 } 725 726 /** 727 * Remove all keys in the array map that exist in the given collection. 728 * @param collection The collection whose contents are to be used to remove keys. 729 * @return Returns true if any keys were removed from the array map, else false. 730 */ 731 public boolean removeAll(Collection<?> collection) { 732 return MapCollections.removeAllHelper(this, collection); 733 } 734 735 /** 736 * Remove all keys in the array map that do <b>not</b> exist in the given collection. 737 * @param collection The collection whose contents are to be used to determine which 738 * keys to keep. 739 * @return Returns true if any keys were removed from the array map, else false. 740 */ 741 public boolean retainAll(Collection<?> collection) { 742 return MapCollections.retainAllHelper(this, collection); 743 } 744 745 /** 746 * Return a {@link java.util.Set} for iterating over and interacting with all mappings 747 * in the array map. 748 * 749 * <p><b>Note:</b> this is a very inefficient way to access the array contents, it 750 * requires generating a number of temporary objects.</p> 751 * 752 * <p><b>Note:</b></p> the semantics of this 753 * Set are subtly different than that of a {@link java.util.HashMap}: most important, 754 * the {@link java.util.Map.Entry Map.Entry} object returned by its iterator is a single 755 * object that exists for the entire iterator, so you can <b>not</b> hold on to it 756 * after calling {@link java.util.Iterator#next() Iterator.next}.</p> 757 */ 758 @Override 759 public Set<Map.Entry<K, V>> entrySet() { 760 return getCollection().getEntrySet(); 761 } 762 763 /** 764 * Return a {@link java.util.Set} for iterating over and interacting with all keys 765 * in the array map. 766 * 767 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 768 * requires generating a number of temporary objects.</p> 769 */ 770 @Override 771 public Set<K> keySet() { 772 return getCollection().getKeySet(); 773 } 774 775 /** 776 * Return a {@link java.util.Collection} for iterating over and interacting with all values 777 * in the array map. 778 * 779 * <p><b>Note:</b> this is a fairly inefficient way to access the array contents, it 780 * requires generating a number of temporary objects.</p> 781 */ 782 @Override 783 public Collection<V> values() { 784 return getCollection().getValues(); 785 } 786} 787