Java数组随机存储对象

Question

数组表示停车场中的空闲座位。现在，汽车（线程）在随机时间停车，然后离开

我如何知道哪些插槽是免费的？我是否每次都必须迭代数组才能找到一个空闲插槽，还是有更好的解决方案？是否可以创建第二个数组并仅在其中存储空闲标记

我应该使用与数组不同的数据结构吗

Answer 1

Do I have to iterate the Array each time to find a free slot

您不必无休止地遍历数组来检查空闲插槽

让汽车在离开车位时通知你它的索引。当汽车即将进入时，请阅读阵列中的空闲插槽。输入后，标记索引

您可能有一个实现Runnable的Car对象：

class Car implements Runnable{
    private int pos;    //index of array
}

通知可以使用Observer模式实现，您可以在其中维护一个汽车列表。当汽车离开时，通知观察者

Answer 2

有许多不同的停车实施方法，它们在生动性和公平性方面可能有所不同。但是为了存放免费停车位，一定要排队。就java而言，如果您使用阻塞队列，您的折衷是公平性优于活动性，因为底层算法使用锁。对于非阻塞队列，折衷的方法是活跃度优于公平性，因为底层算法使用CAS而不是锁

我认为从停车场开始，根据最近的空闲位置将车按顺序停放是合理的。所以可以使用PriorityQueue（底层数据结构是min heap）。CopyOnWriteArrayList用作线程安全数组

  // a non blocking queue can be used instead of blocking
  private final BlockingQueue<Integer> queue;
  private final CopyOnWriteArrayList<ParkingPlace> places;

  public Parking(int numberOfPlaces) {
    places = new CopyOnWriteArrayList<>();
    queue = new PriorityBlockingQueue<>(numberOfPlaces, Integer::compareTo);
    for (int i = 0; i < numberOfPlaces; i++) {
      // preallocate
      places.add(null);
      queue.add(i);
    }
  }

  public static class ParkingPlace {
    private final long timeout;
    private final long id;

    public ParkingPlace(long timeout, long id) {
      this.timeout = timeout;
      this.id = id;
    }

    public long getTimeout() {
      return timeout;
    }

    public long getId() {
      return id;
    }

    @Override
    public String toString() {
      return "ParkingPlace{" +
          "timeout=" + timeout +
          ", id=" + id +
          '}';
    }
  }

  public static void main(String[] args) throws Exception {
    final Parking parking = new Parking(5);
    int numOfCars = 12;
    ExecutorService executorService = Executors.newFixedThreadPool(numOfCars);
    for (int i = 0; i < numOfCars; i++) {
      executorService.submit(parking::park);
    }
    try {
      Thread.sleep(500);
    } catch (InterruptedException e) {
      // ignored
    }
    System.out.println(parking.getState());
    executorService.shutdown();
    executorService.awaitTermination(5, TimeUnit.SECONDS);
  }

  public void park() {
    long id = Thread.currentThread().getId();
    Integer place;
    try {
      System.out.println("Car with id " + id + " has come to the parking");
      // should be replaced with busy loop for non-blocking queue
      place = queue.take();
    } catch (InterruptedException e) {
      // ignore
      return;
    }
    long timeout = (new Random().nextInt(10) + 1) * 100L;
    System.out.println("Car with id " + id + " will park for " + timeout + " millis at place " + place);
    ParkingPlace parkingPlace = new ParkingPlace(timeout, id);
    try {
      places.set(place, parkingPlace);
      try {
        Thread.sleep(timeout);
      } catch (InterruptedException e) {
        // ignore
      }
    } catch (Exception e) {
      e.printStackTrace();
    } finally {
      System.out.println("Car with id " + id + " has left the parking place " + place);
      // free place and return it back to queue
      places.set(place, null);
      queue.add(place);
    }
  }

  public List<ParkingPlace> getState() {
    return places;
  }

Answer 3

一个parkingNumber和Accounted（boolean）的ParkingSpace类，然后是一个List<ParkingSpace>

class ParkingSpace implements Runnable {
    private int parkingSlot;
    private boolean occupied;
}

最好让停车场告诉你停车场已被占用