HashMap的实现

前言

网上对于HashMap的实现有很多，也写得很不错。我也读过许多对数据结构有比较深理解的博文，感触也比较深。今天写这篇文章也可以算是一个读后感。或者说是对阅读之后的一个加深理解。其实HashMap的原理其实绝大部分的人都知道，底层是数组加链表结构实现的。但是为什么要这样实现，不知道大家有没有去想过这个问题。

数组

首先说一下数组的特性：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。数组对于给定下标查询的速度是非常快的，但是对于插入或者删除操作的时候，就稍微显得有点力不从心了。

链表

链表的特性:对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。从上面的时间复杂度可以看出，链表对于新增，删除操作是在非常快，对于查询就出现了它的弊端。

在这样的背景下，于是就有聪明人想到了一个问题。为何不将他们二者之间的优势结合起来，不就完美了吗。这是哈希表结构就应运而生了。

哈希表

相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。

t01a3c20166ce2ee885.jpg

根据上面的图，其实我们大致能看出他的实现思路。通过key的哈希函数获得对应的hash值，以hash值作为下标寻找对应的数组中的位置，如果当前位置没有值则插入，如果已经存在时。这时才是hashmap的精髓之处。这里我们统称 哈希冲突，如何解决这个冲突就产生了几个不同的数据结构方向。开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法（这里介绍一下 散列：散列（Hashing）是计算机科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。二次再散列法是指第一次散列产生哈希地址冲突，为了解决冲突，采用另外的散列函数或者对冲突结果进行处理的方法
），链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。

大致的一个思路是这样的，当然实际过程中肯定还有各种各样的问题，这只有亲身操作了才有体会。这里我也简单的实现了一把，并附上了注释以及说明。当然其中的很多功能并没有全部实现。

1.首先定义接口

package com.example.demo.MyHashMap;

public interface IMyMap<K,V> {

    // 实现hashmap时 需要注意的几个地方 1.了解HashMap数据结构组成 数组+单链表
    // 2.如何解决key hash后的平均分布，减少碰撞 hash函数实现
    // 3.数据阈值的控制以及扩容

    public  V put(K k,V v);

    public  V get(K k);

    // 定义内部entry接口
    interface Entry<K,V>{

        public  K getKey();

        public  V getValue();
    }
}

2.实现接口

package com.example.demo.MyHashMap;
import java.util.ArrayList;
import java.util.List;

public class MyHashMap<K,V> implements IMyMap<K,V> {

    // 定义底层数组的初始化大小
    private static final  int DEF_INIT_CAP = 1 << 4;

    // 定义阈值比例 容量达到这个比例时，就需要进行扩容

    private  static final  float DEF_LOAD_FACTOR = 0.75f;

    private  int defaultInitSize;

    private float defaultLoadFactor;

    //map中entry数量
    private int entrySize;

    //table数组
    private  Entry<K,V>[] tables = null;

    // 定义构造函数 注意这里为什么需要这样定义构造函数 实际上用到的都是第二个构造函数。这里实际上用到了门面的设计模式。
    // 这里的主要作用是为:子系统提供一个集中化和简化的沟通管道
    public  MyHashMap(){
       this(DEF_INIT_CAP,DEF_LOAD_FACTOR);
    }

    // 初始化信息
    public  MyHashMap(int defaultInitSize,float defaultLoadFactor){

        if(defaultInitSize <0) throw new IllegalArgumentException();

        if(defaultLoadFactor <=0 || Float.isNaN(defaultLoadFactor)) throw new IllegalArgumentException();

        this.defaultInitSize = defaultInitSize;

        this.defaultLoadFactor = defaultLoadFactor;

        tables = new Entry[defaultInitSize];
    }


    @Override
    public V put(K k, V v) {
        //定义以前的值
        V oldValue = null;

        // 在put之前需要判断 map数量是否需要扩容
        if(entrySize >= (defaultInitSize * defaultLoadFactor)){
            // 需要进行扩容操作
            resize(2*defaultInitSize);
        }
        // 对key进行哈希处理 得到index位置
        int index = hash(k) & (defaultInitSize -1);
        // 判断这个位置 数组是否存在值
        if(tables[index] == null){
            tables[index] = new Entry<K,V>(k,v,null);
            ++entrySize;
        }else{
            // 如果存在 则需要遍历这个链表
            Entry<K,V> entry = tables[index];
            Entry<K,V> e = entry;
            // 遍历
            while (e != null){
                if(k == e.getKey()  || "k".equals(e.getKey())){
                    oldValue = e.value;
                    e.value = v;
                    return oldValue;
                }
                e = e.next;
            }
            // 重新插入tables中
            tables[index] = new Entry<K,V>(k,v,entry);
            ++entrySize;
        }
        return oldValue;
    }

    @Override
    public V get(K k) {
        int index = hash(k) & (defaultInitSize - 1);
        if(tables[index] == null){
            return null;
        }else{
            Entry<K,V> entry1 = tables[index];
            do {
                if(k == entry1.getKey() || k.equals(entry1.getKey())){
                    return entry1.getValue();
                }
                entry1 = entry1.next;
            }while (entry1.next != null);
        }

        return null;
    }

    // hash函数参考 采用jdk中实现的

    private  int hash(K k){
        int hashCode = k.hashCode();
        hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
        return hashCode ^ (hashCode >>> 7) ^(hashCode >>>4);
    }

    // 数组扩容 这里需要注意 初始变量需要改变
    public  void resize(int i){
        Entry[] table = new Entry[i];
        defaultInitSize = i;
        entrySize = 0;
        rehash(table);
    }

    public void rehash(Entry<K,V>[] newTable){
        // 对老的集合进行遍历 并放进新的集合中
        List<Entry<K,V>> list = new ArrayList<>();
        for(Entry<K,V> entrys : tables){
            if(entrys != null){
                // 对链表进行遍历
                do {
                    list.add(entrys);
                    entrys = entrys.next;
                }while (entrys != null);
            }
        }
        //将原来的引用覆盖
        if(newTable.length > 0){
            tables = newTable;
        }

        // 重新put
        for(Entry<K,V>  entry1 : list){
            put(entry1.getKey(),entry1.getValue());
        }
    }


    class Entry<K,V> implements  IMyMap.Entry<K,V>{
        private  K key;

        private  V value;

        private  Entry<K,V> next;

        public  Entry(){

        }

        public  Entry(K k,V v ,Entry<K,V> next){
            this.key = k;
            this.value = v;
            this.next = next;
        }

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

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

这里把代码都写在了一起，为了方便就没有单独在抽出来了.... 这只是一个简单的实现，如果有兴趣或者想提高自己对数据结构的理解，还是推荐亲自去实现一把，还是有收获的。如果觉得有收获记得点个赞(^__)