集合：具有共同性质的或合适一定条件的事物的全体，组成集合的这些个体成为元素。

集合之间常见的关系：包含（⊆），真包含（⊂），相等（=）。

笛卡尔积：设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等于二的幂次方时成立，位运算能比%高效得多。
参考文章https://www.cnblogs.com/littleKing163/p/5695153.html