Отметить пустое пространство в массиве, не используя ноль

Question

Я расширяю AbstractMap и хочу реализовать свою собственную хэш-карту, используя два параллельных массива:

K[] keys;
V[] values;

Предположим, я хочу также сохранить значения null, как я могу инициализировать эти два массива, чтобы я мог различать пространство в массиве, где я мог бы разместить несколько новых пар ключ-значение, и пространство, в котором я храню null?

Answer 1

Могу ли я предложить не использовать два массива, а вместо этого сделать что-то вроде:

class Node {
    K key;
    V value;
}

Node[] nodes;

Тогда не запись - это элемент в nodes, равный null.

Answer 2

Сохранение значения null не является проблемой в вашем сценарии. Пока keys[n] != null, просто верните values[n], values[n] равно null или нет.

Помните, что вас не просят ввести n, но объекты типа K, поэтому при каждом доступе к Map потребуется поиск по keys, чтобы найти ключ, который они ищут.

Однако, если вы хотите разрешить хранение value против ключа null, тогда использование чего-то вроде private static final Object NULL_KEY = "NULL", вероятно, сработает, как указывают другие предложения.

private static final Object NULL_KEY = "NULL";
K[] keys;
V[] values;

private int find(K key) {
  for (int i = 0; i < keys.length; i++) {
    if (keys[i] == key) {
      return i;
    }
  }
  return -1;
}

public V put(K key, V value) {
  V old = null;
  if (key != null) {
    int i = find(key);
    if (i >= 0) {
      old = values[i];
      values[i] = value;
    } else {
      // ...
    }
  } else {
    return put((K) NULL_KEY, value);
  }
  return old;
}

public V get(K key) {
  if (key != null) {
    int i = find(key);
    if (i >= 0) {
      return values[i];
    }
    return null;
  } else {
    return (get((K) NULL_KEY));
  }
}

Answer 3

Поскольку может быть только один нулевой ключ, вы можете просто иметь специальное ссылочное значение (не в массиве), которое содержит значение объекта, сопоставленного с этим нулевым ключом (и, возможно, логическое значение, указывающее, установлено ли это значение).К сожалению, это, вероятно, усложнит итерацию.

Например,

private boolean isNullMapped = false;
private V nullValue = null;

public put(K key, V value)
{
  if (key == null) { nullValue = value; }
  ...
}

В качестве альтернативы вы можете обернуть все ключи в объект-обертку (предположим, что вы все равно хотите использовать параллельные массивы вместо записей), и еслизначение, содержащееся в этом объекте-обертке, равно нулю, тогда он представляет собой нулевой ключ.

Например,

private static class KeyWrapper<K>
{
  public K key;
}

Наконец, в качестве вопроса для рассмотрения, если у вас нет записей в ваших массивах, но вместо этого непосредственно хранят массивы K и V, тогда как вы учитываете различные ключи, которые совместно используют один и тот же хэш-код?Реализация java.util имеет массивы записей, которые также действуют как связанные списки, чтобы учесть эту возможность (и, кстати, нулевой ключ всегда сопоставляется с индексом массива 0).

Answer 4

В реализации java.util используется специальный объект, представляющий нуль.

Answer 5

Не совсем уверен в деталях вашего вопроса, но у вас всегда может быть какой-то особый объект для вашего "пробела".

private static final Object BLANK = new Object();

Тогда, если элемент в массиве == BLANK, то рассмотрите его какпустое место.

Answer 6

Если значения могут быть нулевыми, но ключи не могут быть нулевыми, то наличие нулевого ключа будет означать, что ключа нет.

Если ключ также может быть нулевым, вы можете использовать параллельный массив логических значений для хранения данных о том, занят ли каждый пробел или нет.

K[] keys;
V[] values;
boolean[] hasValue;