用邻接矩阵A存无向图顶点间的关系,则A^n中aij代表i和j两点间走n步能到的方案数。
证明思路:矩阵相乘,考虑运算的过程及其背后对应的意义,相应行和列的元素相乘再相加,aik*akj,对称矩阵,0和1代表的意义,对应顶点间有路径,同时也巧妙地借用了0和1的特殊性。
打不出好看的公式,ε=(´ο`*)))
集合:具有共同性质的或合适一定条件的事物的全体,组成集合的这些个体成为元素。
集合之间常见的关系:包含(⊆),真包含(⊂),相等(=)。
笛卡尔积:设A,B为集合,以A中元素为第一元素,B中元素为第二元素构成有序对,所以这样的有序对组成的集合称为A与B的笛卡尔积,记作A×B。用符号化表示:A×B={<x,y>|x∈A∧y∈B}
对关系图的表示方法,一共有三种,简单的是集合,另外有两种,矩阵和关系图。
例题:
那么我们之前介绍了集合和关系R,那么现在介绍关系的n次幂。
设R为A上的关系,n为自然数,则R的n次幂定义:
(1)Rº={<x,x>|x∈A}
(2)?^(?+1)=?ⁿ ∘R
HashMap的容量为什么是2的n次幂,和这个(n - 1) & hash的计算方法有着千丝万缕的关系,符号&是按位与的计算,这是位运算,计算机能直接运算,特别高效,&的计算方法是,只有当对应位置的数据都为1时,运算结果也为1,当HashMap的容量是2的n次幂时,(n-1)的2进制也就是1111111***111这样形式的,这样与添加元素的hash值进行位运算时,能够充分的散列,使得添加的元素均匀分布在HashMap的每个位置上,减少hash碰撞,下面举例进行说明
由图可见,非2的n次幂的 (n - 1) & hash 算法,hash碰撞几率变大
用邻接矩阵A存无向图顶点间的关系,则A^n中aij代表i和j两点间走n步能到的方案数。
证明思路:矩阵相乘,考虑运算的过程及其背后对应的意义,相应行和列的元素相乘再相加,aik*akj,对称矩阵,0和1代表的意义,对应顶点间有路径,同时也巧妙地借用了0和1的特殊性。
打不出好看的公式,ε=(´ο`*)))
转载于:https://www.cnblogs.com/SUMaywlx/p/10887447.html
前言
逛了一圈发现大家对于这个问题的回答写的都比较散乱,简而言之两点原因:
1.为了保证得到的新的数组索引和老数组索引一致
2.rehash时的取余操作,hash % length == hash & (length - 1)这个关系只有在length等于二的幂次方时成立,位运算能比%高效得多
论述
1.为了保证得到的新的数组索引和老数组索引一致。HashMap的初始容量是2的n次幂,扩容也是2倍的形式进行扩容,是因为容量是2的n次幂,可以使得添加的元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!
hashMap的数组长度一定保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换),个人理解。
还有,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀,比如:
我们看到,上面的&运算,高位是不会对结果产生影响的(hash函数采用各种位运算可能也是为了使得低位更加散列),我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。参考文章 https://blog.csdn.net/samniwu/article/details/90550196
2.rehash时的取余操作,hash % length == hash & (length - 1)这个关系只有在length等于二的幂次方时成立,位运算能比%高效得多。