1 /* 2 * Copyright (C) 2008 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import com.google.common.annotations.GwtCompatible; 20 import static com.google.common.base.Preconditions.checkArgument; 21 22 /** 23 * Static methods for implementing hash-based collections. 24 * 25 * @author Kevin Bourrillion 26 * @author Jesse Wilson 27 */ 28 @GwtCompatible 29 final class Hashing { 30 private Hashing() {} 31 32 /* 33 * This method was written by Doug Lea with assistance from members of JCP 34 * JSR-166 Expert Group and released to the public domain, as explained at 35 * http://creativecommons.org/licenses/publicdomain 36 */ 37 static int smear(int hashCode) { 38 hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12); 39 return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4); 40 } 41 42 // We use power-of-2 tables, and this is the highest int that's a power of 2 43 private static final int MAX_TABLE_SIZE = 1 << 30; 44 45 // If the set has this many elements, it will "max out" the table size 46 private static final int CUTOFF = 1 << 29; 47 48 // Size the table to be at most 50% full, if possible 49 static int chooseTableSize(int setSize) { 50 if (setSize < CUTOFF) { 51 return Integer.highestOneBit(setSize) << 2; 52 } 53 54 // The table can't be completely full or we'll get infinite reprobes 55 checkArgument(setSize < MAX_TABLE_SIZE, "collection too large"); 56 return MAX_TABLE_SIZE; 57 } 58 } 59
