Java线性探测哈希表：如何不通过0或null判断数组索引是否未初始化

原代码的核心问题在于：int数组默认初始值为0，导致无法正确存储0——判断table[key]!=0会把未使用的位置误判为已占用，而用null判断又会因为int是基本类型报错。以下是几种可行的解决办法：

• 使用Integer包装类数组
  把int数组换成Integer数组，未占用位置的初始值为null，可通过null判断是否空闲，存储0时Java会自动装箱为Integer.valueOf(0)，不会和null混淆。修改后的代码：

  public class LinearProbing {
      private Integer table[];
      private int size;
  
      LinearProbing(int size) {
          this.size = size;
          table = new Integer[size];
      }
  
      public void hash(int value) {
          int key = value % size;
          while (table[key] != null) {
              key++;
              if (key == size) {
                  key = 0;
              }
          }
          table[key] = value;
      }
  
      public void display() {
          for (int i = 0; i < size; i++) {
              System.out.println(i + "->" + table[i]);
          }
      }
  }
  

  优点是改动最小、逻辑清晰；缺点是存在少量装箱拆箱的性能开销，多数场景下可忽略。

• 单独维护占用状态数组
  新增一个boolean类型的occupied数组，专门标记每个位置是否被占用，初始值全为false。存储值时将对应位置的occupied[key]设为true，判断空闲只看occupied[key]，和存储的int值无关。修改后的代码：

  public class LinearProbing {
      private int table[];
      private boolean occupied[];
      private int size;
  
      LinearProbing(int size) {
          this.size = size;
          table = new int[size];
          occupied = new boolean[size];
      }
  
      public void hash(int value) {
          int key = value % size;
          while (occupied[key]) {
              key++;
              if (key == size) {
                  key = 0;
              }
          }
          table[key] = value;
          occupied[key] = true;
      }
  
      public void display() {
          for (int i = 0; i < size; i++) {
              System.out.println(i + "->" + table[i]);
          }
      }
  }
  

  优点是避免了包装类的类型转换开销，逻辑直观，适合性能敏感场景；缺点是多维护一个数组，占用额外内存。

• 使用特殊哨兵值标记空闲位置
  选择一个业务中不会用到的int值作为哨兵，比如Integer.MIN_VALUE（-2147483648），初始化数组时将所有位置设为该哨兵值，判断空闲时检查table[key] != 哨兵值，这样存储0就不会和空闲标记冲突。修改后的代码：

  public class LinearProbing {
      private int table[];
      private int size;
      private static final int EMPTY = Integer.MIN_VALUE;
  
      LinearProbing(int size) {
          this.size = size;
          table = new int[size];
          // 初始化所有位置为哨兵值
          for (int i = 0; i < size; i++) {
              table[i] = EMPTY;
          }
      }
  
      public void hash(int value) {
          int key = value % size;
          while (table[key] != EMPTY) {
              key++;
              if (key == size) {
                  key = 0;
              }
          }
          table[key] = value;
      }
  
      public void display() {
          for (int i = 0; i < size; i++) {
              System.out.println(i + "->" + (table[i] == EMPTY ? "空" : table[i]));
          }
      }
  }
  

  优点是无需额外数组，也没有包装类开销；缺点是必须确保业务数据不会用到该哨兵值，否则会出现冲突。

内容的提问来源于stack exchange，提问作者BhanuPrakashSakkuri