温州本地网站平台wordpress文章多个分类

温州本地网站平台,wordpress文章多个分类,wordpress目录怎么制作,商务网站开发基本流程常用的数据结构 数组#xff1a;采用一段连续的存储单元来存储数据。对于指定下标的查找#xff0c;时间复杂度为O(1)#xff0c;但在数组中间以及头部插入数据时#xff0c;需要复制移动后面的元素。 链表#xff1a;一种在物理存储单元上非连续、非顺序的存储结构Node类作为HashMap中的一个内部类除了key、value两个属性外还定义了一个next指针。当有哈希冲突时HashMap会用之前数组当中相同哈希值对应存储的Node对象通过指针指向新增的相同哈希值的Node对象的引用。static class Node K, V implements Map.Entry K, V { final int hash; final K key; V value; Node K, V next; Node(int hash, K key, V value, Node K, V next) { this.hash hash; this.key key; this.value value; this.next next; } }HashMap还有两个重要的属性加载因子loadFactor和边界值threshold。在初始化HashMap时就会涉及到这两个关键初始化参数。int threshold; final float loadFactor;LoadFactor属性是用来间接设置Entry数组哈希表的内存空间大小在初始HashMap不设置参数的情况下默认LoadFactor值为0.75。为什么是0.75这个值呢这是因为对于使用链表法的哈希表来说查找一个元素的平均时间是O(1n)这里的n指的是遍历链表的长度因此加载因子越大对空间的利用就越充分这就意味着链表的长度越长查找效率也就越低。如果设置的加载因子太小那么哈希表的数据将过于稀疏对空间造成严重浪费。那有没有什么办法来解决这个因链表过长而导致的查询时间复杂度高的问题呢你可以先想想我将在后面的内容中讲到。Entry数组的Threshold是通过初始容量和LoadFactor计算所得在初始HashMap不设置参数的情况下默认边界值为12。如果我们在初始化时设置的初始化容量较小HashMap中Node的数量超过边界值HashMap就会调用resize()方法重新分配table数组。这将会导致HashMap的数组复制迁移到另一块内存中去从而影响HashMap的效率。HashMap添加元素优化初始化完成后HashMap就可以使用put()方法添加键值对了。从下面源码可以看出当程序将一个key-value对添加到HashMap中程序首先会根据该key的hashCode()返回值再通过hash()方法计算出hash值再通过putVal方法中的(n - 1) hash决定该Node的存储位置。public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }if ((tab table) null || (n tab.length) 0) n (tab resize()).length; //通过putVal方法中的(n - 1) hash决定该Node的存储位置 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);如果你不太清楚hash()以及(n-1)hash的算法就请你看下面的详述。我们先来了解下hash()方法中的算法。如果我们没有使用hash()方法计算hashCode而是直接使用对象的hashCode值会出现什么问题呢假设要添加两个对象a和b如果数组长度是16这时对象a和b通过公式(n - 1) hash运算也就是(16-1)a.hashCode和(16-1)b.hashCode15的二进制为0000000000000000000000000001111假设对象 A 的 hashCode 为 1000010001110001000001111000000对象 B 的 hashCode 为 0111011100111000101000010100000你会发现上述与运算结果都是0。这样的哈希结果就太让人失望了很明显不是一个好的哈希算法。但如果我们将 hashCode 值右移 16 位h 16代表无符号右移16位也就是取 int 类型的一半刚好可以将该二进制数对半切开并且使用位异或运算如果两个数对应的位置相反则结果为1反之为0这样的话就能避免上面的情况发生。这就是hash()方法的具体实现方式。简而言之就是尽量打乱hashCode真正参与运算的低16位。我再来解释下(n - 1) hash是怎么设计的这里的n代表哈希表的长度哈希表习惯将长度设置为2的n次方这样恰好可以保证(n - 1) hash的计算得到的索引值总是位于table数组的索引之内。例如hash15n16时结果为15hash17n16时结果为1。在获得Node的存储位置后如果判断Node不在哈希表中就新增一个Node并添加到哈希表中整个流程我将用一张图来说明从图中我们可以看出在JDK1.8中HashMap引入了红黑树数据结构来提升链表的查询效率。这是因为链表的长度超过8后红黑树的查询效率要比链表高所以当链表超过8时HashMap就会将链表转换为红黑树这里值得注意的一点是这时的新增由于存在左旋、右旋效率会降低。HashMap获取元素优化当HashMap中只存在数组而数组中没有Node链表时是HashMap查询数据性能最好的时候。一旦发生大量的哈希冲突就会产生Node链表这个时候每次查询元素都可能遍历Node链表从而降低查询数据的性能。特别是在链表长度过长的情况下性能将明显降低红黑树的使用很好地解决了这个问题使得查询的平均复杂度降低到了O(log(n))链表越长使用黑红树替换后的查询效率提升就越明显。我们在编码中也可以优化HashMap的性能例如重写key值的hashCode()方法降低哈希冲突从而减少链表的产生高效利用哈希表达到提高性能的效果。HashMap扩容优化在JDK1.7 中HashMap整个扩容过程就是分别取出数组元素一般该元素是最后一个放入链表中的元素然后遍历以该元素为头的单向链表元素依据每个被遍历元素的 hash 值计算其在新数组中的下标然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。而在 JDK 1.8 中HashMap对扩容操作做了优化。由于扩容数组的长度是 2 倍关系所以对于假设初始 tableSize 4 要扩容到 8 来说就是 0100 到 1000 的变化左移一位就是 2 倍在扩容中只用判断原来的 hash 值和左移动的一位newtable 的值按位与操作是 0 或 1 就行0 的话索引不变1 的话索引变成原索引加上扩容前数组。之所以能通过这种“与运算“来重新分配索引是因为 hash 值本来就是随机的而hash 按位与上 newTable 得到的 0扩容前的索引位置和 1扩容前索引位置加上扩容前数组长度的数值索引处就是随机的所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。我们还可以在预知存储数据量的情况下提前设置初始容量初始容量预知数据量/加载因子。这样做的好处是可以减少resize()操作提高HashMap的效率。