从源码可以看出,初始化的数组长度为capacity,capacity的值总是2的N次方,大小比第一个参数稍大或相等。
3.
HashMap的put操作
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 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; }
3.1
put进的key为null
从源码中可以看出,HashMap是允许key为null的,会调用putForNullKey()方法:
private V putForNullKey(V value) { for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
putForNullKey方法会遍历以table[0]为链表头的链表,如果存在key为null的KV,那么替换其value值并返回旧值。否则调用addEntry方法,这个方法也很简单,将[null,value]放在table[0]的位置,并将新加入的键值对封装成一个Entity对象,将其next指向原table[0]处的Entity实例。
size表示HashMap中存放的所有键值对的数量。
threshold = capacity*loadFactor,最后几行代码表示当HashMap的size大于threshold时会执行resize操作,将HashMap扩容为原来的2倍。扩容需要重新计算每个元素在数组中的位置,indexFor()方法中的table.length参数也证明了这一点。
但是扩容是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。比如说我们有1000个元素,那么我们就该声明new HashMap(2048),因为需要考虑默认的0.75的扩容因子和数组数必须是2的N次方。若使用声明new HashMap(1024)那么put过程中会进行扩容。
3.2 put进的key不为null
将上述put方法中的相关代码复制一下方便查看:
int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry 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; }
从源码可以看出,第1、2行计算将要put进的键值对的数组的位置i。第4行判断加入的key是否和以table[i]为链表头的链表中所有的键值对有重复,若重复则替换value并返回旧值,若没有重复则调用addEntry方法,上面对这个方法的逻辑已经介绍过了。
至此HashMap的put操作已经介绍完毕了。
4.
HashMap的get操作
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry 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; } private V getForNullKey() { for (Entry e = table[0]; e != null; e = e.next) { if (e.key == null) return e.value; } return null; }
如果了解了前面的put操作,那么这里的get操作逻辑就很容易理解了,源码中的逻辑已经非常非常清晰了。
需要注意的只有当找不到对应value时,返回的是null。或者value本身就是null。这是可以通过containsKey()来具体判断。
了解了上面HashMap的put和get操作原理,可以通过下面这个小例题进行知识巩固,题目是打印在数组中出现n/2以上的元素,我们便可以使用HashMap的特性来解决。
public class HashMapTest { public static void main(String[] args) { int [] a = {2,1,3,2,0,4,2,1,2,3,1,5,6,2,2,3}; Map map = new HashMap(); for(int i=0; i set = map.keySet(); for (Integer s : set) { if(map.get(s)>=a.length/2){ System.out.println(s); } } } }
5. HashMap和HashTable的对比
HashTable和HashMap采用相同的存储机制,二者的实现基本一致,不同的是:
(1)HashMap是非线程安全的,HashTable是线程安全的,内部的方法基本都经过synchronized修饰。
(2)因为同步、哈希性能等原因,性能肯定是HashMap更佳,因此HashTable已被淘汰。
(3) HashMap允许有null值的存在,而在HashTable中put进的键值只要有一个null,直接抛出NullPointerException。
(4)HashMap默认初始化数组的大小为16,HashTable为11。前者扩容时乘2,使用位运算取得哈希,效率高于取模。而后者为乘2加1,都是素数和奇数,这样取模哈希结果更均匀。
这里本来我没有仔细看两者的具体哈希算法过程,打算粗略比较一下区别就过的,但是最近师姐面试美团移动开发时被问到了稍微具体一些的算法过程,我也是醉了…不过还是恭喜师姐面试成功,起薪20W,真是羡慕,希望自己一年后找工作也能顺顺利利的。
言归正传,看下两种集合的hash算法。看源码也不难理解。
//HashMap的散列函数,这里传入参数为键值对的keystatic final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} //返回hash值的索引,h & (length-1)操作等价于 hash % length操作, 但&操作性能更优static int indexFor(int h, int length) { // length must be a non-zero power of 2 return h & (length-1);}//HashTable的散列函数直接在put方法里实现了int hash = key.hashCode();int index = (hash & 0x7FFFFFFF) % tab.length;
6. HashTable和ConCurrentHashMap的对比
先对ConcurrentHashMap进行一些介绍吧,它是线程安全的HashMap的实现。
HashTable里使用的是synchronized关键字,这其实是对对象加锁,锁住的都是对象整体,当Hashtable的大小增加到一定的时候,性能会急剧下降,因为迭代时需要被锁定很长的时间。
ConcurrentHashMap算是对上述问题的优化,其构造函数如下,默认传入的是16,0.75,16。
public ConcurrentHashMap(int paramInt1, float paramFloat, int paramInt2) { //… int i = 0; int j = 1; while (j >> this.segmentShift & this.segmentMask)].put(paramK, i, paramV, false); }
ConcurrentHashMap引入了分割(Segment),上面代码中的最后一行其实就可以理解为把一个大的Map拆分成N个小的HashTable,在put方法中,会根据hash(paramK.hashCode())来决定具体存放进哪个Segment,如果查看Segment的put操作,我们会发现内部使用的同步机制是基于lock操作的,这样就可以对Map的一部分(Segment)进行上锁,这样影响的只是将要放入同一个Segment的元素的put操作,保证同步的时候,锁住的不是整个Map(HashTable就是这么做的),相对于HashTable提高了多线程环境下的性能,因此HashTable已经被淘汰了。
7. HashMap和ConCurrentHashMap的对比
最后对这俩兄弟做个区别总结吧:
(1)经过4.2的分析,我们知道ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的syn关键字锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。
(2)HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。
至此对HashMap、HashTable以及ConCurrentHashMap异同比较总结完毕。
请尊重原创,转载请出自出处:http://blog.csdn.net/seu_calvin/article/details/52653711