Come eliminare un particolare oggetto List in Java?

Question

Ho una lista di circa 100.000 impiegati in Java. Ora voglio eliminare rapidamente un determinato oggetto dipendente dall'elenco. Quali sono i modi possibili per farlo senza iterare l'intera lista? (Se eseguo l'iterazione di ciascun oggetto, confronta i dettagli, quindi elimina: questo scenario richiede molto tempo)

Answer 1

È necessario trovare un modo per trovare rapidamente l'oggetto. Si potrebbe

• hanno un ArrayList ordinato e quindi eseguire una ricerca binaria con Collections.binarySearch O(log N) Nota: in realtà la rimozione di un elemento da un ArrayList è O(n) Mentre LinkedList come O(1) per rimuovere, una ricerca binaria su di esso sarebbe inutile cioè molto più lento di O(N)
• si potrebbe avere invece un Set di dipendenti di hash e la rimozione sarebbe O(1) ammortizzata. È possibile utilizzare un LinkedHashSet se si desidera conservare un ordine come l'ordine di inserimento.
• potresti rendere l'oggetto mutabile e avere un campo come enabled che hai impostato su false invece di rimuoverlo. Si potrebbe rimuoverlo in seguito come un processo batch in un momento (durante la notte o durante il fine settimana)

Answer 2

Ora voglio cancellare un particolare oggetto dipendente dalla lista ...

Si può solo utilizzare List.remove per fare questo

... rapidamente

In pratica, anche anche se la rimozione dell'elemento potrebbe essere un'operazione O(1), l'iterazione su tutta la lunghezza dell'elenco è O(n) ed è, come si sospetta, non molto veloce.

Ritengo che il problema sarebbe meglio essere servito dalla potenza di una mappa di hash. Questo ha una costante ricerca e tempi di rimozione. La classe LinkedHashMap potrebbe soddisfare le tue esigenze. Mantiene l'ordine di inserimento nello stesso modo di un elenco collegato, ma ha anche l'inserimento e la cancellazione di un tempo costante.