JAVA集合——Map原理浅析

JAVA开发 workingTime 389℃ 0评论

Map即映射表:它存放的是键值对关联的对象。因此,可以通过键来查找值。

在了解Map之前,我们通过Map的概念,先思考几个问题:

  • map如何存放键-值的?
  • map如何确定键的唯一性?
  • map如何通过键快速查找值?
  • 自己如何实现一个简单的map?

抱着提出问题,解决问题的态度,让我们开始map之旅吧。

第一步:来实现一个能想到的最简单的Map

我能想到的最简单的map就是将key和value放入一个二维数组中,然后根据key去数组中循环查找value。

二话不说,开撸:

public class AssociativeArray<K, V> {
    //定义pairs二维数组
    private Object[][] pairs;
    private int index;

    /**
     * 定义固定长度的数组
     * */
    public AssociativeArray(int length) {
        //pairs二维数组的长度是length,宽度为2
        pairs = new Object[length][2];
    }

    public void put(K key, V value) {
        if (index >= pairs.length) {
            throw new ArrayIndexOutOfBoundsException();
        }
        //将key和value放入数组
        pairs[index++] = new Object[]{key, value};
    }
    /**
     * 根据key来查询value的值
     * */
    public V get(K key) {
        for (int i = 0; i < index; i++) {
            if (key.equals(pairs[i][0])) return (V) pairs[i][1];
        }
        return null;
    }
    /**
     * 重写toString方法,输出map中的数据
     * */
    public String toString() {
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < index; i++) {
            result.append(pairs[i][0].toString());
            result.append(":");
            result.append(pairs[i][1].toString());
            if (i < index - 1) result.append("\n");
        }
        return result.toString();
    }

    public static void main(String[] args) {
            //因为打算存5个元素,所以给数组固定一个长度为5
        AssociativeArray<String,String> map = new AssociativeArray<>(5);
        map.put("111","aaa");
        map.put("222","bbb");
        map.put("333","ccc");
        map.put("444","ddd");
        map.put("555","eee");

        System.out.println(map);
        System.out.println(map.get("333"));
    }
}

上面的代码,输出结果符合预期,确实把对象对进去了,也取出来了。但是总感觉哪里不对?

  • 首先,数组长度是固定的,我怎么可能每次都知道要传入的数组长度呢?
  • 再有,每次根据key取value值,都要将数组循环一边,那要是这个数组很大,这性能差的要死啊。
  • 最后,这个代码实在很low,一点也不高大上呀。

散列码和hashCode()

为了解决性能问题,HashMap使用了特殊值,散列码,来取代对键的缓慢搜索。

那什么是散列码呢?

散列码是:”相对唯一“的,用以代表对象的int值,它是通过将该对象的某些信息进行转换后由hashCode()生成的。

先来看一下不用散列码的例子:一个优秀的射击运动员在训练,向靶子射击10枪,设计完成后,想查看自己某一枪是否命中。

public class Shoot {
    protected int number;   //射击次数
    public Shoot(int n){this.number = n;}
    public String toString(){
        return "Shoot # " + number;
    }
}
public class Points {
    private static Random ran = new Random();
    //假设0-10环为命中,其他为脱靶
    private boolean shadow = ran.nextInt(20) < 10 && ran.nextInt(20) > 0;
    public String toString(){
        if (shadow) return "命中!";
        else return "脱靶!";
    }
}

AssociativeArray类的main方法稍加改动

public static void main(String[] args) {  
   AssociativeArray<Groundhog,Prediction> map = new AssociativeArray<>(10);
   for (int i = 0;i<10;i++){
       map.put(new Shoot(i),new Points());
   }
   //打印map中的值
   System.out.println(map);
   //查看第三次射击是否命中,这时候发现输出是null
   System.out.println(map.get(new Shoot(2)));
}

在打印map的值时,可以看到KEY中明明有2这个键,可为什么map.get(new Shoot(2))输出是null呢?

原因:问题出在Shoot自动地继承自基类Object,所以这里使用Object的hashCode()方法生成散列码,而他默认是使用对象的地址计算散列码。因此,由new Shoot(2)生成的第一个实例的散列码与由new Shoot(2)生成的第二个实例的散列码是不同的,而我们正是使用后者进行查找的。

public class Shoot {
    protected int number;   //射击次数
    public Shoot(int n){this.number = n;}
    public String toString(){
       return "Shoot # " + number;
    }
    //重写hashCode()方法,用number作为散列码
    public int hashCode(){return number;}
    //重写equles方法,默认的equals()只是比较对象的地址
    public boolean equals(Object o){
        return o instanceof Shoot && (number == ((Shoot)o).number);
    }
}

Shoot射击类中重写Object的hashCode()equals(Object o)后,就可以正常查找射击是否命中了。

再写一个Map

我们知道了数组实现map的缺点,又了解了散列码和hashCode(),现在我们根据这些信息,让我们再实现一个更加完善的map吧。

public class SlowMap<K, V> extends AbstractMap<K, V> {

    private List<K> keys = new ArrayList<K>();
    private List<V> values = new ArrayList<V>();

    public V put(K key, V value) {
        V oldValue = get(key);
        if (!keys.contains(key)) {
            keys.add(key);
            values.add(value);
        } else values.set(keys.indexOf(key), value);
        return oldValue;
    }

    public V get(Object key) {
        if (keys.contains(key)) {
            return values.get(keys.indexOf(key));
        }
        return null;
    }

