数据结构中散列表的装填因子

Question

数据结构中散列表的装填因子能不能大于一？
如果使用链地址法来处理冲突的话，一直链接下去的话，是不是装填因子就会大于一。

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7793643
• 这篇博客你也可以参考下：散列表查找成功的平均查找长度实质 开散列和闭散列 链地址法举例 闭散列负载因子  开散列的负载因子
• 除此之外, 这篇博客: 已知树中非叶子节点的度数和数量，如何计算树中叶子节点的个数？中的 求解 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  这里假设树中有 S 个结点，根据定义可知，树的总度数则为 S-1；

  再假设树中有 X 个叶子结点，则能得出式子

  S = X + 4 + 3 + 2 + 2
  S-1 = 0*X + 1*4 + 2*3 + 3*2 + 4*2
  

  两个方程式，求解两个未知数，这是必然能够解出来的，求得

  S = 25
  X = 14
  

  因此，树中有 14 个叶子结点。
  
  

• 您还可以看一下 张传波老师的软件设计是怎样炼成的？课程中的 详细设计是架构设计的延续小节, 巩固相关知识点
  
• 以下回答来自chatgpt:

  回答：

  散列表的装填因子可以大于1，但是过大的装填因子会导致散列表的性能下降，因为会导致冲突的概率增加。一般建议装填因子不要超过0.75。

  使用链地址法解决散列表中的冲突时，确实可能会出现装填因子大于1的情况。但是这并不需要特别担心，因为链地址法本身就是为了解决冲突而存在，通过链表连接冲突的元素，可以让散列表的性能更优秀。当然，仍需注意装填因子过大的问题。

  回文子串个数问题可以使用动态规划来解决。下面给出Java代码实现，具体思路和注释已经写在代码中了：

  import java.util.Scanner;
  public class 回文子串个数 {
  
      public static void main(String[] args) {
          Scanner val = new Scanner(System.in);
          String s = val.next();
          System.out.println(s);
          System.out.println(countSubstrings(s));
  
      }
      static int countSubstrings(String s) {
          int count=0;
          int length = s.length();//获取字符串的长度
          boolean[][] dp = new boolean[length][length];
          //从下往上，从左往右遍历
          for(int i=length-1;i>=0;i--) {
              for(int j=i;j<length;j++) {
                  if(s.charAt(i) != s.charAt(j)) {
                      //如果两端不相等，不是回文串 
                      continue;
                  }
                  //两端相等，如果字符串长度<=2或者左下方的dp值为true，则当前dp值也为true
                  dp[i][j] = (j-i <= 2 || dp[i+1][j-1]);
                  if(dp[i][j]) {
                      //如果当前dp值为true，则回文个数+1
                      count++;
                  }
              }
          }
          return count;
      }
  }
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^