互联网架构-Java8集合框架源码分析-040：LinkedList集合源码深度解析

040：LinkedList集合源码深度解析

1 HashMap课程深度源码分析介绍

课程内容：
1、初始HashMap底层源码分析
2、使用ArrayList实现HashMap集合
3、HashCode碰撞问题如何解决
4、使用LinkedList集合手写HashMap集合

2 HashTable与HashMap之间的区别

1.继承和实现方式不同
HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口；
Hashtable继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
2.线程安全不同
Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程；
HashMap的函数是非同步的，它不是线程安全的。
3.对null值的处理不同
HashMap的key、value都可以为null；
Hashtable的key、value都不可以为null。

3 自定义Map接口中Entry对象作用

public interface MayiktMap<K, V> {

    /**
     * 集合大小
     *
     * @return
     */
    int size();

    /**
     * 添加元素
     *
     * @param key
     * @param value
     * @return
     */
    V put(K key, V value);

    /**
     * 根据key查询
     *
     * @param key
     * @return
     */
    V get(K key);

    // 使用Entry对象存放键值对，封装key和value
    interface Entry<K, V> {
        /**
         * 获得key
         * @return
         */
        K getKey();

        /**
         * 获得value
         * @return
         */
        V getValue();

        /**
         * 设置value
         * @param value
         * @return
         */
        V setValue(V value);
    }
}

4 基于Arraylist集合实现HashMap

public class MayiktArrayListMap<K, V> implements MayiktMap<K, V> {

    private List<Entry> entrys = new ArrayList<Entry>();

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

    // 缺点：key重复没有处理，覆盖
    public V put(K key, V value) {
        Entry entry = new Entry(key, value);
        entrys.add(entry);
        return value;
    }

    // 缺点：遍历所有，效率太低
    public V get(K key) {
        for (Entry entry : entrys) {
            if (entry.getKey().equals(key)) {
                return (V) entry.getValue();
            }
        }
        return null;
    }

    // 使用Entry对象存放键值对，封装key和value
    class Entry<K, V> implements MayiktMap.Entry<K, V> {
        private K k;
        private V v;

        public K getKey() {
            return this.k;
        }

        public V getValue() {
            return this.v;
        }

        public V setValue(V value) {
            this.v = value;
            return this.v;
        }

        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
}

public class Test001 {

    public static void main(String[] args) {
        MayiktArrayListMap<String, String> mayiktArrayListMap = new MayiktArrayListMap<String, String>();
        mayiktArrayListMap.put("zhangsan", "111");
        mayiktArrayListMap.put("lisi", "222");
        System.out.println(mayiktArrayListMap.get("zhangsan"));//111
        System.out.println(mayiktArrayListMap.get("lisi"));//222

    }
}

5 hashCode与equals之间的区别

HashCode作用：hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值，主要应用于HashMap能够快速查找。

HashCode和Equals实现都是可以比较对象使用，区别就在于：
用HashCode比较两个对象相同，对象不一定相同；
用Equals比较两个对象相同，对象一定相同。
所以，一般先使用HashCode比较两个对象，如果不同，对象肯定不同（不需要使用Equals比较）；如果相同，再继续使用Equals比较。

public class Test002 {
    public static void main(String[] args) {
        String a = "a";
        Integer b = new Integer(97);
        System.out.println(a.hashCode());//97
        System.out.println(b.hashCode());//97

    }
}

6 基于Linkedlist集合实现HashMap（get和put方法）

如何解决HashCode冲突问题？
使用链表技术，如果两个对象不同，但是hashCode相同，底层会通过一个链表存放相同hashCode对象。

public class MayiktLinkedListMap<K, V> implements MayiktMap<K, V> {

    private LinkedList<Entry>[] objects = new LinkedList[100];

    public int size() {
        return 0;
    }

    public V put(K key, V value) {
        // 计算数组下标位置
        int hash = hash(key);
        LinkedList<Entry> linkedList = objects[hash];
        Entry entry = new Entry(key, value);

        if (linkedList == null) {
            linkedList = new LinkedList();
            linkedList.add(entry);
            objects[hash] = linkedList;
            return value;
        }
        // 产生hashCode冲突问题，使用equals判断key是否相同，是否需要修改value
        for (Entry ey : linkedList) {
            if (ey.getKey().equals(key)) {
                ey.setValue(value);
                return value;
            }
        }
        // hashCode相同，对象不同
        linkedList.add(entry);


        return value;
    }

    public V get(K key) {
        if (key == null) {
            return null;
        }
        int hashCode = hash(key);
        LinkedList<Entry> linkedList = objects[hashCode];
        if (linkedList != null) {
            for (Entry ey : linkedList) {
                if (ey.getKey().equals(key)) {
                    return (V) ey.getValue();
                }
            }
        }
        return null;
    }

    private int hash(K key) {
        int hashCode = key.hashCode();
        int hash = hashCode % objects.length;
        return hash;
    }

    // 使用Entry对象存放键值对，封装key和value
    class Entry<K, V> implements MayiktMap.Entry<K, V> {
        private K k;
        private V v;

        public K getKey() {
            return this.k;
        }

        public V getValue() {
            return this.v;
        }

        public V setValue(V value) {
            this.v = value;
            return this.v;
        }

        public Entry(K k, V v) {
            this.k = k;
            this.v = v;
        }
    }
}

public class Test003 {
    public static void main(String[] args) {
        MayiktLinkedListMap mayiktLinkedListMap = new MayiktLinkedListMap();
        mayiktLinkedListMap.put("a","zhangsan");
        mayiktLinkedListMap.put(97,"lisi");
        System.out.println(mayiktLinkedListMap.get("a"));//zhangsan
        System.out.println(mayiktLinkedListMap.get(98));//lisi
    }
}

本文地址：https://blog.csdn.net/u012425860/article/details/111994545