1 /* 2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved. 3 */ 4 /* 5 * Licensed to the Apache Software Foundation (ASF) under one or more 6 * contributor license agreements. See the NOTICE file distributed with 7 * this work for additional information regarding copyright ownership. 8 * The ASF licenses this file to You under the Apache License, Version 2.0 9 * (the "License"); you may not use this file except in compliance with 10 * the License. You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 21 package com.sun.org.apache.xerces.internal.util; 22 23 24 /** 25 * This class is an unsynchronized hash table primary used for String 26 * to Object mapping. 27 * <p> 28 * The hash code uses the same algorithm as SymbolTable class. 29 * 30 * @author Elena Litani 31 */ 32 public class SymbolHash { 33 34 // 35 // Constants 36 // 37 38 /** Default table size. */ 39 protected static final int TABLE_SIZE = 101; 40 41 /** Maximum hash collisions per bucket. */ 42 protected static final int MAX_HASH_COLLISIONS = 40; 43 44 protected static final int MULTIPLIERS_SIZE = 1 << 5; 45 protected static final int MULTIPLIERS_MASK = MULTIPLIERS_SIZE - 1; 46 47 // 48 // Data 49 // 50 51 /** Actual table size **/ 52 protected int fTableSize; 53 54 /** Buckets. */ 55 protected Entry[] fBuckets; 56 57 /** Number of elements. */ 58 protected int fNum = 0; 59 60 /** 61 * Array of randomly selected hash function multipliers or <code>null</code> 62 * if the default String.hashCode() function should be used. 63 */ 64 protected int[] fHashMultipliers; 65 66 // 67 // Constructors 68 // 69 70 /** Constructs a key table with the default size. */ 71 public SymbolHash() { 72 this(TABLE_SIZE); 73 } 74 75 /** 76 * Constructs a key table with a given size. 77 * 78 * @param size the size of the key table. 79 */ 80 public SymbolHash(int size) { 81 fTableSize = size; 82 fBuckets = new Entry[fTableSize]; 83 } 84 85 // 86 // Public methods 87 // 88 89 /** 90 * Adds the key/value mapping to the key table. If the key already exists, 91 * the previous value associated with this key is overwritten by the new 92 * value. 93 * 94 * @param key 95 * @param value 96 */ 97 public void put(Object key, Object value) { 98 99 // search for identical key 100 int collisionCount = 0; 101 final int hash = hash(key); 102 int bucket = hash % fTableSize; 103 for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) { 104 if (key.equals(entry.key)) { 105 // replace old value 106 entry.value = value; 107 return; 108 } 109 ++collisionCount; 110 } 111 112 if (fNum >= fTableSize) { 113 // Rehash the table if the number of entries 114 // would exceed the number of buckets. 115 rehash(); 116 bucket = hash % fTableSize; 117 } 118 else if (collisionCount >= MAX_HASH_COLLISIONS && key instanceof String) { 119 // Select a new hash function and rehash the table if 120 // MAX_HASH_COLLISIONS is exceeded. 121 rebalance(); 122 bucket = hash(key) % fTableSize; 123 } 124 125 // create new entry 126 Entry entry = new Entry(key, value, fBuckets[bucket]); 127 fBuckets[bucket] = entry; 128 ++fNum; 129 } 130 131 /** 132 * Get the value associated with the given key. 133 * 134 * @param key 135 * @return the value associated with the given key. 136 */ 137 public Object get(Object key) { 138 int bucket = hash(key) % fTableSize; 139 Entry entry = search(key, bucket); 140 if (entry != null) { 141 return entry.value; 142 } 143 return null; 144 } 145 146 /** 147 * Get the number of key/value pairs stored in this table. 148 * 149 * @return the number of key/value pairs stored in this table. 150 */ 151 public int getLength() { 152 return fNum; 153 } 154 155 /** 156 * Add all values to the given array. The array must have enough entry. 157 * 158 * @param elements the array to store the elements 159 * @param from where to start store element in the array 160 * @return number of elements copied to the array 161 */ 162 public int getValues(Object[] elements, int from) { 163 for (int i=0, j=0; i<fTableSize && j<fNum; i++) { 164 for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) { 165 elements[from+j] = entry.value; 166 j++; 167 } 168 } 169 return fNum; 170 } 171 172 /** 173 * Return key/value pairs of all entries in the map 174 */ 175 public Object[] getEntries() { 176 Object[] entries = new Object[fNum << 1]; 177 for (int i=0, j=0; i<fTableSize && j<fNum << 1; i++) { 178 for (Entry entry = fBuckets[i]; entry != null; entry = entry.next) { 179 entries[j] = entry.key; 180 entries[++j] = entry.value; 181 j++; 182 } 183 } 184 return entries; 185 } 186 187 /** 188 * Make a clone of this object. 189 */ 190 public SymbolHash makeClone() { 191 SymbolHash newTable = new SymbolHash(fTableSize); 192 newTable.fNum = fNum; 193 newTable.fHashMultipliers = fHashMultipliers != null ? (int[]) fHashMultipliers.clone() : null; 194 for (int i = 0; i < fTableSize; i++) { 195 if (fBuckets[i] != null) { 196 newTable.fBuckets[i] = fBuckets[i].makeClone(); 197 } 198 } 199 return newTable; 200 } 201 202 /** 203 * Remove all key/value association. This tries to save a bit of GC'ing 204 * by at least keeping the fBuckets array around. 205 */ 206 public void clear() { 207 for (int i=0; i<fTableSize; i++) { 208 fBuckets[i] = null; 209 } 210 fNum = 0; 211 fHashMultipliers = null; 212 } // clear(): void 213 214 protected Entry search(Object key, int bucket) { 215 // search for identical key 216 for (Entry entry = fBuckets[bucket]; entry != null; entry = entry.next) { 217 if (key.equals(entry.key)) 218 return entry; 219 } 220 return null; 221 } 222 223 /** 224 * Returns a hashcode value for the specified key. 225 * 226 * @param key The key to hash. 227 */ 228 protected int hash(Object key) { 229 if (fHashMultipliers == null || !(key instanceof String)) { 230 return key.hashCode() & 0x7FFFFFFF; 231 } 232 return hash0((String) key); 233 } // hash(Object):int 234 235 private int hash0(String symbol) { 236 int code = 0; 237 final int length = symbol.length(); 238 final int[] multipliers = fHashMultipliers; 239 for (int i = 0; i < length; ++i) { 240 code = code * multipliers[i & MULTIPLIERS_MASK] + symbol.charAt(i); 241 } 242 return code & 0x7FFFFFFF; 243 } // hash0(String):int 244 245 /** 246 * Increases the capacity of and internally reorganizes this 247 * SymbolHash, in order to accommodate and access its entries more 248 * efficiently. This method is called automatically when the 249 * number of keys in the SymbolHash exceeds its number of buckets. 250 */ 251 protected void rehash() { 252 rehashCommon((fBuckets.length << 1) + 1); 253 } 254 255 /** 256 * Randomly selects a new hash function and reorganizes this SymbolHash 257 * in order to more evenly distribute its entries across the table. This 258 * method is called automatically when the number keys in one of the 259 * SymbolHash's buckets exceeds MAX_HASH_COLLISIONS. 260 */ 261 protected void rebalance() { 262 if (fHashMultipliers == null) { 263 fHashMultipliers = new int[MULTIPLIERS_SIZE]; 264 } 265 PrimeNumberSequenceGenerator.generateSequence(fHashMultipliers); 266 rehashCommon(fBuckets.length); 267 } 268 269 private void rehashCommon(final int newCapacity) { 270 271 final int oldCapacity = fBuckets.length; 272 final Entry[] oldTable = fBuckets; 273 274 final Entry[] newTable = new Entry[newCapacity]; 275 276 fBuckets = newTable; 277 fTableSize = fBuckets.length; 278 279 for (int i = oldCapacity; i-- > 0;) { 280 for (Entry old = oldTable[i]; old != null; ) { 281 Entry e = old; 282 old = old.next; 283 284 int index = hash(e.key) % newCapacity; 285 e.next = newTable[index]; 286 newTable[index] = e; 287 } 288 } 289 } 290 291 // 292 // Classes 293 // 294 295 /** 296 * This class is a key table entry. Each entry acts as a node 297 * in a linked list. 298 */ 299 protected static final class Entry { 300 // key/value 301 public Object key; 302 public Object value; 303 /** The next entry. */ 304 public Entry next; 305 306 public Entry() { 307 key = null; 308 value = null; 309 next = null; 310 } 311 312 public Entry(Object key, Object value, Entry next) { 313 this.key = key; 314 this.value = value; 315 this.next = next; 316 } 317 318 public Entry makeClone() { 319 Entry entry = new Entry(); 320 entry.key = key; 321 entry.value = value; 322 if (next != null) 323 entry.next = next.makeClone(); 324 return entry; 325 } 326 } // entry 327 328 } // class SymbolHash