linkedset使用技巧?
从源码的角度来对linkedHashSet寻根问底!
先一览linkedHashSet类中的所有方法,发现就是一些构造方法,没什么特别的。。spliterator方法也只是个迭代器!
从构造器中的super方法点过去可得见端倪,原来构造器中的父级构造器使用的是linkedHashMap进行实例化,那么linkedHashSet的特性势必跟linkedHashMap息息相关,换句话说linkedHashSet的输出有序来自于linkedHashMap;
下面对linkedHashMap进行详细分析:
linkedHashMap继承HashMap,实现了Map,很明显linkedHashMap也算是HashMap,还保存了数组链表的结构,至于有序的原因肯定不会是因为Map接口和继承HashMap,也就是说linkedHashMap的有序,肯定就是在linkedHashMap类中实现的;
HashMap的底层数据结构是使用数组中的位置作为桶,每个桶中放置一份链表(或者红黑树),而hashCod
Sardine调用put方法的底层实现怎么做?
hashmapput方法的实现:
12345678910111213141516171819首先对key做null检查。如果key是null,会被存储到table[0],因为null的hash值总是0。
key的hashcode()方被调用,然后计算hash值。hash值用来找到存储Entry对象的数组的索引。有时候hash函数可能写的很不好,所以JDK的设计者添加了另一个叫做hash()的方法,它接收刚才计算的hash值作为参数。如果你想了解更多关于hash()函数的东西,可以参考:hashmap中的hash和indexFor方法
indexFor(hash,table.length)用来计算在table数组中存储Entry对象的精确的索引。
在我们的例子中已经看到,如果两个key有相同的hash值(也叫),他们会以链表的形式来存储。所以,这里我们就迭代链表。
·如果在刚才计算出来的索引位置没有元素,直接把Entry对象放在那个索引上。
·如果索引上有元素,然后会进行迭代,一直到Entry-gtnext是null。当前的Entry对象变成链表的下一个节点。
·如果我们再次放入同样的key会怎样呢?逻辑上,它应该替换老的value。事实上,它确实是这么做的。在迭代的过程中,会调用equals()方法来检查key的相等性(key.equals(k)),如果这个方法返回true,它就会用当前Entry的value来替换之前的value。
2.hashMapget方法的解析:
1234567当你传递一个key从hashmap总获取value的时候:
对key进行null检查。如果key是null,table[0]这个位置的元素将被返回。
key的hashcode()方法被调用,然后计算hash值。
indexFor(hash,table.length)用来计算要获取的Entry对象在table数组中的精确的位置,使用刚才计算的hash值。
在获取了table数组的索引之后,会迭代链表,调用equals()方法检查key的相等性,如果equals()方法返回true,get方法返回Entry对象的value,否则,返回null。
3.要牢记以下关键点:
·HashMap有一个叫做Entry的内部类,它用来存储key-value对。·上面的Entry对象是存储在一个叫做table的Entry数组中。·table的索引在逻辑上叫做“桶”(bucket),它存储了链表的第一个元素。·key的hashcode()方法用来找到Entry对象所在的桶。·如果两个key有相同的hash值,他们会被放在table数组的同一个桶里面。·key的equals()方法用来确保key的唯一性。·value对象的equals()和hashcode()方法根本一点用也没有。简单地说,HashMap在底层将key-value当成一个整体进行处理,这个整体就是一个Entry对象。HashMap底层采用一个Entry[]数组来保存所有的key-value对,当需要存储一个Entry对象时,会根据hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。
HashMap的resize(rehash)
当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.7512的时候,就把数组的大小扩展为2*1632,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素newHashMap(1000),但是理论上来讲newHashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。但是newHashMap(1024)还不是更合适的,因为0.75*1000lt1000,也就是说为了让0.75*sizegt1000,我们必须这样newHashMap(2048)才最合适,既考虑了amp的问题,也避免了resize的问题。