基础很重要哦...
1. HashMap工作原理：
HashMap是基于Hash表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null作为键和值。无序。
2. HashMap数据结构：
HashMap实际上是一个“链表散列”的数据结构，即是数组和链表的结合体。HashMap底层就是个数组结构，数组的每一项是一个链表。当新建一个HashMap时，就会新创建一个数组。
Java代码：
| /** * 长度扩容必须是2的倍数 */ transient Entry[] table; static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; … … public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } |
可以看到，每个Entry就是一个键值对，本身对象持有下一个对象的引用，这样就构成了链表。
为了元素在HashMap中均匀分布，通常想到的是把hashCode对数组长度取模运算，但是取模运算的消耗比较大，那么HashMap做法是根据key算的的hashCode跟数组-1进行“与”运算(&)。
将初始大小设置为16的原因(当扩容是必须是2的整数次幂)：主要为了使HashMap的访问的性能最高，减少key在bucket中存取时的碰撞几率。
3. HashMap的resize：
当HashMap的元素越来越多时，碰撞的几率就越来越高，因为数组的长度初始时是固定的，所以为了提高查询的效率，就要对HashMap的数组进行扩容，在HashMap数组扩容后最消耗性能点是：原数组中的元素必须重新计算在新数组中的位置，然后存放进去。
什么时候扩容？
当HashMap中的元素个数超过数组大小*负载因子的时，会进行数组扩容，默认的loadFactor是0.75（意思是当一个Map填满了75%bucket的时），也就是当为12（16*0.75），就会把数组扩容原来大小的两倍：16*2=32。然后重新计算每个元素在数组中的位置（此时比较消耗性能了）。 这个过程也叫做rehashing（因为它调用了hash方法找到新bucket的位置）。
建议当我们已预知了数组的元素个数，可根据具体需求自行设置数组初始容量以便提高查询性能。但是要记得考虑“&”的问题。这样也解决了resize的问题。
4. HashMap的存取实现：
put方法分析：
如果传入key为null值，则将其放倒数组的第一个位置。如果key不为空，首先对key调用hashCode方法，对返回的hashCode值做hash，通过计算hash值可以找到bucket(这个bucket就是指Entry数组)位置(下标)来存储Entry对象。
| 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; } |
虽然发生碰撞的几率较小，但是如果发生碰撞，则会将新添加的元素放倒链表头部，早先加入的元素放倒链表尾部（我们可以将发生碰撞的这个链表理解为LinkedList，这个LinkedList中存储了键值对形式的Map.Entry对象）。
| 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); } |
get方法：
调用get方法时，首先会根据传入的key调用hashCode方法，计算hash值找到bucket位置，然后遍历链表（即上面所说的linkedList<Entry<K,V>>），判断hash和key的equals方法查找到对应的Entry对象。
| 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; } |
最佳实践方式：
使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。
参考:http://www.importnew.com/7099.html
posted on 2013-11-18 18:01
David1228 阅读(2890)
评论(4) 编辑 收藏 所属分类:
JAVA