Mappa / archivio ID tempo di esecuzione per gli oggetti

Question

Mappa / archivio ID tempo di esecuzione per gli oggetti

#1 da (1 voti)
#2 da (0 voti)

1

Cosa voglio ottenere: Ho bisogno di ottenere un id (unico) di esecuzione per "qualsiasi oggetto" (per le classi sia in java SE, le classi che ho creato o classi fornite da altre terze parti ... qualsiasi istanza di una classe).

Idealmente dovrebbe essere facile come:

Map<Object, UUID> objId = new HashMap<>();
MyClassFoo foo = new MyClassFoo();
UUID fooId = objId.getOrElse(foo, UUID.randomUUID());
if (!objId.containsKey(foo)) {
    objId.put(foo, fooId);
}

// From here onwards whenever I need the runtime ID for foo I can get it from the map objId

Il problema:

Questo non funzionerà con oggetti mutabili poiché il mio oggetto può continuare a cambiare da qui il suo codice hash, e tutti conosciamo i problemi che si potrebbero presentare quando si lavora con una mappa usando un oggetto mutabile come chiave.

Inoltre tale approccio non funziona a causa di limitazioni come: non è possibile utilizzare un ArrayList come chiave se ArrayList è un elenco di elenchi che contiene se stesso, poiché la mappa tenterà di utilizzare il suo hashCode. L'implementazione del codice hash per ArrayList richiede il calcolo dell'hashCode di tutti gli oggetti contenuti che causano un overflow dello stack per gli elenchi autonomi.

Ciò di cui ho bisogno dalla community: Ho bisogno di sapere più (o un paio di buone proposte di alternative a quella mappa) un modo efficace per ottenere ciò che voglio. Ho considerato un List<Pair<Object, UUID>> ordinato e faccio una ricerca binaria su di esso ogni volta che ho bisogno dell'ID per un oggetto, ma oltre a rendere l'implementazione un po 'più complessa sono anche preoccupato dell'impatto sulle prestazioni di tale cambiamento (dato che tale la lista può contenere da poche coppie di oggetti fino a diversi milioni).

Ho fatto i miei compiti a casa ? Penso di sì, oltre a considerare possibili alternative (come quella sopra menzionata), ho cercato di trovare un'implementazione diversa di una mappa che soddisfi le mie esigenze, ma tutte sembrano utilizzare l'hashCode dell'oggetto chiave.

Questa è una domanda basata sull'opinione? Beh ... sì, ma non mi piacerebbe che fosse etichettato come tale, dal momento che ciò che sto chiedendo sono alternative per risolvere il mio problema e le implicazioni / aspetti della performance da considerare per l'implementazione di tali proposte.

P.S: Sto lavorando nel linguaggio Java ma il concetto del problema può essere applicato indipendentemente da quello.

java hashing map

posta Ordiel 22.08.2017 - 21:10

fonte

2 risposte

Leggi altre domande sui tag java hashing map

Autorizzazione e autenticazione in un'applicazione DDD Un progetto per soluzione per creare pacchetti di nuget

score 1 · Answer 1

Potresti mettere oggetti in un secchio dalla loro classe concreta. La classe di un oggetto non può cambiare dopo l'istanziazione e questo aiuterà a ridurre immediatamente lo spazio di ricerca (se c'è una distribuzione abbastanza uniforme delle classi dell'oggetto). La seconda raccomandazione che farò è che puoi ancora utilizzare Map<Object, UUID> . Dovresti scorrere l'intera mappa se hai una mappa mancante e aggiornare l'oggetto sulla mappa se l'hash è cambiato. Ecco un po 'di codice per illustrare:

Map<Class, Map<Object, UUID>> ids = new HashMap<>();

// Create new id for object
UUID assignId(Object obj) {
    UUID uuid = UUID.randomUUID();
    if (!ids.containsKey(obj.getClass())) {
        ids.put(obj.getClass(), new HashMap<>());
    }
    ids.get(obj.getClass()).put(obj, uuid);
}

// Get id of object
UUID retrieveId(Object obj) {
    Map<Object, UUID> classMap = ids.get(obj.getClass());
    if (classMap == null) {
        return null;
    }
    UUID hit = classMap.get(obj);
    // if hit is non-null then the object's hashcode hasn't changed 
    // and search is fast
    if (hit != null) {
        return hit;
    }
    // obj has mutated since we stored its id, or obj doesn't have an id
    Iterator<Entry<Object, UUID>> itr = classMap.entrySet().iterator();
    UUID uuid = null;
    while(itr.hasNext()){
        Entry<Object, UUID> entry = itr.next();
        if (entry.getKey() == obj) {
            // we found our object
            uuid = entry.getValue();
            // remove the entry from the map (with the old hashcode)
            itr.remove();
        }
    }
    if (uuid == null) {
        // object doesn't have an id at all
        return null;
    }
    // reinsert the object into the map to get a new hash code
    // makes search faster next lookup (if the hashcode doesn't change)
    classMap.put(obj, uuid);
}

Questo algoritmo verrà eseguito in O (1) volta se l'hashcode dell'oggetto non è cambiato o O (n) se l'hashcode è cambiato.

score 0 · Answer 2

Se è fattibile, puoi ereditare tutte le tue classi da una superclasse che ha UUID come proprietà readonly uguale al valore hash del timestamp quando è stato istanziato più qualche altro identificatore relativo al tipo di classe originale.

se l'applicazione è in esecuzione su più macchine, è possibile aggiungere il valore hash del server su cui si sta eseguendo.

puoi implementare il metodo del generatore UUID nella superclasse e chiamarlo nei costruttori.