当前位置:首页 > Java技术 > 《java编程思想》:散列的原理

《java编程思想》:散列的原理

2022年08月06日 16:39:09Java技术4

以实现一个简单的HashMap为例,详细讲解在code之中。

简单解释散列原理:

1.map中内建固定大小数组,但是数组并不保存key值本身,而是保存标识key的信息

2.通过key生成数组角标,对应位置存放LinkedList,list中存放的是键值对

3.如此,无论放入多少个键值对,数组大小都不必改变,当key值生成的角标值重复时,获取对应位置的list,向list中添加键值对即可

4.当调用get()方法时,只需遍历对应角标位置的list,而不用遍历所有的键值对信息,所以加快了查询速度。

5.注意,get()和put()中使用的计算散列值,也就是数组角标的公式一定要一致,保证计算所得的角标一致

/**
 * Created by Don9 on 2017/
 */
public class MyHashMap<K,V> extends AbstractMap<K,V>{
    /* 1.自定义数组大小 */
    static final int SIZE = 999;
    /* 2.创建内部数组,数组存放的是LinkedList,而list中存放的是想要存放的键值对 */
    LinkedList<MyEntry<K,V>>[] buckets = new LinkedList[999];
    /* 3.put方法,此方法返回key对应的曾经的oldValue */
    public V put(K key,V value){
        /* 4.先定义一个返回值 */
        V oldValue = null;
        /* 5.根据key计算出一个散列值,用于当作内置数组的下角标(
            此公式不固定,是自定义的,但是要保证结果稳定不变,同时不能大于数组size) */
        int index = Math.abs(key.hashCode()) % SIZE;
        /* 6.当index位置为空时,填充新的list */
        if(buckets[index]==null){
            buckets[index] = new LinkedList<MyEntry<K,V>>();
        }
        /* 7.获取index位置的list */
        LinkedList<MyEntry<K, V>> bucket = buckets[index];
        /* 8.MyEntry是自定义的Entry实现类,用于保存键值对,这个类也可以自定义,只要实现接口Entry即可,
            新建entry保存传入的键值对 */
        MyEntry<K, V> newMe = new MyEntry<K, V>(key,value);
        /* 9.定义一个found标记,用于记录是否替换完毕 */
        boolean found = false;
        ListIterator<MyEntry<K, V>> it = bucket.listIterator();
        /* 10.遍历当前位置的list */
        while(it.hasNext()){
            MyEntry<K, V> oldMe = it.next();
            /* 11.list中已经存在了当前key */
            if(oldMe.getKey().equals(key)){
                /* 12.获得oldValue值,用于返回 */
                oldValue = oldMe.getValue();
                /* 13.用新的entry替换老的 */
                it.set(newMe);
                /* 14.标记改为true,说明替换完毕 */
                found = true;
                /* 15.跳出 */
                break;
            }
        }
        /* 16.如果未替换完毕,也就是说key值在之前的list中不存在 */
        if(!found){
            /* 17.添加新的entry到list中 */
            bucket.add(newMe);
        }
        /* 18.返回oldValue */
        return oldValue;
    }

    /* 19.定义get查找方法 */
    public V get(Object key){
        /* 20.生成散列值,也就是数组角标,此处一定要和put方法中生成方式一致,保证相同的key生成相同的位置 */
        int index = Math.abs(key.hashCode()) % SIZE;
        /* 21.index位置为null,不存在key,返回null */
        if(buckets[index]==null){
            return null;
        }
        /* 22.index位置不为null,遍历查询,返回value */
        for(MyEntry<K,V> me:buckets[index]){
            if(me.getKey().equals(key)){
                return me.getValue();
            }
        }
        return null;
    }


    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }
}

 

作者:don9's
来源链接:https://www.cnblogs.com/don9/p/6941298.html

