前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >散列算法与散列码

散列算法与散列码

作者头像
JMCui
发布于 2018-03-15 08:58:05
发布于 2018-03-15 08:58:05
1.5K00
代码可运行
举报
文章被收录于专栏:JMCuiJMCui
运行总次数:0
代码可运行

一、引入

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
 1 /**
 2  * Description:新建一个类作为map的key
 3  */
 4 public class Groundhog
 5 {
 6     protected int number;
 7 
 8     public Groundhog(){
 9     }
10     public Groundhog(int number)
11     {
12         this.number = number;
13     }
14 
15     @Override
16     public String toString()
17     {
18         return "Groundhog{" + "number=" + number + '}';
19     }
20 }
21 
22 /**
23  * Description:新建一个类作为map的value
24  */
25 public class Prediction
26 {
27     private boolean shadow=Math.random() > 0.5;
28 
29     @Override
30     public String toString()
31     {
32         if (shadow) return "Six more weeks of Winter";
33         else return "Early Spring!";
34     }
35 }
36 
37 /**
38  * Description:测试类
39  */
40 public class SpringDetector
41 {
42     public static void detectSpring(Class grondHotClass) throws Exception{
43         Constructor constructor = grondHotClass.getConstructor(new Class[]{int.class});
44         Map map=new HashMap();
45         for (int i=0;i<10;i++){
46             map.put(constructor.newInstance(new Object[]{new Integer(i)}),new Prediction());
47         }
48         System.out.println("map="+map);
49 
50         Groundhog groundhog=(Groundhog)constructor.newInstance(new Object[]{new Integer(3)});
51         System.out.println(groundhog);
52 
53         if (map.containsKey(groundhog)) {//查找这个key是否存在
54             System.out.println((Prediction)map.get(groundhog));
55         }else {
56             System.out.println("key not find:"+groundhog);
57         }
58 
59     }
60     public static void main(String[] args)
61     {
62         try {
63             detectSpring(Groundhog.class);
64         } catch (Exception e) {
65             e.printStackTrace();
66         }
67     }
68 }

    看这个结果,问题就来了,map中明明存在Groudhog{number=3},为什么结果显示的是Key not find呢??问题出在哪里呢?原来是Groudhog类没有重写hashCode()方法,所以这里是使用Object的hashCode()方法生成散列码,而他默认是使用对象的地址计算散列码。因此,由Groudhog(3)生成的第一个实例的散列码与Groudhog(3)生成的散列码是不同的,所以无法查找到 key。但是仅仅重写hashCode()还是不够的,除非你重写equals()方法。原因在于不同的对象可能计算出同样的hashCode的值,hashCode 的值并不是唯一的,当hashCode的值一样时,就会使用equals()判断当前的“键”是否与表中的存在的键“相同”,即“

如果两个对象相同,那么他们的hashCode值一定相同。

如果两个对象的hashCode值相同,他们不一定相同。

    正确的equals()方法必须满足下列5个条件:

1、自反性: x.equals(x) 一定成立。

2、对称性: 如果x.equals(y)成立,那么y.equals(x)也一定成立。

3、传递性:如果x.equals(y)=true ,y.equals(z)=true,那么x.equals(z)=true也成立。

4、一致性:无论调用x.equal(y)多少次,返回的结果应该保持一致。

5、对任何不是null的x,x.equals(null)一定返回false。

二、理解hashCode()

     散列的价值在于速度:散列使得查询得以快速执行。由于速度的瓶颈是对“键”进行查询,而存储一组元素最快的数据结构是数组,所以用它来代表键的信息,注意:数组并不保存“键”的本身。而通过“键”对象生成一个数字,将其作为数组的下标索引。这个数字就是散列码,由定义在Object的hashCode()生成(或成为散列函数)。同时,为了解决数组容量被固定的问题,不同的“键”可以产生相同的下标。那对于数组来说?怎么在同一个下标索引保存多个值呢??原来数组并不直接保存“值”,而是保存“值”的 List。然后对 List中的“值”使用equals()方法进行线性的查询。这部分的查询自然会比较慢,但是如果有好的散列函数,每个下标索引只保存少量的值,只对很少的元素进行比较,就会快的多。

    不知道大家有没有理解我上面在说什么。不过没关系,下面会有一个例子帮助大家理解。不过我之前一直被一个问题纠结:为什么一个hashCode的下标存的会有多个值?因为hashMap里面只能有唯一的key啊,所以只能有唯一的value在那个下标才对啊。这里就要提出一个新的概念哈希冲突的问题,借用网上的一个例子:

    比如:数组的长度是5。这时有一个数据是6。那么如何把这个6存放到长度只有5的数组中呢。按照取模法,计算6%5,结果是1,那么就把6放到数组下标是1的位置。那么,7就应该放到2这个位置。到此位置,哈希冲突还没有出现。这时,有个数据是11,按照取模法,11%5=1,也等于1。那么原来数组下标是1的地方已经有数了,是6。这时又计算出1这个位置,那么数组1这个位置,就必须储存两个数了。这时,就叫哈希冲突。冲突之后就要按照顺序来存放了。所以这里Java中用的解决方法就是在这个hashCode上存一个List,当遇到相同的hashCode时,就往这个List里add元素就可以了。这才是hash原理的精髓所在啊!哈哈、纠结我一天。

