网站如何批量上传产品,火狐浏览器网页版,安徽论坛网站建设,中讯高科网站建设转载自 Java HashSet和HashMap源码剖析总体介绍
之所以把HashSet和HashMap放在一起讲解#xff0c;是因为二者在Java里有着相同的实现#xff0c;前者仅仅是对后者做了一层包装#xff0c;也就是说HashSet里面有一个HashMap#xff08;适配器模式#xff09;。因此本文将重…转载自 Java HashSet和HashMap源码剖析总体介绍
之所以把HashSet和HashMap放在一起讲解是因为二者在Java里有着相同的实现前者仅仅是对后者做了一层包装也就是说HashSet里面有一个HashMap适配器模式。因此本文将重点分析HashMap。
HashMap实现了Map接口允许放入null元素除该类未实现同步外其余跟Hashtable大致相同跟TreeMap不同该容器不保证元素顺序根据需要该容器可能会对元素重新哈希元素的顺序也会被重新打散因此不同时间迭代同一个HashMap的顺序可能会不同。根据对冲突的处理方式不同哈希表有两种实现方式一种开放地址方式Open addressing另一种是冲突链表方式Separate chaining with linked lists。Java HashMap采用的是冲突链表方式。
从上图容易看出如果选择合适的哈希函数put()和get()方法可以在常数时间内完成。但在对HashMap进行迭代时需要遍历整个table以及后面跟的冲突链表。因此对于迭代比较频繁的场景不宜将HashMap的初始大小设的过大。
有两个参数可以影响HashMap的性能初始容量inital capacity和负载系数load factor。初始容量指定了初始table的大小负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时容器将自动扩容并重新哈希。对于插入元素较多的场景将初始容量设大可以减少重新哈希的次数。
将对向放入到HashMap或HashSet中时有两个方法需要特别关心hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里当多个对象的哈希值冲突时equals()方法决定了这些对象是否是“同一个对象”。所以如果要将自定义的对象放入到HashMap或HashSet中需要Override hashCode()和equals()方法。
方法剖析
get()
get(Object key)方法根据指定的key值返回对应的value该方法调用了getEntry(Object key)得到相应的entry然后返回entry.getValue()。因此getEntry()是算法的核心。算法思想是首先通过hash()函数得到对应bucket的下标然后依次遍历冲突链表通过key.equals(k)方法来判断是否是要找的那个entry。上图中hash(k)(table.length-1)等价于hash(k)%table.length原因是HashMap要求table.length必须是2的指数因此table.length-1就是二进制低位全是1跟hash(k)相与会将哈希值的高位全抹掉剩下的就是余数了。
1234567891011121314//getEntry()方法finalEntryK,V getEntry(Object key) { ...... inthash (key null) ? 0: hash(key); for(EntryK,V e table[hash(table.length-1)];//得到冲突链表 e ! null; e e.next) {//依次遍历冲突链表中的每个entry Object k; //依据equals()方法判断是否相等 if(e.hash hash ((k e.key) key || (key ! null key.equals(k)))) returne; } returnnull;}put()
put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找看是否包含该元组如果已经包含则直接返回查找过程类似于getEntry()方法如果没有找到则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry插入方式为头插法。
123456789101112//addEntry()voidaddEntry(inthash, K key, V value, intbucketIndex) { if((size threshold) (null! table[bucketIndex])) { resize(2* table.length);//自动扩容并重新哈希 hash (null! key) ? hash(key) : 0; bucketIndex hash (table.length-1);//hash%table.length } //在冲突链表头部插入新的entry EntryK,V e table[bucketIndex]; table[bucketIndex] newEntry(hash, key, value, e); size;}remove()
remove(Object key)的作用是删除key值对应的entry该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry然后删除该entry修改链表的相应指针。查找过程跟getEntry()过程类似。
123456789101112131415161718192021//removeEntryForKey()finalEntryK,V removeEntryForKey(Object key) { ...... inthash (key null) ? 0: hash(key); inti indexFor(hash, table.length);//hash(table.length-1) EntryK,V prev table[i];//得到冲突链表 EntryK,V e prev; while(e ! null) {//遍历冲突链表 EntryK,V next e.next; Object k; if(e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {//找到要删除的entry modCount; size--; if(prev e) table[i] next;//删除的是冲突链表的第一个entry elseprev.next next; returne; } prev e; e next; } returne;}HashSet
前面已经说过HashSet是对HashMap的简单包装对HashSet的函数调用都会转换成合适的HashMap方法因此HashSet的实现非常简单只有不到300行代码。这里不再赘述。
12345678910111213141516//HashSet是对HashMap的简单包装publicclassHashSetE{ ...... privatetransientHashMapE,Object map;//HashSet里面有一个HashMap // Dummy value to associate with an Object in the backing Map privatestaticfinal Object PRESENT newObject(); publicHashSet() { map newHashMap(); } ...... publicbooleanadd(E e) {//简单的方法转换 returnmap.put(e, PRESENT)null; } ......}本文github地址