版权声明:
1、JavaClub(https://www.javaclub.cn)以学习交流为目的,由作者投稿、网友推荐和小编整理收藏优秀的IT技术及相关内容,包括但不限于文字、图片、音频、视频、软件、程序等,其均来自互联网,本站不享有版权,版权归原作者所有。

2、本站提供的内容仅用于个人学习、研究或欣赏,以及其他非商业性或非盈利性用途,但同时应遵守著作权法及其他相关法律的规定,不得侵犯相关权利人及本网站的合法权利。
3、本网站内容原作者如不愿意在本网站刊登内容,请及时通知本站(javaclubcn@163.com),我们将第一时间核实后及时予以删除。


本文链接:https://www.javaclub.cn/java/18416.html

分享给朋友:

“《java编程思想》:散列的原理” 的相关文章

读Java编程思想随笔の数组

  数组与其他种类的容器之间区别有三:效率、类型和保存基本类型的能力。在Java中,数组是一种最高的存储和随机访问对象引用序列的方式。数组就是一个简单的线性序列,这使得元素访问非常快速。但是为这种速度所付出的代价是数组对象的大小被固定,并且在其生命周期中不可改变。你可以能会建议使用Ar...

Java编程思想 4th 第2章 一切都是对象

Java编程思想 4th 第2章 一切都是对象

Java是基于C++的,但Java是一种更纯粹的面向对象程序设计语言,和C++不同的是,Java只支持面向对象编程,因此Java的编程风格也是纯OOP风格的,即一切都是类,所有事情通过类对象协作来完成。 在Java中,使用引用来操纵对象,在Java编程思想的第四版中,使用的术语是...

Java编程思想学习(五)----第5章:初始化与清理

随着计算机革命的发展,“不安全”的编程方式已逐渐成为编程代价高昂的主因之一。 C++引入了构造嚣(constructor)的概念,这是一个在创建对象时被自动调用的特殊方法。Java中也采用了构造器,并额外提供了“垃圾回收器”。对于不再使用的内存资源,垃圾回收器能自动将其释放。...

回顾Java编程思想篇(一)

本文主要介绍Java中对象的理解。 很久以前看过Java编程思想这本书,当时看得不是很懂,重新拿起这本书,感觉非常陌生,于是产生了重新研究的念头,并做一些读书笔记。   一、一切都是对象 1、Java与...

JAVA编程思想三

第三章主要是对JAVA控制执行流程的介绍,在这里注意到了几点与C++的不同之处: (1)Java不允许像C++中对一个数字作为布尔类型的判断,即0为false,非0为true; (2)逗号操作符在C++中是取最后一个表达式的值作为整个表达式的值;在Java中将逗号操作符一般...

【Java编程思想】8.多态

【Java编程思想】8.多态

在面向对象的程序设计语言中,多态是继数据抽象和继承之后的第三种基本特征。 多态分离了“做什么”和“怎么做”,让接口和实现分离开,改善了代码的可读性和组织结构,创建了可拓展的程序。 封装,通过合并特征和行为来创建新的数据类型。 实现隐藏,通过将细节“私有化”把接口...

Java编程思想读书笔记之内部类

         现在是够懒得了,放假的时候就想把这篇笔记写出来,一直拖到现在,最近在读《Java编程思想》,我想会做不止这一篇笔记,因为之前面试的时候总会问道一些内部类的问题,那这本书的笔记就从内部类开始...

[JAVA]java编程思想-第一章-对象入门

第1章 对象入门 “为什么面向对象的编程会在软件开发领域造成如此震憾的影响?” 面向对象编程(OOP)具有多方面的吸引力。对管理人员,它实现了更快和更廉价的开发与维护过程。对分析与设计人员,建模处理变得更加简单,能生成清晰、易于维护的设计方案。对程序员,对象模...

Java编程思想第四版勘误

  坊间传说这本书翻译得很烂,我倒觉得还好。虽然看原文更准确,但是如果在具备一定编程思维和基础、能够看出来疑问的情况下,还是看中文更快一些,而且这本书本身也不适合初学者看。当然,错误和不通顺还是有的,而且官方和网上居然没有一份公开的勘误表,至少我没有搜到,搜索“Java编程思想第四版勘...

Java编程思想【温故知新】

第一章:对象导论 1. 抽象过程(类与对象的关系)   类是一类对象的共同行为(成员函数)与状态(成员变量),对象是具体类的实例化。(Eg.人类是一个类,共同的行为:吃,状态:名字。)   【类创建者需要考虑这件事情,回头看看这个概念四个字醍醐灌顶,每次创建这...

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。