第一步：来实现一个能想到的最简单的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的原理了…