Come posso evitare di dover verificare l'esistenza di un altro vertice quando si aggiunge a un elenco di adiacenza?

Sto scrivendo un grafico e ho deciso di fare in modo che l'Adjacency List fosse la sua classe.

In questo momento, (ridotto) sembra che:

public class AdjacencyList<Vertex> {

    //A map between a vertex, and a list of vertices that it connects to.
    private HashMap<Vertex, HashSet<Vertex>> vertices =
        new HashMap<Vertex, HashSet<Vertex>>();

    //Adds a new vertex, and gives it a list of outgoing vertices.
    public void addVertex(Vertex v, List<Vertex> outgoing) {
        vertices.put(v, new HashSet<Vertex>(outgoing));
    }

    //Adds a directed (one-way) edge to the given vertex.
    public void addDirectedToVertex(Vertex v, Vertex newVertex) {
        HashSet<Vertex> outgoingList = vertices.get(v);
        if (outgoingList != null) {
            outgoingList.add(newVertex);

        } else {
            throw new NoSuchElementException("Vertex " + v + " doesn't exist.");
        }
    }

}

Che andava bene, fino a quando ho capito che è possibile aggiungere un vertice alla lista in uscita di un vertice che non ha il suo posto nella mappa di hash. Ciò potrebbe portare a qualcuno che aggiunge un vertice alla lista in uscita di un altro vertice che altrimenti non esiste da nessuna parte; che sono sicuro che potrebbe causare problemi lungo la strada.

Per risolvere il problema, ho pensato di aggiungere un controllo in alto prima dell'aggiunta. Se il vertice da aggiungere alla lista non esiste in HashMap, potrei lanciarlo o dargli una propria voce. Qualcosa del genere:

//Adds a directed (one-way) edge to the given vertex.
public void addDirectedToVertex(Vertex v, Vertex newVertex) {
    if (!vertices.containsKey(newVertex)) {
        addVertex(newVertex);
    }

    HashSet<Vertex> outgoingList = vertices.get(v);
    if (outgoingList != null) {
        outgoingList.add(newVertex);

    } else {
        throw new NoSuchElementException("Vertex " + v + " doesn't exist.");
    }
}

Sfortunatamente, ciò significa che ogni aggiunta richiederà 2 ricerche, il che sembra inutilmente complicato.

È qualcosa di cui dovrei preoccuparmi, o sarebbe considerato un'ottimizzazione pre-matura?

Se questo è un problema legittimo, qualcuno può vedere un modo per riconfigurare le cose per migliorarlo?