源代码：https://gitee.com/AgentXiao/Collection

一、HashMap的底层实现（线程不安全，效率高）

HashMap的存储方式是键（key）值（value）对。

二、自己实现一个简单的HashMap

（1）键值对类

package pri.xiaowd.demo03;

/**
 * @ClassName Entry
 * @Description 键值对
 * @Author xwd
 * @Date 2018/10/7 15:43
 */
public class Entry {
    private Object key;
    private Object value;

    public Entry() {
    }

    public Entry(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    public Object getKey() {
        return key;
    }

    public void setKey(Object key) {
        this.key = key;
    }

    public Object getValue() {
        return value;
    }

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

（2）以一个数组的方式存储键值对，不考虑数组扩容的问题（直接初始化一个大容量的数组）

    private Entry[] entry = new Entry[1024];
    private int size;//键值对的个数

（3）size()
add(Object key,Object value)
get(Object key)
remove(Object obj)

    /**
     * @MethodName size
     * @Descrition 获得键值对的个数
     * @Param []
     * @return int
     */
    public int size(){
        return size;
    }

    /**
     * @MethodName put
     * @Descrition 添加键值对
     * @Param [obj, value]
     * @return void
     */
    public void put(Object obj,Object value){
        Entry e = new Entry(obj,value);//新建一个键值对
        entry[size++] = e;
    }
    /**
     * @MethodName get
     * @Descrition 根据键查找值
     * @Param [key]
     * @return java.lang.Object
     */
    public Object get(Object key){
        for(int i=0;i<size;i++){
            if(entry[i].getKey().equals(key)){
                return entry[i].getValue();
            }
        }
        return null;
    }
    /**
     * @MethodName remove
     * @Descrition 移除键值对
     * @Param [key]
     * @return void
     */
    public void remove(Object key){
        for(int i=0;i<size;i++){
            if(entry[i].getKey().equals(key)){
                int numMoved = size-1-i;  //如果需要移除的是最后一个，则不需要进行拷贝搬移，而是直接将最后一个赋值null
                if(numMoved > 0){
                    System.arraycopy(entry,i+1,entry,i,numMoved);
                }
                size--;
                entry[size] = null;
            }
        }
    }

（4）containKey(Object key)
containValue(Object value)

    /**
     * @MethodName containsKey
     * @Descrition 判断是否存在key
     * @Param [key]
     * @return boolean
     */
    public boolean containsKey(Object key){
        for(int i=0;i<size;i++){
            if(entry[i].getKey().equals(key)){
                return true;
            }
        }
        return false;
    }
    /**
     * @MethodName containValue
     * @Descrition 判断似乎否存在value
     * @Param [value]
     * @return boolean
     */
    public boolean containValue(Object value){
        for(int i=0;i<size;i++){
            if(entry[i].getValue().equals(value)){
                return true;
            }
        }
        return false;
    }

（5）考虑到键不能重复，对put方法做一下改进

    /**
     * @MethodName put
     * @Descrition 添加键值对
     * @Param [obj, value]
     * @return void
     */
    public void put(Object key,Object value){
        Entry e = new Entry(key,value);//新建一个键值对
        //判断是否已经存在key，如果有的话直接覆盖
        for(int i=0;i<size;i++){
            if(entry[i].getKey().equals(key)){
                entry[i].setValue(value);
                return;
            }
        }
        entry[size++] = e;
    }

（6）这种写法效率低，因为如果有很多键值对，每次都要一个一个遍历。

三、升级版的HashMap（通过hashCode精准定位在数组的那个位置，如果位置重复使用链表进行存储）

数组+链表

    private LinkedList[] entry = new LinkedList[1024];//Map的底层实现：数组+链表
    private int size;//键值对的个数

（1）put和get方法

    /**
     * @MethodName put
     * @Descrition 添加键值对
     * @Param [obj, value]
     * @return void
     */
    public void put(Object key,Object value){
        Entry entry = new Entry(key,value);
        int hash = key.hashCode()%1024;//取余数，是0-1023之间的数值,可以定位数组的位置

        if(entryLinked[hash] == null){  //如果该位置还没有链表对象,新建一个并添加
            LinkedList linkedList = new LinkedList();
            entryLinked[hash] = linkedList;
            linkedList.add(entry);
        }else{  //如果该位置已经有链表对象,直接添加,但是要先判断是否重复
            LinkedList list = entryLinked[hash];
            for(int i=0;i<list.size();i++){
                Entry e = (Entry) list.get(i);
                if(e.getKey().equals(key)){
                    e.setValue(value);
                    return;
                }
            }
            entryLinked[hash].add(entry);
        }
    }
    /**
     * @MethodName get
     * @Descrition 根据key获取value
     * @Param [key]
     * @return java.lang.Object
     */
    public Object get(Object key){
        int hash = key.hashCode()%1024;

        if(entryLinked[hash] != null){
            LinkedList list = entryLinked[hash];
            for(int i=0;i<list.size();i++){
                Entry e = (Entry) list.get(i);
                if(e.getKey().equals(key)){
                    return e.getValue();
                }
            }
        }
        return null;
    }

（2）equals和hashCode
Java中规定，如果两个对象调用equals返回true，他们的hashCode是相等的。equals方法默认比较两者是否使用一个对象，在String中是重写过的，可以比较两者的内容是否相同。

注意：hashCode也可能是负数，做以下的改进

        int hashNum = key.hashCode();
        int hash = hashNum > 0 ? hashNum:-hashNum;

        hash = hash%1024;//取余数，是0-1023之间的数值,可以定位数组的位置

四、HashSet 无序不可重复 通过HashMap实现

1、add(Object key)：将key添加到HashMap的key中
JDK源代码如下：

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

set的不可重复是利用了map的键不可重复特性
自己实现的代码如下：

    /**
     * @MethodName add
     * @Descrition 添加内容
     * @Param [obj]
     * @return void
     */
    public void add(Object obj){
        map.put(obj,PRESENT);//set的不可重复是利用了map的键不可重复特性
    }

2、自己实现HashSet

/**
 * @ClassName MyHashSet
 * @Description 自己实现HashSet
 * @Author xwd
 * @Date 2018/10/7 17:53
 */
public class MyHashSet {

    private HashMap map;
    private static final Object PRESENT = new Object();

    public MyHashSet() {
        map = new HashMap();
    }
    /**
     * @MethodName size
     * @Descrition 得到元素个数，直接返回map的size()，
     * @Param []
     * @return int
     */
    public int size(){
        return map.size();
    }
    /**
     * @MethodName add
     * @Descrition 添加内容
     * @Param [obj]
     * @return void
     */
    public void add(Object obj){
        map.put(obj,PRESENT);//set的不可重复是利用了map的键不可重复特性
    }
    /**
     * @MethodName remove
     * @Descrition 移除内容
     * @Param [obj]
     * @return void
     */
    public void remove(Object obj){
        map.remove(obj);
    }
}

五、总结

ArrayList：有序可重复
LinkedList：无序可重复
HashMap：有序不可重复
HashSet：无序不可重复