三、HashMap的性能因子

容量(Capacity):散列表中的数量。

初始化容量(Initial capacity):创建散列表时桶的数量。HashMap 和 HashSet都允许你在构造器中制定初始化容量。

尺寸(Size):当前散列表中记录的数量。

负载因子(Load factor):等于"size/capacity"。负载因子为0,表示空的散列表,0.5表示半满的散列表,依次类推。轻负载的散列表具有冲突少、适宜插入与适宜查询的特点(但是使用迭代器遍历会变慢)。HashMap和hashSet的构造器允许你制定负载因子。这意味着,当负载达到制定值时,容器会自动成倍的增加容量,并将原有的对象重新分配,存入新的容器内(这称为“重散列”rehashing)。HashMap默认的负载因子为0.75,这很好的权衡了时间和空间的成本。

备注:为使散列分布均衡,Java的散列函数都使用2的整数次方来作为散列表的理想容量。对现代的处理器来说,除法和求余是最慢的动作。使用2的整数次方的散列表,可用掩码代替除法。因为get()是使用最多的操作,求余数的%操作是其开销的大部分,而使用2的整数次方可以消除此开销(也可能对hashCode()有些影响)

四、怎么重写hashCode()

现在的IDE工具中,一般都能自动的帮我们重写了hashCode()和equals()方法,但那或许并不是最优的,重写hashCode()有两个原则:

  • 必须速度快,并且必须有意义。也就是说,它必须基于对象的内容生成散列码。
  • 应该产生分布均匀的散列码。如果散列码都集中在一块,那么在某些区域的负载就会变得很重。

下面是怎么写出一份像样的hashCode()的基本指导:

1、给int变量result 赋予某个非零值常量,例如 17。

2、为每个对象内每个有意义的属性f (即每个可以做equals()的属性)计算出一个 int 散列码c:

3、合并计算得到的散列值:result=37*result+c;

4、返回 result;

5、检查hashCode()最后生成的结果,确保相同的对象有相同的散列码。

五、自定义HashMap

下面我们将自己写一个hashMap,便于了解底层的原理,大家如果看的懂下面的代码,也就很好的理解了hashCode的原理了。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * Description:首先新建一个类作为map中存储的对象并重写了hashCode()和equals()方法
 */
public class MPair implements Map.Entry,Comparable
{
    private Object key,value;

    public MPair(Object key,Object value)
    {
        this.key = key;
        this.value=value;
    }
    @Override
    public int compareTo(Object o)
    {
        return ((Comparable)key).compareTo(((MPair)o).key);
    }
    
    @Override
    public Object getKey()
    {
        return key;
    }

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

     @Override
    public int hashCode()
    {
        int result = key != null ? key.hashCode() : 0;
        result = 31 * result + (value != null ? value.hashCode() : 0);
        return result;
    }

    @Override
    public boolean equals(Object o)
    {
        return key.equals(((MPair)o).key);
    }

    @Override
    public Object setValue(Object v)
    {
        Object result=value;
        this.value=v;
        return result;
    }
    
