Марк пустое пространство в массив без использования нуль

Question

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

K[] keys; 
V[] values; 

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

Answer 1

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

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

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

Answer 2

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

private static final Object BLANK = new Object(); 

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

Answer 3

Может я предлагаю не использовать два массива, и вместо того, чтобы сделать что-то вдоль линий:

class Node { 
    K key; 
    V value; 
} 

Node[] nodes; 

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

Answer 4

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

Answer 5

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

E.g.

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

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

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

E.g.

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

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

Answer 6

Хранение nullЗначение не является проблемой в вашем случае. До тех пор, пока keys[n] != null, просто верните values[n], values[n] is 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)); 
    } 
}