11/2 哈希表查找成败平均次数计算

散列表的装填因子 定义：α= 填入表中的元素个数 / 散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小
通常，只要a取的合适（一般取0.7-0.8之间），哈希表的平均查找长度就会是常数也就是O（1）级别的。

线性探测和二次探测必须考虑载荷因子，超过0.7-0.8就增容，增大效率，（以空间换时间）

• 查找成功： 查找次数/数据个数
• 查找失败： 探查次数/散列表的表长。

问题主要是查找不成功的次数那里，不是0-r-1的区间循环，而是整个哈希表内循环，只计算前r个地址的不成功次数。

数据结构哈希函数，求线性探测法查找失败时的平均查找长度

因为是mod11，所以查找失败总共有11种情况。也就是 (3*k)%11的余数是0-10的时候。
逐个看下就行了。
余数为：

平方探测

https://blog.****.net/m0_38015368/article/details/78694496

一个n 阶对称矩阵A的下三角部分按行优先(row major)顺序压缩存储在一维数组B中，其中B[0]存储矩阵中第1个元素a11, 则元素aij (i ≤ j)存放在

对称矩阵

在一个n阶方阵A中，若元素满足下述性质：

1.a_ij=a_ji
2.0≤i，j≤n-1
则称A为对称矩阵。

对称矩阵的压缩存

对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。

①按"行优先顺序"存储主对角线(包括对角线)以下的元素

即按a₀₀,a₁₀,a₁₁,……，a_n-1,0,a_n-1,1…，a_n-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）。

其中：

sa[0]=a₀₀,

sa[1]=a₁₀,

……，

sa[n(n+1)／2-1]=a_n-1,n-1

②元素aij的存放位置

aij元素前有i行(从第0行到第i-1行)，一共有：

1+2+…+i=i×(i+1)／2个元素；

在第i行上，aij之前恰有j个元素(即ai0，a_i1，…，a_ij-1)，因此有：

sa[i×(i+1)／2+j]=a_ij

③a_ij和sa[k]之间的对应关系：

• 若i≥j，k=i×(i+1)／2+j
  0≤k<n(n+1)／2

• 若i＜j，k=j×(j+1)／2+i
  0≤k<n(n+1)／2

令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：

k=i×(i+1)／2+j0≤k<n(n+1)／2

（3）对称矩阵的地址计算公式

LOC(aij)=LOC(sa[k])

=LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d

通过下标变换公式，能立即找到矩阵元素aij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。

【例】a₂₁和a₁₂均存储在sa[4]中，这是因为

k=I×(I+1)／2+J=2×(2+1)／2+1=4

参考：https://baike.so.com/doc/279162-295488.html

关于拉链法查找失败长度

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组t[0…m-1]。凡是散列地址为i的结点，均插入到以t为头指针的单链表中。t中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。

一个10阶对称矩阵A的下三角部分按行优先(row major)顺序压缩存储在一维数组B中，则数组B的大小应为