    @Override
    public String toString()
    {
        return "MPair{" + "key=" + key + ", value=" + value + '}';
    }
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public class SimpleHashMap extends AbstractMap
{
    
    private static final int SZ=3;//定一个初始大小的哈希表容量
    private LinkedList[] linkedLists=new LinkedList[SZ];//建一个hash数组,用linkedList实现
    public Object put(Object key,Object value){
        Object result=null;
        int index=key.hashCode() % SZ;//对key的值做求模法求出index
        if (index<0) index=-index;
        if (linkedLists[index]==null) linkedLists[index]=new LinkedList();//如果这个index位置没有对象,就新建一个

        LinkedList linkedList = linkedLists[index];//取出这个index的对象linkedList
        MPair mPair = new MPair(key,value);//新建要存储的对象mPair
        ListIterator listIterator = linkedList.listIterator();
        boolean found =false;
        while (listIterator.hasNext()){//遍历这个index位置的List,如果查找到跟之前一样的对象(根据equals来比较),则更新那个key对应的value
            Object next = listIterator.next();
            if (next.equals(mPair)){
                result = ((MPair) next).getValue();
                listIterator.set(mPair);//更新动作
                found=true;
                break;
            }
        }
        if (!found) linkedLists[index].add(mPair);//如果没有找到这个对象,则在这index的List对象上新增一个元素。
        return result;

    }

    public Object get(Object key){
        int index = key.hashCode() % SZ;
        if (index<0) index=-index;
        if (linkedLists[index]==null) return null;
        LinkedList linkedList = linkedLists[index];
        MPair mPair=new MPair(key,null);//新建一个空的对象值,因为equals()的比较是看他们的key是否相等,而在List中的遍历对象的时候,是通过key来查找对象的。
        ListIterator listIterator = linkedList.listIterator();
        while (listIterator.hasNext()){
            Object next = listIterator.next();
            if (next.equals(mPair)) return ((MPair)next).getValue();//找到了这个key就返回这个value
        }
        return null;

    }

    @Override
    public Set<Entry> entrySet()
    {
        Set set=new HashSet();
        for (int i=0;i<linkedLists.length;i++){
            if (linkedLists[i]==null) continue;
            Iterator iterator = linkedLists[i].iterator();
            while (iterator.hasNext()){
                set.add(iterator.next());
            }
        }
        return set;
    }

    public static void main(String[] args)
    {
       SimpleHashMap simpleHashMap=new SimpleHashMap();
        simpleHashMap.put("1", "1");
        simpleHashMap.put("2", "2");
        simpleHashMap.put("3","3");
        simpleHashMap.put("4","4");//这里有四个元素,其中key是1和key是4的index是一样的,所以index为1的List上面存了两个元素。
        System.out.println(simpleHashMap);
        Object o = simpleHashMap.get("1");
        System.out.println(o);
        Object o1 = simpleHashMap.get("4");
        System.out.println(o1);

    }
}

六、结语

不知道大家理解了没?整了我一天,终于还算大概理解了其中的原理了。文笔比较粗糙,大家凑活看吧,毕竟,不会做饭的作家不是好程序员啊!哈哈...... 或者,可能我有很多理解的不到位的地方,还请大家不吝指教!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
Flex + XML的图片轮显
逻辑部分与JavaScript有些类似,在解析XML时,单独写了一个as类来处理,btn的外观使用了CSS进行控制,资源全部放在名为assets文件夹目录下,工程目录
meteoric
2018/11/16
4170
Flex笔记_格式化数据 原
注意:上述代码没有输出结果是因为Flex内部会把XML转换成一组高级对象,既不是Date也不是String,而format函数只接受这两种对象作为参数,因此代码需要做如下修改:
LeoXu
2018/08/15
5970
Flex实现
传统网络应用是基于页面的,服务器端数据传递的模式,而且将网络程序的表示层建立于HTML之上,但是HTML只适合文本。因此,传统的,基于页面的系统已经越来越不适应使用者的全方位提要要求。富因特网应用程序(Rich Internet Application)便应运而生了。
张哥编程
2024/12/17
1580
Flex效果
通过前面章节的学习,我们已经可以开发FLex应用了,本章的任务是对Flex应用进行美化以提高用户的感受度。
张哥编程
2024/12/17
1050
Flex事件机制(三)
本文通过介绍自定义事件,讲解了在Flex中如何实现事件机制,并利用EventDispatcher类简化了自定义事件的实现。通过一个具体的实例,展示了如何创建一个自定义事件并派发,最后总结了使用自定义事件的好处。
高爽
2017/12/28
8480
Flex事件机制(三)
Flex4中的ModuleLoader,Alert以及TitleWindow
1、ModuleLoader 在Asp.Net开发中,经常会把页面的公共部分封装成自定义控件ascx,以达到重用或动态加载的目的。在Flex4中MXML Module能达到类似的功能,可以把某些功能单
菩提树下的杨过
2018/01/22
7910
Flex常用组件
本章主要介绍如何使用Flex组件构建界面。Flex组件可分为可见组件和非可见组件。可见组件用于界面的外观设计,非可见组件为辅助应用程序的设计。例如,使用Flex非可见组件来存储数据,为一些多值可见组件提供数据源,如下拉框组件。另外,本章还着重介绍了Flex中最常用的几种组件, 包括复选框(CheckBox)、 下拉框(ComboBox)、列表框(List)、单选框(RadioButton)、输入框(Textln- put)、消息提示框(Alert)、AdvancedDataGrid数据表格组件、Tree组件、MenuBar 菜单导航组件、VideoPlayer视频播放组件等。
张哥编程
2024/12/19
2200
构建第一个Flex的Mobile APP
Flash Builder 4.5已经支持直接创建Flex Mobile Project,写一个最简单的例子
meteoric
2018/11/15
4890
使用代码分离构建自定义组件
这样,使用一个script标签来编写as代码,mxml代码和as代码混淆在一起,比较混乱,维护困难,看着也比较乱。
高爽
2022/05/07
4960
jquery图片幻灯片(小图列表,大图展示)
先来个效果图(没有服务器,没办法提供演示版) 效果不如FLASH版的好,接下来我就发出FLASH版的来 全部代码如下所示 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <META HTTP-EQUIV="Co
liulun
2022/05/09
2.4K0
jquery图片幻灯片(小图列表,大图展示)
Flex应用性能优化
前几章介绍了Flex应用开发的主要内容,本章将介绍Flex应用性能优化相关的知识,比如如何减少SWF文件的大小和内存泄漏问题以及改善代码性能的技巧等。很多时候,影响应用性能的主要因素是设计。不好的设计是导致应用性能低下的主要原因,而针对不同特点的应用,采用何种设计方法往往与设计者本身的经验和素质相关。在排除了设计的因素之后在Flex应用开发中还有很多具体细节和技巧可以提高Flex应用的性能,本章将介绍RSL技术以减小SWF文件的体积,和Flex垃圾回收原理,以及预防内存泄露的一些基本技巧。此外还介绍了Flex应用中进行打印机打印的常见方法。
张哥编程
2024/12/17
1070
Flex上传文件
前几天写了一篇jsp页面利用ajaxFileUpload上传文件。如今把flex上传页面也分享出来:
全栈程序员站长
2022/07/07
3580
flex4 amcharts 删除水印「建议收藏」
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116648.html原文链接:https://javaforall.cn
全栈程序员站长
2022/07/06
5400
flex4/flash builder中动态加载Module并与之交互的正确方式
关于flex中动态加载Module的文章,网上有很多,但多半是基于flex3的,如果在flash builder/flex4中按他们所提供的方法去做,最后将module加载到容器中时,会报:null object reference错误。 经过多番摸索,发现只能在ready回调中,以Object这种基本类型使用,不能强制做任何类型转型,方能正常加载到容器,并与加载后的实例交互(虽然这样flash builder的IDE环境中,无法智能代码提示),原因不明! 开始吧,先创建一个mxml Module,命名为:
菩提树下的杨过
2018/01/22
6670
as3的InteractivePNG例子
在as3中很多时候需要只能选中png中可视区域,即透明区域“感觉可以穿透”。两张png重叠的时候,鼠标可以分别响应它们的事件。如下图所示:
meteoric
2018/11/15
5630
Pylons 和 Flex 3
"Pylons" 和 "Flex 3" 是两个不同的技术,各自有着不同的背景和应用场景:
华科云商小徐
2024/07/03
1150
flash/flex 与 FluorineFx通讯之Hello World!
Bēniaǒk兄弟的Flex与.NET互操作(六):Flex和.NET协同开发利器FluorineFx 是基于vs2008 + flex builder3的,不知道什么原因,我在vs2010 + flash builder4 上试了几次,总是不成功(也许晚上应该自我检讨下人品鸟),于是有了这一篇东东,算是对 vs2010/flash builder4环境下的一个补充吧 .net的服务端依照参照silverlight获取外部数据的另一种选择:FluorineFx 里的做法,在TestLib.cs里定义一个方法
菩提树下的杨过
2018/01/23
9330
flash/flex 与 FluorineFx通讯之Hello World!
Flex笔记_使用Spark列表控件 原
ListBase ->  SkinnableDataContainer -> SkinnableContainerBase -> SkinnableComponent -> UIComponent ->
LeoXu
2018/08/15
6040
Flex与外部的数据通信
第3章讲解了视图状态、Flex页面间的跳转、Flex应用的模态窗体、数据绑定、使用拖放,图表等知识。本章将学习Flex与外部的数据通信。在实际开发过程中,Flex应用的数据往往来自于业务逻辑数据提供的服务器端。虽然Flex是用于开发富客户端界面的强大平台,可以编写业务逻辑,但从架构的角度看,仍然需要将核心的业务逻辑放在Flex程序之外。Flex与外部程序的数据通信主要包括HTTPService. WebService和Remoting 3种方式。
张哥编程
2024/12/17
1120
Flex简单小程序
主mxml: <?xml version="1.0" encoding="utf-8"?> <s:Application xmlns:fx="http://ns.adobe.com/mxml/2009
三产
2021/01/13
5390
相关推荐
Flex + XML的图片轮显
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档