Table de hachage triée (Carte, Dictionnaire) Conception de la structure de données

Qu'est-ce que vous envisagez est une haquetable avec des pointeurs dans les entrées à la prochaine entrée dans la commande triée. C'est beaucoup comme le LinkedHashMap dans Java, sauf que les liens suivent un ordre de tri plutôt que l'ordre d'insertion. Vous pouvez réellement mettre en œuvre cela totalement en enveloppant une liaison LinkedHashMap et que la mise en oeuvre de transfert de tri les entrées du LinkedHashMap dans un Treemap, puis de nouveau dans une liaison LinkedHashMap.

Voici une implémentation qui trie les entrées dans une liste de matrices plutôt que de transférer à une carte d'arbre. Je pense que l'algorithme de tri utilisé par Collection.Sort fera un bon travail de fusion des nouvelles entrées dans la partie déjà triée. P>

public class SortaSortedMap<K extends Comparable<K>,V> implements Map<K,V> {

    private LinkedHashMap<K,V> innerMap;

    public SortaSortedMap() {
        this.innerMap = new LinkedHashMap<K,V>();
    }

    public SortaSortedMap(Map<K,V> map) {
        this.innerMap = new LinkedHashMap<K,V>(map);
    }

    public Collection<V> values() {
        return innerMap.values();
    }

    public int size() {
        return innerMap.size();
    }

    public V remove(Object key) {
        return innerMap.remove(key);
    }

    public V put(K key, V value) {
        return innerMap.put(key, value);
    }

    public Set<K> keySet() {
        return innerMap.keySet();
    }

    public boolean isEmpty() {
        return innerMap.isEmpty();
    }

    public Set<Entry<K, V>> entrySet() {
        return innerMap.entrySet();
    }

    public boolean containsKey(Object key) {
        return innerMap.containsKey(key);
    }

    public V get(Object key) {
        return innerMap.get(key);
    }

    public boolean containsValue(Object value) {
        return innerMap.containsValue(value);
    }

    public void clear() {
        innerMap.clear();
    }

    public void putAll(Map<? extends K, ? extends V> m) {
        innerMap.putAll(m);
    }

    public void sort() {
        List<Map.Entry<K,V>> entries = new ArrayList<Map.Entry<K,V>>(innerMap.entrySet());
        Collections.sort(entries, new KeyComparator());
        LinkedHashMap<K,V> newMap = new LinkedHashMap<K,V>();
        for (Map.Entry<K,V> e: entries) {
            newMap.put(e.getKey(), e.getValue());
        }
        innerMap = newMap;
    }

    private class KeyComparator implements Comparator<Map.Entry<K,V>> {

        public int compare(Entry<K, V> o1, Entry<K, V> o2) {
            return o1.getKey().compareTo(o2.getKey());
        }

    }

}

Pourquoi avez-vous besoin exactement d'une fonction de tri ()?
Que voulez-vous peut-être et besoin d'un arbre noir rouge.

http://fr.wikipedia.org/wiki/red-black_tree

Ces arbres sont automatiquement trier votre entrée par un comparateur que vous donnez. Ils sont complexes, mais ont d'excellentes caractéristiques O (n). Couple de vos entrées d'arbres comme clé avec un hachage Carte comme dictionnaire et vous obtenez votre DataStructure.

en Java, il est implémenté comme Treemap en tant qu'instance de type.