HashMap的实现

作者: 小鸡在路上 | 来源:发表于2018-06-26 23:57 被阅读12次

    前言

    网上对于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;
            }
        }
    }
    
    

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

    相关文章

      网友评论

        本文标题:HashMap的实现

        本文链接:https://www.haomeiwen.com/subject/plsvyftx.html