手写ArrayList，LinkedList，HashMap集合

项目当中一直用到很多集合，却不知道他们底层是怎么实现的，很想了解他们实现原理，然后自己看了一些集合的源码和博客，根据自己的思路简单手写了一下ArrayList，LinkedList，HashMap的源码实现

1.ArrayList的底层是一个数组，查询效率比较高，添加和删除效率比较低低：代码如下：

/**
 * 手写ArrayList，基于数组
 * @author 24147
 *
 */
public class MyArrList {

    // 定义一个数组
    Object[] objs = new Object[4];

    int size = 0; //集合大小

    // 返回List的长度
    public int size() {
        return size;
    }

    // 添加元素
    public void add(Object value) {
        if (size == objs.length) {
            Object[ ] newObjs = new Object[objs.length * 2];
            System.arraycopy(objs, 0, newObjs, 0, size);
            objs = newObjs;
        }
        objs[size] = value;
        size++;
    }

    // 指定位置添加元素
    public void add(int index, Object value) {
        if (size == objs.length) {
            Object[ ] newObjes = new Object[objs.length * 2];
            // 分两次copy数组
            System.arraycopy(objs, 0, newObjes, 0, index);
            System.arraycopy(objs, index, newObjes, index + 1, size - index);
            objs = newObjes;
        } else {
            System.arraycopy(objs, index, objs, index + 1, size - index);
        }
        objs[index] = value;
        size++;
    }

    // 设置元素
    public void set(int index, Object value) throws Exception {
        if (index < 0 || index >= size) {
            throw new Exception("超出范围");
        }
        objs[index] = value;
    }

    // 访问元素
    public Object get(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new Exception("超出范围");
        }
        return objs[index];
    }

    // 删除元素
    public void remove(int index) throws Exception {
        if (index < 0 || index >= size) {
            throw new Exception("超出范围");
        }
        for (int i = (index + 1); i < size; i++) {
            objs[i - 1] = objs[i];
        }
        size--;
    }

    // 清除元素
    public void clear() {
        size = 0;
        objs = new Object[4];
    }

}

2.LinedList的底层是一个双向链表，添加和删除效率高，查询效率低，他的每一个元素都是一个节点：Node，Node类如下：

/**
 * 定义一个LinkedList的节点
 * @author 24147
 *
 */
public class Node {

    private Object value;   //节点的值

    private Node nextNode;  //下一个节点

    private Node preNode;   //上一个节点

    public Node(Object value) {
        super();
        this.value = value;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Node getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }

    public Node getPreNode() {
        return preNode;
    }

    public void setPreNode(Node preNode) {
        this.preNode = preNode;
    }

}

下面就是LinkedList代码的实现：

/**
 * 手写LinkedList，基于双向链表
 * @author 24147
 *
 */
public class MyLinkedList {

    private Node first; //链表的第一个节点

    private Node last;  //链表的最后一个节点

    private int size;   //定义LinkedList的长度

    public int size() {
        return size;
    }

    //增加元素
    public void add(Object value) {
        Node node = new Node(value);
        if (first == null) {        //添加的是第一个节点
            first = node;
        } else {    //第一个节点不为空
            last.setNextNode(node);
            node.setPreNode(last);
        }
        last = node;
        size++;
    }

    // 指定元素添加元素
    public void add(int index, Object value) {
        Node node = new Node(value);
        if (index == 0) {
            first.setPreNode(node);
            node.setNextNode(first);
            first = node;
        } else if (index == size) {
            last.setNextNode(node);
            node.setPreNode(last);
            last = node;
        } else {
            Node temp = first;
            // 找到要添加索引的上一个元素temp
            for (int i = 0; i < index - 1; i++) {
                temp = temp.getNextNode();
            }
            // 找到添加索引的下一个元素
            Node nextNode = temp.getNextNode();
            temp.setNextNode(node);
            node.setPreNode(temp);
            node.setNextNode(nextNode);
            nextNode.setPreNode(node);
        }
        size++;
    }

    //获取元素
    public Object get(int index) {
        if (index == 0) {
            return first.getValue();
        }
        Node temp = first;
        for (int i = 0; i < index; i++) {
            temp = temp.getNextNode();
        }
        return temp.getValue();
    }

    //删除元素
    public void remove(int index) {
        if (index == 0) {
            first = first.getNextNode();
            first.setPreNode(null);
        } else if (index == (size - 1)) {
            last.getPreNode().setNextNode(null);
            last = last.getPreNode();
        } else {
            Node temp = first;
            for (int i = 0; i < index; i++) {
                temp = temp.getNextNode();
            }
            //找到删除元素的上一个元素和下一个元素
            Node preNode = temp.getPreNode();
            Node nextNode = temp.getNextNode();
            preNode.setNextNode(nextNode);
            nextNode.setPreNode(preNode);
            // 对象垃圾回收
            temp = null;
        }
        size--;
    }

}

3.HashMap的底层是数组+链表的数据结构，结合了ArrayList和LinkedList的优点，查询，添加，删除效率都比较高，是项目最常用的一种数据结构，Entry类如下：

public class Entry<K, V> implements Map.Entry<K, V> {

    final K key;
    V value;
    Entry<K, V> next;   // 下一个节点
    int hash;   // 对象的hash值

    // 构造方法
    public Entry(K key, V value, Entry<K, V> next, int hash) {
        this.key  = key;
        this.value = value;
        this.next = next;
        this.hash = hash;
    }

    public final K getKey() {
        return key;
    }

    public final V getValue() {
        return value;
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

}

下面就是HashMap真正的实现了：

/**
 * 手写HashMap，基于数组+链表
 * @author 24147
 */
public class MyHashMap<K, V> {

    private Entry[ ] table; // 定义Entry类型数组

    static final int DEFAULT_INITIAL_CAPACITY = 16;//默认数组长度

    private int size;   // 当前集合长度

    // 构造函数
    public MyHashMap() {
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        size = 0;
    }

    // 添加元素
    public V put(K key, V value) {
        if (key == null) {
            return null;
        }
        int hash = key.hashCode();
        int index = getIndex(hash);
        Entry<K, V> entry = table[index];
        // 如果添加的key已经存在，只需要修改value值就行
        for (Entry<K, V> e = entry; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                V oldValue = e.getValue();
                e.setValue(value);
                return oldValue;
            }
        }
        // 如果key值不存在
        table[index] = new Entry<K, V>(key, value, entry, hash);        // 添加entry
        size++;
        return null;
    }

    // 获取元素
    public V get(Object key) {
        if (key == null) {
            return null;
        }
        int hash = key.hashCode();
        int index = getIndex(hash);
        // 遍历Entry，找出key对应的元素
        for (Entry<K, V> e = table[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                return e.getValue();
            }
        }
        return null;
    }

    // 删除元素
    public V remove(Object key) {
        if (key == null) {
            return null;
        }
        int hash = key.hashCode();
        int index = getIndex(hash);
        Entry<K, V> entry = table[index];
        for (Entry<K, V> e = entry, prev = null; e != null; prev = e, e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                if (prev == null) {
                    table[index] = e.next;
                } else {
                    prev.next = e.next;
                }
                size--;
                return e.value;
            }
        }
        return null;
    }

    // 获取数组长度
    public int size() {
        return size;
    }

    // 获取下标：index
    public int getIndex(int hash) {
        return hash % table.length;
    }

}