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