Hashtable.java revision e26ba79900d471d02d656f686926918ef7dc751f
1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.IOException; 21c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Blochimport java.io.InvalidObjectException; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 24c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Blochimport java.io.ObjectStreamField; 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 27adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 28438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * Hashtable is a synchronized implementation of {@link Map}. All optional operations are supported. 29f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 30438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * <p>Neither keys nor values can be null. (Use {@code HashMap} or {@code LinkedHashMap} if you 31438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * need null keys or values.) 32f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 33c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param <K> the type of keys maintained by this map 34c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param <V> the type of mapped values 35438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * @see HashMap 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 37c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Blochpublic class Hashtable<K, V> extends Dictionary<K, V> 38c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Map<K, V>, Cloneable, Serializable { 39c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 40c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Min capacity (other than zero) for a Hashtable. Must be a power of two 41c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * greater than 1 (and less than 1 << 30). 42c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 43c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final int MINIMUM_CAPACITY = 4; 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 45c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 46c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Max capacity for a Hashtable. Must be a power of two >= MINIMUM_CAPACITY. 47c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 48c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final int MAXIMUM_CAPACITY = 1 << 30; 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 50c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 51c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * An empty table shared by all zero-capacity maps (typically from default 52c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * constructor). It is never written to, and replaced on first put. Its size 53c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * is set to half the minimum, so that the first resize will create a 54c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * minimum-sized table. 55c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 56c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final Entry[] EMPTY_TABLE 57c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch = new HashtableEntry[MINIMUM_CAPACITY >>> 1]; 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 59c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 60c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The default load factor. Note that this implementation ignores the 61c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * load factor, but cannot do away with it entirely because it's 62438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * mentioned in the API. 63c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 64c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * <p>Note that this constant has no impact on the behavior of the program, 65c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * but it is emitted as part of the serialized form. The load factor of 66c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * .75 is hardwired into the program, which uses cheap shifts in place of 67c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * expensive division. 68c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 69c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final float DEFAULT_LOAD_FACTOR = .75F; 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 71c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 72c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The hash table. 73c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 74c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient HashtableEntry<K, V>[] table; 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 76c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 77c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The number of mappings in this hash map. 78c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 79c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient int size; 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 81c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 82c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Incremented by "structural modifications" to allow (best effort) 83c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * detection of concurrent modification. 84c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 85c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient int modCount; 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 87c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 88c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The table is rehashed when its size exceeds this threshold. 89c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The value of this field is generally .75 * capacity, except when 90c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the capacity is zero, as described in the EMPTY_TABLE declaration 91c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * above. 92c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 93c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient int threshold; 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 95c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Views - lazily initialized 96c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient Set<K> keySet; 97c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient Set<Entry<K, V>> entrySet; 98c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private transient Collection<V> values; 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code Hashtable} using the default capacity and load 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * factor. 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 104c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable() { 106c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch table = (HashtableEntry<K, V>[]) EMPTY_TABLE; 107c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch threshold = -1; // Forces first put invocation to replace EMPTY_TABLE 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code Hashtable} using the specified capacity and the 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * default load factor. 113f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity. 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable(int capacity) { 118c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < 0) { 119c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new IllegalArgumentException("Capacity: " + capacity); 120c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 121c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 122c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity == 0) { 123c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") 124c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = (HashtableEntry<K, V>[]) EMPTY_TABLE; 125c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch table = tab; 126c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch threshold = -1; // Forces first put() to replace EMPTY_TABLE 127c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 128c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 129c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 130c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < MINIMUM_CAPACITY) { 131c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MINIMUM_CAPACITY; 132c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else if (capacity > MAXIMUM_CAPACITY) { 133c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MAXIMUM_CAPACITY; 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 135c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = roundUpToPowerOfTwo(capacity); 136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 137c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch makeTable(capacity); 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code Hashtable} using the specified capacity and load 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * factor. 143f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param capacity 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial capacity. 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param loadFactor 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the initial load factor. 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable(int capacity, float loadFactor) { 150c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this(capacity); 151c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 152c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (loadFactor <= 0 || Float.isNaN(loadFactor)) { 153c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new IllegalArgumentException("Load factor: " + loadFactor); 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 155c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 156c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 157c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Note that this implementation ignores loadFactor; it always uses 158438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * a load factor of 3/4. This simplifies the code and generally 159c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * improves performance. 160c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new instance of {@code Hashtable} containing the mappings 165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * from the specified map. 166f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param map 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the mappings to add. 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public Hashtable(Map<? extends K, ? extends V> map) { 171c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this(capacityForInitSize(map.size())); 172c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch constructorPutAll(map); 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 175c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 176c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Inserts all of the elements of map into this Hashtable in a manner 177438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * suitable for use by constructors and pseudo-constructors (i.e., clone, 178c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * readObject). 179c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 180c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private void constructorPutAll(Map<? extends K, ? extends V> map) { 181c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<? extends K, ? extends V> e : map.entrySet()) { 182c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch constructorPut(e.getKey(), e.getValue()); 183c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 187c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns an appropriate capacity for the specified initial size. Does 188c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * not round the result up to a power of two; the caller must do this! 189c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive). 190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 191c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static int capacityForInitSize(int size) { 192c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth 193c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 194c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY 195c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY; 196adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 197adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 198adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a new {@code Hashtable} with the same key/value pairs, capacity 200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * and load factor. 201f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return a shallow copy of this {@code Hashtable}. 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see java.lang.Cloneable 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @SuppressWarnings("unchecked") 206c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized Object clone() { 207c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 208c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This could be made more efficient. It unnecessarily hashes all of 209c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the elements in the map. 210c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 211c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable<K, V> result; 212adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project try { 213c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result = (Hashtable<K, V>) super.clone(); 214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } catch (CloneNotSupportedException e) { 215c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new AssertionError(e); 216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 218c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Restore clone to empty state, retaining our capacity and threshold 219c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.makeTable(table.length); 220c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.size = 0; 221c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.keySet = null; 222c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.entrySet = null; 223c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.values = null; 224c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 225c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.constructorPutAll(this); 226c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return result; 227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 230c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns true if this {@code Hashtable} has no key/value pairs. 231f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 232c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return {@code true} if this {@code Hashtable} has no key/value pairs, 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 234c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 235adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 236c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized boolean isEmpty() { 237c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return size == 0; 238c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 239adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 240c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 241c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns the number of key/value pairs in this {@code Hashtable}. 242c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 243c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the number of key/value pairs in this {@code Hashtable}. 244c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #elements 245c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #keys 246c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 247c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized int size() { 248c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return size; 249c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 250c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 251c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 252c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns the value associated with the specified key in this 253c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable}. 254c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 255c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param key 256c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the key of the value returned. 257c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the value associated with the specified key, or {@code null} if 258c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the specified key does not exist. 259c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #put 260c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 261c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized V get(Object key) { 262c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Doug Lea's supplemental secondaryHash function (inlined) 263c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = key.hashCode(); 264c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 20) ^ (hash >>> 12); 265c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 7) ^ (hash >>> 4); 266c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 267c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 268c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 269c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; e = e.next) { 270c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K eKey = e.key; 271c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (eKey == key || (e.hash == hash && key.equals(eKey))) { 272c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return e.value; 273adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 274adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 275c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return null; 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 279adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns true if this {@code Hashtable} contains the specified object as a 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * key of one of the key/value pairs. 281f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param key 283adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to look for as a key in this {@code Hashtable}. 284adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if object is a key in this {@code Hashtable}, 285adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code false} otherwise. 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #contains 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see java.lang.Object#equals 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public synchronized boolean containsKey(Object key) { 290c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Doug Lea's supplemental secondaryHash function (inlined) 291c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = key.hashCode(); 292c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 20) ^ (hash >>> 12); 293c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch hash ^= (hash >>> 7) ^ (hash >>> 4); 294c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 295c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 296c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)]; 297c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; e = e.next) { 298c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K eKey = e.key; 299c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (eKey == key || (e.hash == hash && key.equals(eKey))) { 300c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return true; 301c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 302c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 303c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 304adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 305adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Searches this {@code Hashtable} for the specified value. 308f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 309adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param value 310adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the object to search for. 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true} if {@code value} is a value of this 312adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code Hashtable}, {@code false} otherwise. 313adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 314c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized boolean containsValue(Object value) { 315c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value == null) { 316c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new NullPointerException(); 317adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 318c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 319c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry[] tab = table; 320c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int len = tab.length; 321c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 322c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int i = 0; i < len; i++) { 323c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry e = tab[i]; e != null; e = e.next) { 324c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value.equals(e.value)) { 325c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return true; 326c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 327f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 328c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 329c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 330adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 331adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 332adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 333c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns true if this {@code Hashtable} contains the specified object as 334c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the value of at least one of the key/value pairs. 335f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 336c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param value 337c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the object to look for as a value in this {@code Hashtable}. 338c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return {@code true} if object is a value in this {@code Hashtable}, 339c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code false} otherwise. 340c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #containsKey 341c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see java.lang.Object#equals 342adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 343c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object value) { 344c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsValue(value); 345adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 346adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 347adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 348c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Associate the specified value with the specified key in this 349c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable}. If the key already exists, the old value is replaced. 350c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The key and value cannot be null. 351f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 352c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param key 353c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the key to add. 354c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param value 355c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the value to add. 356c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the old value associated with the specified key, or {@code null} 357c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * if the key did not exist. 358c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #elements 359c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #get 360c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #keys 361c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see java.lang.Object#equals 362adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 363c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized V put(K key, V value) { 364c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value == null) { 365c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new NullPointerException(); 366adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 367c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 368c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 369c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 370c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> first = tab[index]; 371c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 372c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && key.equals(e.key)) { 373c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V oldValue = e.value; 374c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e.value = value; 375c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return oldValue; 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 377c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 378adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 379c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // No entry for key is present; create one 380c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 381c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size++ > threshold) { 382c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch rehash(); // Does nothing!! 383c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab = doubleCapacity(); 384c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch index = hash & (tab.length - 1); 385c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch first = tab[index]; 386adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 387c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 388c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return null; 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 390adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 391adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 392c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This method is just like put, except that it doesn't do things that 393c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * are inappropriate or unnecessary for constructors and pseudo-constructors 394c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * (i.e., clone, readObject). In particular, this method does not check to 395c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * ensure that capacity is sufficient, and does not increment modCount. 396adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 397c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private void constructorPut(K key, V value) { 398c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value == null) { 399c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new NullPointerException(); 400adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 401c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 402c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 403c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 404c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> first = tab[index]; 405c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = first; e != null; e = e.next) { 406c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && key.equals(e.key)) { 407c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e.value = value; 408c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 409adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 410adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 412c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // No entry for key is present; create one 413c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = new HashtableEntry<K, V>(key, value, hash, first); 414c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size++; 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 416adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 417adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 418c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Copies every mapping to this {@code Hashtable} from the specified map. 419f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 420c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param map 421c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the map to copy mappings from. 422adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 423c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized void putAll(Map<? extends K, ? extends V> map) { 424c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch ensureCapacity(map.size()); 425c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<? extends K, ? extends V> e : map.entrySet()) { 426c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch put(e.getKey(), e.getValue()); 427c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 429adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 431c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Ensures that the hash table has sufficient capacity to store the 432c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * specified number of mappings, with room to grow. If not, it increases the 433c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * capacity as appropriate. Like doubleCapacity, this method moves existing 434c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * entries to new buckets as appropriate. Unlike doubleCapacity, this method 435c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * can grow the table by factors of 2^n for n > 1. Hopefully, a single call 436c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * to this method will be faster than multiple calls to doubleCapacity. 437f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 438c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * <p>This method is called only by putAll. 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 440c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private void ensureCapacity(int numMappings) { 441c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings)); 442c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] oldTable = table; 443c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int oldCapacity = oldTable.length; 444c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (newCapacity <= oldCapacity) { 445c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 446c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 447c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 448c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch rehash(); // Does nothing!! 449c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 450b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes if (newCapacity == oldCapacity * 2) { 451c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch doubleCapacity(); 452c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return; 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 454c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 455c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // We're growing by at least 4x, rehash in the obvious way 456c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 457c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size != 0) { 458c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int newMask = newCapacity - 1; 459c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int i = 0; i < oldCapacity; i++) { 460c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = oldTable[i]; e != null;) { 461c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> oldNext = e.next; 462c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int newIndex = e.hash & newMask; 463c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> newNext = newTable[newIndex]; 464c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch newTable[newIndex] = e; 465c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e.next = newNext; 466c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e = oldNext; 467c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 468f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 469c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 470adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 471adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 472adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 473c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Increases the capacity of this {@code Hashtable}. This method is called 474c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * when the size of this {@code Hashtable} exceeds the load factor. 475adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 476c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch protected void rehash() { 477c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 478c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This method has no testable semantics, other than that it gets 479c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * called from time to time. 480c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 481c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 483c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 484c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Allocate a table of the given capacity and set the threshold accordingly. 485c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param newCapacity must be a power of two 486c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 487c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private HashtableEntry<K, V>[] makeTable(int newCapacity) { 488c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") HashtableEntry<K, V>[] newTable 489c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch = (HashtableEntry<K, V>[]) new HashtableEntry[newCapacity]; 490c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch table = newTable; 491c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity 492c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return newTable; 493c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 495c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 496c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Doubles the capacity of the hash table. Existing entries are placed in 497c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the correct bucket on the enlarged table. If the current capacity is, 498c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which 499c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * will be new unless we were already at MAXIMUM_CAPACITY. 500c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 501c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private HashtableEntry<K, V>[] doubleCapacity() { 502c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] oldTable = table; 503c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int oldCapacity = oldTable.length; 504c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (oldCapacity == MAXIMUM_CAPACITY) { 505c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return oldTable; 506c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 507b5bde2fd72189192b52e726a2d606d70c3c8a34bElliott Hughes int newCapacity = oldCapacity * 2; 508c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] newTable = makeTable(newCapacity); 509c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size == 0) { 510c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return newTable; 511c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 512adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 513c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int j = 0; j < oldCapacity; j++) { 514c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /* 515c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Rehash the bucket using the minimum number of field writes. 516c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * This is the most subtle and delicate code in the class. 517c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 518c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> e = oldTable[j]; 519c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e == null) { 520c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch continue; 521c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 522c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int highBit = e.hash & oldCapacity; 523c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> broken = null; 524c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch newTable[j | highBit] = e; 525c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K,V> n = e.next; n != null; e = n, n = n.next) { 526c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int nextHighBit = n.hash & oldCapacity; 527c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (nextHighBit != highBit) { 528c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (broken == null) 529c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch newTable[j | nextHighBit] = n; 530c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch else 531c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch broken.next = n; 532c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch broken = e; 533c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch highBit = nextHighBit; 534adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 536c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (broken != null) 537c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch broken.next = null; 538c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 539c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return newTable; 540c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 541adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 542c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 543c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Removes the key/value pair with the specified key from this 544c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable}. 545c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 546c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param key 547c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the key to remove. 548c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return the value associated with the specified key, or {@code null} if 549c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the specified key did not exist. 550c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #get 551c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #put 552c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 553c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized V remove(Object key) { 554c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 555c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 556c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 557c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[index], prev = null; 558c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; prev = e, e = e.next) { 559c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && key.equals(e.key)) { 560c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (prev == null) { 561c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = e.next; 562c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else { 563c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch prev.next = e.next; 564f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 565c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 566c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size--; 567c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return e.value; 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 569c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 570c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return null; 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 572adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 573c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 574c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Removes all key/value pairs from this {@code Hashtable}, leaving the 575c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * size zero and the capacity unchanged. 576c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 577c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #isEmpty 578c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 579c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 580c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized void clear() { 581c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size != 0) { 582c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Arrays.fill(table, null); 583c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 584c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size = 0; 585c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 586c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 587f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 588c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 589c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns a set of the keys contained in this {@code Hashtable}. The set 590c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * is backed by this {@code Hashtable} so changes to one are reflected by 591c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the other. The set does not support adding. 592c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 593c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return a set of the keys. 594c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 595c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Set<K> keySet() { 596c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Set<K> ks = keySet; 597c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (ks != null) ? ks : (keySet = new KeySet()); 598c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 599f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 600c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 601c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns a collection of the values contained in this {@code Hashtable}. 602c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The collection is backed by this {@code Hashtable} so changes to one are 603c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * reflected by the other. The collection does not support adding. 604c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 605c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return a collection of the values. 606c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 607c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Collection<V> values() { 608c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Collection<V> vs = values; 609c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (vs != null) ? vs : (values = new Values()); 610c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 611f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 612c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 613c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns a set of the mappings contained in this {@code Hashtable}. Each 614c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * element in the set is a {@link Map.Entry}. The set is backed by this 615c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable} so changes to one are reflected by the other. The set 616c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * does not support adding. 617c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 618c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return a set of the mappings. 619c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 620c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Set<Entry<K, V>> entrySet() { 621c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Set<Entry<K, V>> es = entrySet; 622c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (es != null) ? es : (entrySet = new EntrySet()); 623c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 624f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 625c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 626c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 627c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns an enumeration on the keys of this {@code Hashtable} instance. 628c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * The results of the enumeration may be affected if the contents of this 629c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable} are modified. 630c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 631c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return an enumeration of the keys of this {@code Hashtable}. 632c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #elements 633c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 634c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see Enumeration 635c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 636c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Enumeration<K> keys() { 637c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new KeyEnumeration(); 638c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 639c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 640c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 641c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns an enumeration on the values of this {@code Hashtable}. The 642c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * results of the Enumeration may be affected if the contents of this 643c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code Hashtable} are modified. 644c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * 645c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return an enumeration of the values of this {@code Hashtable}. 646c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #keys 647c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #size 648c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see Enumeration 649c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 650c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public synchronized Enumeration<V> elements() { 651c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new ValueEnumeration(); 652c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 653c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 654c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 655c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Note: technically the methods of this class should synchronize the 656c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * backing map. However, this would require them to have a reference 657438d9883775e6ee31c097e2103a25571d2426cd9Elliott Hughes * to it, which would cause considerable bloat. Moreover, the RI 658c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * behaves the same way. 659c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 660c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static class HashtableEntry<K, V> implements Entry<K, V> { 661c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch final K key; 662c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V value; 663c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch final int hash; 664c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next; 665c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 666c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) { 667c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.key = key; 668c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.value = value; 669c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.hash = hash; 670c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.next = next; 671f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 672f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 673c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public final K getKey() { 674c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key; 675f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 676f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 677c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public final V getValue() { 678c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return value; 679c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 680c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 681c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public final V setValue(V value) { 682c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (value == null) { 683c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new NullPointerException(); 684c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 685c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V oldValue = this.value; 686c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch this.value = value; 687c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return oldValue; 688c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 689c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 690c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public final boolean equals(Object o) { 691c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!(o instanceof Entry)) { 692f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson return false; 693f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 694c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<?, ?> e = (Entry<?, ?>) o; 695c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key.equals(e.getKey()) && value.equals(e.getValue()); 696f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 697f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 698c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public final int hashCode() { 699c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key.hashCode() ^ value.hashCode(); 700c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 701c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 702c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public final String toString() { 703c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return key + "=" + value; 704c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 705c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 706c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 707c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private abstract class HashIterator { 708c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int nextIndex; 709c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> nextEntry; 710c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> lastEntryReturned; 711c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int expectedModCount = modCount; 712c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 713c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashIterator() { 714c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 715c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next = null; 716c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (next == null && nextIndex < tab.length) { 717c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch next = tab[nextIndex++]; 718f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 719c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch nextEntry = next; 720f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 721f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 722c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean hasNext() { 723c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return nextEntry != null; 724c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 725c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 726c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> nextEntry() { 727c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (modCount != expectedModCount) 728c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new ConcurrentModificationException(); 729c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (nextEntry == null) 730c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new NoSuchElementException(); 731c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 732c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> entryToReturn = nextEntry; 733c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 734c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next = entryToReturn.next; 735c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (next == null && nextIndex < tab.length) { 736c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch next = tab[nextIndex++]; 737f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 738c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch nextEntry = next; 739c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return lastEntryReturned = entryToReturn; 740f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 741f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 742c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> nextEntryNotFailFast() { 743c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (nextEntry == null) 744f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson throw new NoSuchElementException(); 745c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 746c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> entryToReturn = nextEntry; 747c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 748c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V> next = entryToReturn.next; 749c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (next == null && nextIndex < tab.length) { 750c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch next = tab[nextIndex++]; 751f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 752c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch nextEntry = next; 753c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return lastEntryReturned = entryToReturn; 754f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 755f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 756f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson public void remove() { 757c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (lastEntryReturned == null) 758c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new IllegalStateException(); 759c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (modCount != expectedModCount) 760c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new ConcurrentModificationException(); 761c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.remove(lastEntryReturned.key); 762c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch lastEntryReturned = null; 763c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch expectedModCount = modCount; 764f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 765f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson } 766f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson 767c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class KeyIterator extends HashIterator 768c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Iterator<K> { 769c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public K next() { return nextEntry().key; } 770c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 771c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 772c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class ValueIterator extends HashIterator 773c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Iterator<V> { 774c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public V next() { return nextEntry().value; } 775c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 776c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 777c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class EntryIterator extends HashIterator 778c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Iterator<Entry<K, V>> { 779c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Entry<K, V> next() { return nextEntry(); } 780c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 781c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 782c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class KeyEnumeration extends HashIterator 783c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Enumeration<K> { 784c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean hasMoreElements() { return hasNext(); } 785c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public K nextElement() { return nextEntryNotFailFast().key; } 786c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 787c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 788c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class ValueEnumeration extends HashIterator 789c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch implements Enumeration<V> { 790c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean hasMoreElements() { return hasNext(); } 791c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public V nextElement() { return nextEntryNotFailFast().value; } 792adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 793adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 794adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 795c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns true if this map contains the specified mapping. 796adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 797c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private synchronized boolean containsMapping(Object key, Object value) { 798c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 799c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 800c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 801c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[index]; e != null; e = e.next) { 802c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && e.key.equals(key)) { 803c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return e.value.equals(value); 804c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 805adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 806c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; // No entry for key 807adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 808adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 809adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 810c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Removes the mapping from key to value and returns true if this mapping 811c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * exists; otherwise, returns does nothing and returns false. 812adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 813c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private synchronized boolean removeMapping(Object key, Object value) { 814c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int hash = secondaryHash(key.hashCode()); 815c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch HashtableEntry<K, V>[] tab = table; 816c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int index = hash & (tab.length - 1); 817c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (HashtableEntry<K, V> e = tab[index], prev = null; 818c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch e != null; prev = e, e = e.next) { 819c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (e.hash == hash && e.key.equals(key)) { 820c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!e.value.equals(value)) { 821c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; // Map has wrong value for key 822adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 823c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (prev == null) { 824c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch tab[index] = e.next; 825c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else { 826c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch prev.next = e.next; 827adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 828c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch modCount++; 829c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch size--; 830c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return true; 831adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 832adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 833c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; // No entry for key 834adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 835adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 836adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 837c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Compares this {@code Hashtable} with the specified object and indicates 838c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * if they are equal. In order to be equal, {@code object} must be an 839c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * instance of Map and contain the same key/value pairs. 840f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 841c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @param object 842c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * the object to compare with this object. 843c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @return {@code true} if the specified object is equal to this Map, 844c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * {@code false} otherwise. 845c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * @see #hashCode 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 847c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized boolean equals(Object object) { 848c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return (object instanceof Map) && 849c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch entrySet().equals(((Map<?, ?>)object).entrySet()); 850c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 851c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 852c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized int hashCode() { 853c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int result = 0; 854c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<K, V> e : entrySet()) { 855c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K key = e.getKey(); 856c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V value = e.getValue(); 857c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (key == this || value == this) { 858c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch continue; 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 860c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result += (key != null ? key.hashCode() : 0) 861c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch ^ (value != null ? value.hashCode() : 0); 862adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 863c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return result; 864adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 865adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 866adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 867c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * A rough estimate of the number of characters per entry, for use 868c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * when creating a string buffer in the toString method. 869adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 870c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final int CHARS_PER_ENTRY = 15; 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 872adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the string representation of this {@code Hashtable}. 874f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 875adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the string representation of this {@code Hashtable}. 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 877c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @Override public synchronized String toString() { 878c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch StringBuilder result = new StringBuilder(CHARS_PER_ENTRY * size); 879c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append('{'); 880c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Iterator<Entry<K, V>> i = entrySet().iterator(); 881c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch boolean hasMore = i.hasNext(); 882c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch while (hasMore) { 883c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<K, V> entry = i.next(); 884c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 885c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch K key = entry.getKey(); 886c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append(key == this ? "(this Map)" : key.toString()); 887c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 888c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append('='); 889c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 890c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch V value = entry.getValue(); 891c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append(value == this ? "(this Map)" : value.toString()); 892c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 893c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (hasMore = i.hasNext()) { 894c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append(", "); 895c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 896adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 897adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 898c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch result.append('}'); 899c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return result.toString(); 900c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 901c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 902c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class KeySet extends AbstractSet<K> { 903c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Iterator<K> iterator() { 904c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new KeyIterator(); 905c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 906c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int size() { 907c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.size(); 908c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 909c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object o) { 910c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsKey(o); 911c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 912c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean remove(Object o) { 913c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 914c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int oldSize = size; 915c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.remove(o); 916c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return size != oldSize; 917adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 918adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 919c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public void clear() { 920c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.clear(); 921c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 922c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean removeAll(Collection<?> collection) { 923c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 924c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.removeAll(collection); 925c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 926c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 927c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean retainAll(Collection<?> collection) { 928c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 929c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.retainAll(collection); 930c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 931c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 932c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean containsAll(Collection<?> collection) { 933c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 934c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.containsAll(collection); 935c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 936c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 937c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean equals(Object object) { 938c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 939c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.equals(object); 940c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 941c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 942c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int hashCode() { 943c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 944c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.hashCode(); 945c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 946c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 947c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public String toString() { 948c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 949c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toString(); 950c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 951c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 952c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Object[] toArray() { 953c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 954c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(); 955c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 956c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 957c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public <T> T[] toArray(T[] a) { 958c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 959c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(a); 960c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 961c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 962c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 963c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 964c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class Values extends AbstractCollection<V> { 965c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Iterator<V> iterator() { 966c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new ValueIterator(); 967c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 968c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int size() { 969c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.size(); 970c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 971c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object o) { 972c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsValue(o); 973c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 974c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public void clear() { 975c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.clear(); 976c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 977c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean containsAll(Collection<?> collection) { 978c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 979c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.containsAll(collection); 980c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 981c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 982c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public String toString() { 983c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 984c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toString(); 985c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 986c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 987c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Object[] toArray() { 988c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 989c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(); 990c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 991c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 992c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public <T> T[] toArray(T[] a) { 993c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 994c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(a); 995c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 996c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 997c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 998c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 999c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private final class EntrySet extends AbstractSet<Entry<K, V>> { 1000c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Iterator<Entry<K, V>> iterator() { 1001c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return new EntryIterator(); 1002c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1003c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean contains(Object o) { 1004c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!(o instanceof Entry)) 1005c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 1006c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<?, ?> e = (Entry<?, ?>) o; 1007c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return containsMapping(e.getKey(), e.getValue()); 1008c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1009c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean remove(Object o) { 1010c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (!(o instanceof Entry)) 1011c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return false; 1012c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Entry<?, ?> e = (Entry<?, ?>)o; 1013c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return removeMapping(e.getKey(), e.getValue()); 1014c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1015c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int size() { 1016c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.size(); 1017c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1018c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public void clear() { 1019c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch Hashtable.this.clear(); 1020c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1021c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean removeAll(Collection<?> collection) { 1022c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1023c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.removeAll(collection); 1024c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1025c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1026c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean retainAll(Collection<?> collection) { 1027c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1028c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.retainAll(collection); 1029c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1030c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1031c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean containsAll(Collection<?> collection) { 1032c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1033c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.containsAll(collection); 1034c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1035c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1036c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public boolean equals(Object object) { 1037c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1038c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.equals(object); 1039c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1040c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1041c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public int hashCode() { 1042c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return Hashtable.this.hashCode(); 1043c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1044c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public String toString() { 1045c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1046c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toString(); 1047c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1048c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1049c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public Object[] toArray() { 1050c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1051c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(); 1052c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1053c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1054c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch public <T> T[] toArray(T[] a) { 1055c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch synchronized (Hashtable.this) { 1056c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return super.toArray(a); 1057c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1058adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1059adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1060adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1061adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1062c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Applies a supplemental hash function to a given hashCode, which defends 1063c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * against poor quality hash functions. This is critical because Hashtable 1064c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * uses power-of-two length hash tables, that otherwise encounter collisions 1065c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * for hashCodes that do not differ in lower or upper bits. 1066c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch */ 1067c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static int secondaryHash(int h) { 1068c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Doug Lea's supplemental hash function 1069c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch h ^= (h >>> 20) ^ (h >>> 12); 1070c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return h ^ (h >>> 7) ^ (h >>> 4); 1071c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1072c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1073c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch /** 1074c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * Returns the smallest power of two >= its argument, with several caveats: 1075c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * If the argument is negative but not Integer.MIN_VALUE, the method returns 1076c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method 1077c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * returns Integer.MIN_VALUE. If the argument is zero, the method returns 1078c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch * zero. 1079adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1080c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static int roundUpToPowerOfTwo(int i) { 1081c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i--; // If input is a power of two, shift its high-order bit right 1082c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1083c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // "Smear" the high-order bit all the way to the right 1084c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 1; 1085c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 2; 1086c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 4; 1087c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 8; 1088c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch i |= i >>> 16; 1089c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1090c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch return i + 1; 1091adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1092adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1093c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final long serialVersionUID = 1421746759512286392L; 1094c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1095c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch private static final ObjectStreamField[] serialPersistentFields = { 1096e26ba79900d471d02d656f686926918ef7dc751fElliott Hughes new ObjectStreamField("threshold", int.class), 1097e26ba79900d471d02d656f686926918ef7dc751fElliott Hughes new ObjectStreamField("loadFactor", float.class), 1098c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch }; 1099c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private synchronized void writeObject(ObjectOutputStream stream) 1101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throws IOException { 1102c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch // Emulate loadFactor field for other implementations to read 1103c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch ObjectOutputStream.PutField fields = stream.putFields(); 1104c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch fields.put("threshold", (int) (DEFAULT_LOAD_FACTOR * table.length)); 1105c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch fields.put("loadFactor", DEFAULT_LOAD_FACTOR); 1106c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeFields(); 1107c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1108c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeInt(table.length); // Capacity 1109c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeInt(size); 1110c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (Entry<K, V> e : entrySet()) { 1111c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeObject(e.getKey()); 1112c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch stream.writeObject(e.getValue()); 1113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void readObject(ObjectInputStream stream) throws IOException, 1117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ClassNotFoundException { 1118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stream.defaultReadObject(); 1119c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int capacity = stream.readInt(); 1120c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < 0) { 1121c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new InvalidObjectException("Capacity: " + capacity); 1122c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1123c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (capacity < MINIMUM_CAPACITY) { 1124c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MINIMUM_CAPACITY; 1125c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else if (capacity > MAXIMUM_CAPACITY) { 1126c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = MAXIMUM_CAPACITY; 1127c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } else { 1128c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch capacity = roundUpToPowerOfTwo(capacity); 1129c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1130c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch makeTable(capacity); 1131c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1132c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch int size = stream.readInt(); 1133c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch if (size < 0) { 1134c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch throw new InvalidObjectException("Size: " + size); 1135c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch } 1136c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch 1137c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch for (int i = 0; i < size; i++) { 1138c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") K key = (K) stream.readObject(); 1139c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch @SuppressWarnings("unchecked") V val = (V) stream.readObject(); 1140c0a4d9b35cbdd33dcc8e6a78a829573f0ed9bf6dJoshua Bloch constructorPut(key, val); 1141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1144