发表时间:2010-09-03 最后修改:2010-11-29
java.util.HashMap是很常见的类,前段时间公司系统由于对HashMap使用不当,导致cpu百分之百,在并发环境下使用HashMap 而没有做同步,可能会引起死循环,关于这一点,sun的官方网站上已有阐述,这并非是bug。
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); table = new Entry[capacity]; init(); }
while (capacity < initialCapacity) capacity <<= 1;
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); }
public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAllForCreate(m); }
static int hash(int h) { return useNewHash ? newHash(h) : oldHash(h); }
private static final boolean useNewHash; static { useNewHash = false; } 这说明useNewHash其实一直为false且不可改变的,hash函数里对 useNewHash的判断真是多余的。
private static int oldHash(int h) { h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } private static int newHash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
int hash = hash(k.hashCode()); int i = indexFor(hash, table.length); 第一行,上面讲过了,是得到哈希值,第二行,则是根据哈希指计算元素在数组中的位置了,位置的计算是将哈希值和数组长度按位与运算。
static int indexFor(int h, int length) { return h & (length-1); } “h & (length-1)”其实这里是很有讲究的,为什么是和(length-1)进行按位与运算呢?这样做是为了提高HashMap的效率。什么?这样能提高效率?且听我细细道来。 首先我们要确定一下,HashMap的数组长度永远都是偶数,即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部,上面也讲过,有这样的一段代码:
while (capacity < initialCapacity) capacity <<= 1; 所以length-1一定是个奇数,假设现在长度为16,减去1后就是15,对应的二进制是:1111。 假设有两个元素,一个哈希值是8,二进制是1000,一个哈希值是9,二进制是1001。和1111与运算后,分别还是1000和1001,它们被分配在了数组的不同位置,这样,哈希的分布非常均匀。 那么,如果数组长度是奇数,减去1后就是偶数了,偶数对应的二进制最低位一定是0了,例如14二进制1110。对上面两个数子分别与运算,得到1000和1000。看到了吗?都是一样的值,哈希值8和9的元素多被存储在数组同一个位置的链表中。在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较。所以,一定要哈希均匀分布,尽量减少哈希冲突,减少了哈希冲突,就减少了链表循环,就提高了效率。
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }
private V putForNullKey(V value) { int hash = hash(NULL_KEY.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { if (e.key == NULL_KEY) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, (K) NULL_KEY, value, i); return null; } NULL_KEY的声明:static final Object NULL_KEY = new Object();
for (Entry<K,V> e = table[i]; e != null; e = e.next) { if (e.key == NULL_KEY) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } 如果遍历完了该位置的链表都没有找到有key相等的,那么将当前对象增加到链表里面去
modCount++; addEntry(hash, (K) NULL_KEY, value, i); return null; 且看看addEntry方法
void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } table[bucketIndex] = new Entry<K,V>(hash, key, value, e);新建一个Entry对象,并放在当前位置的Entry链表的头部,看看下面的 Entry构造函数就知道了,注意红色部分。
Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }
if (size++ >= threshold) resize(2 * table.length); 这是扩容判断,要注意,并不是数据尺寸达到HashMap的最大容量时才扩容,而是达到 threshold指定的值时就开始扩容, threshold=最大容量*加载因子。 看看resize方法
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); } 重点看看红色部分的 transfer方法
void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry<K,V> e = src[j]; if (e != null) { src[j] = null; do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } tranfer方法将所有的元素重新哈希,因为新的容量变大,所以每个元素的哈希值和位置都是不一样的。
如何寻找元素 通过上面代码的分析,应该可以很清楚的看到,HashMap的元素查找大致分为三步: 根据key的hasocde()得到哈希值 根据哈希值确定元素在数组中的位置 找到指定位置的链表,循环比较,先“==”比较,如果不等,再“equals”比较,如果有一个比较相等,就说明找到元素了。 所以说到这里,我想大家也明白了,为什么要把一个对象放进HashMap的时候,最好是重写hashcode()方法和equals 方法呢?根据前面的分析,hashcode()可以确定元素在数组中的位置,而equals方法在链表的比较时要用到。
正确的使用HashMap
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }
|
联系客服