首页  |  知识库  |  资源下载  |  在线工具  |  A-Z  •  JAR  •  名词查         

关于jeromq源码包中定义MultiMap两个HashMap加快搜索速度和满足多场景应用

标签:MultiMap,自定义Map,jeromq,性能,源码分析     发布时间:2018-03-31   

一、前言

对于HashMap的数据结构是基于数组+链表或红黑树,对于值value的搜索无法达到线性搜索高效(O(nlgn)),现在JeroMQ的(jeromq-master源码包)zmq.util.MultiMap分别定义了两个HashMap,一个存储普通键值対,另外一个存值键对V->K(相对创建值的索引空间),这样对于Value的遍历所示根据的快速,同时可以满足很多场景的实用。

二、源码说明

package zmq.util;@b@@b@import java.util.ArrayList;@b@import java.util.Collection;@b@import java.util.Collections;@b@import java.util.Comparator;@b@import java.util.HashMap;@b@import java.util.List;@b@import java.util.Map;@b@import java.util.Map.Entry;@b@@b@// custom implementation of a collection mapping multiple values, tailored for use in the lib.@b@// this class is definitely not thread-safe, and allows only one mapping per key-value@b@// aka if the same value is correlated to a new key, the old mapping is removed.@b@public final class MultiMap<K extends Comparable<? super K>, V>@b@{@b@    // sorts entries according to the natural order of the keys@b@    private final class EntryComparator implements Comparator<Entry<V, K>>@b@    {@b@        @Override@b@        public int compare(Entry<V, K> first, Entry<V, K> second)@b@        {@b@            return first.getValue().compareTo(second.getValue());@b@        }@b@    }@b@@b@    private final Comparator<? super Entry<V, K>> comparator = new EntryComparator();@b@@b@    // where all the data will be put@b@    private final Map<K, List<V>> data;@b@    // inverse mapping to speed-up the process@b@    private final Map<V, K> inverse;@b@@b@    public MultiMap()@b@    {@b@        data = new HashMap<>();@b@        inverse = new HashMap<>();@b@    }@b@@b@    public void clear()@b@    {@b@        data.clear();@b@        inverse.clear();@b@    }@b@@b@    public Collection<Entry<V, K>> entries()@b@    {@b@        List<Entry<V, K>> list = new ArrayList<>(inverse.entrySet());@b@        Collections.sort(list, comparator);@b@        return list;@b@    }@b@@b@    public Collection<V> values()@b@    {@b@        return inverse.keySet();@b@    }@b@@b@    public V find(V copy)@b@    {@b@        K key = inverse.get(copy);@b@        if (key != null) {@b@            List<V> list = data.get(key);@b@            return list.get(list.indexOf(copy));@b@        }@b@        return null;@b@    }@b@@b@    public boolean hasValues(K key)@b@    {@b@        List<V> list = data.get(key);@b@        if (list == null) {@b@            return false;@b@        }@b@        return !list.isEmpty();@b@    }@b@@b@    public boolean isEmpty()@b@    {@b@        return inverse.isEmpty();@b@    }@b@@b@    private List<V> getValues(K key)@b@    {@b@        List<V> list = data.get(key);@b@        if (list == null) {@b@            list = new ArrayList<>();@b@            data.put(key, list);@b@        }@b@        return list;@b@    }@b@@b@    public boolean insert(K key, V value)@b@    {@b@        K old = inverse.get(value);@b@        if (old != null) {@b@            removeData(old, value);@b@        }@b@        boolean inserted = getValues(key).add(value);@b@        if (inserted) {@b@            inverse.put(value, key);@b@        }@b@        return inserted;@b@    }@b@@b@    public Collection<V> remove(K key)@b@    {@b@        List<V> removed = data.remove(key);@b@        if (removed != null) {@b@            for (V val : removed) {@b@                inverse.remove(val);@b@            }@b@        }@b@        return removed;@b@    }@b@@b@    public boolean remove(V value)@b@    {@b@        K key = inverse.remove(value);@b@        if (key != null) {@b@            return removeData(key, value);@b@        }@b@        return false;@b@    }@b@@b@    public boolean remove(K key, V value)@b@    {@b@        boolean removed = removeData(key, value);@b@        if (removed) {@b@            inverse.remove(value);@b@        }@b@        return removed;@b@    }@b@@b@    private boolean removeData(K key, V value)@b@    {@b@        boolean removed = false;@b@        List<V> list = data.get(key);@b@        if (list != null) {@b@            removed = list.remove(value);@b@            if (list.isEmpty()) {@b@                data.remove(key);@b@            }@b@        }@b@        return removed;@b@    }@b@@b@    @Override@b@    public String toString()@b@    {@b@        return data.toString();@b@    }@b@}