    public V remove(Object key) {
        if (keys.contains(key)) {
            keys.remove(keys.indexOf(key));
        }
        return !keys.contains(key) ?
                null : values.get(keys.indexOf(key));
    }

    public void clear() {
        if(keys != null && keys.size() > 0){
            keys = null;
            values = null;
        }
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Map.Entry<K,V>> set = new HashSet<>();
        Iterator<K> ki = keys.iterator();
        Iterator<V> vi = values.iterator();
        while (ki.hasNext()) set.add(new MapEntry<>(ki.next(),vi.next()));
        return set;
    }

    public static void main(String[] args) {
        SlowMap<Integer ,String > map = new SlowMap<>();
        String[] chars =
                "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
                        .split(" ");
        for (int i = 0; i < chars.length; i++){
            map.put(i,chars[i]);
        }

        System.out.println(map);
        System.out.println("Map Size == " + map.size());
        System.out.println(map.entrySet());
        System.out.println(map.get(4));
        System.out.println("删除元素: 【4】");
        map.remove(4);   //删除集合中的某个元素
        System.out.println("Map Size == " + map.size());
        //map.clear();//清空集合
        System.out.println(map);
        
        System.out.println(map.get(4));
    }

}
public class MapEntry<K, V> implements Map.Entry<K, V> {
    private K key;
    private V value;

    @Override
    public K getKey() {
        return key;
    }

    @Override
    public V getValue() {
        return value;
    }

    @Override
    public V setValue(V value) {
        V reslut = value;
        this.value = value;
        return reslut;
    }
        
    public int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }

    public String toString(){return key + "=" + value;}

    public MapEntry(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

分析代码:

SlowMap类继承了AbstractMap,又因为AbstractMap实现了Map接口,这样SlowMap就包含了Map借口的完整实现,继承AbstractMap需要实现entrySet()方法,entrySet()是返回此映射中包含的映射关系的 set 视图集合。
entrySet()中使用的MapEntry类作用是保存和读取键值,在entrySet()中用来产生键值对的Set
这些代码看似很完美的模拟了map集合了,没毛病了~!

代码问题

  • 问题出在Key和Value分别保存在了两个List集合中,整个类中entrySet()方法只是提供了Map的副本,而不是视图。
  • 再有List集合移除元素的速度也是很不理想的。

总之,这个比用单纯的数组是强多了,但是还是有很多可以优化的地方。

优化性能的自定义Map

public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
    static final int SIZE = 997;

    LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];

    public V put(K key, V value) {
        V oldValue = null;
        //计算散列码 abs(int a),返回a的绝对值
        int index = Math.abs(key.hashCode()) % SIZE;
        //如果集合数组中没有元素,则初始化一个数组元素
        if (buckets[index] == null) buckets[index] = new LinkedList<>();
        //获取元素
        LinkedList<MapEntry<K, V>> bucket = buckets[index];
        MapEntry<K, V> pair = new MapEntry<>(key, value);   //将存入KEY,VALUE值存入pair

        boolean found = false;
        ListIterator<MapEntry<K, V>> it = bucket.listIterator();
        while (it.hasNext()) {
            MapEntry<K, V> iPair = it.next();
            /**
             * 对list中的值进行线性查询,解决冲突
             * 既:当向数组集合中插入已经存在的key时,将会用新值的value替换原来的value值
             * */
            if (iPair.getKey().equals(key)) {
                oldValue = iPair.getValue();
                it.set(pair);
                found = true;
                break;
            }
        }
        if (!found) buckets[index].add(pair);
        return oldValue;
    }

    public V get(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets == null) return null;
        for (MapEntry<K, V> iPair : buckets[index]) {
            if (iPair.getKey().equals(key)) return iPair.getValue();
        }
        return null;
    }

    public V remove(Object key) {
        int index = Math.abs(key.hashCode()) % SIZE;
        if (buckets == null) return null;
        for (MapEntry<K, V> iPair : buckets[index]) {
            if (iPair.getKey().equals(key)) {
                //如果存在key的键值,则删除
                buckets[index].remove(iPair);
            } else{
                return iPair.getValue();
            }
        }
        return null;
    }

    public void clear() {
        if (buckets != null && buckets.length > 0) {
            buckets = null;
        }
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> set = new HashSet<>();
        if(buckets != null && buckets.length > 0){
            for (LinkedList<MapEntry<K, V>> bucket : buckets) {
                if (bucket == null) continue;
                set.addAll(bucket);
            }
        }
        return set;
    }

    public static void main(String[] args) {
        SimpleHashMap<Integer, String> map = new SimpleHashMap<>();
        String[] chars =
                "A B C D E F G H I J K L M N O P Q R S T U V W X Y Z"
                        .split(" ");
        for (int i = 0; i < chars.length; i++) {
            map.put(i, chars[i]);
        }
        System.out.println(map.entrySet());
        System.out.println("map的长度是:" + map.size() + " ,第7个元素是: " + map.get(6));
        map.remove(6);
        System.out.println("map的长度是:" + map.size());
        System.out.println(map.get(6));
        map.clear();
        System.out.println(map.entrySet());
    }

}

虽然还存在一点小瑕疵(在解决冲突方面的性能还是略微欠缺),基本上可以表达map的原理了…

总结回顾

HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。既向Map中存入键值对时,实际上是初始化一个数组。使用散列码可以根据key找到对应的value,散列码是在hashCode()中计算。

转载请注明:R&M » JAVA集合——Map原理浅析

喜欢 (0)or分享 (0)
发表我的评论
取消评论

表情

联系我:rm@rmworking.com